Die Türme von Hanoi, ohne Ausprobieren mittels Backtracking, sondern mit straight forward betimmten verlege Anweisungen. Die Idee ist: um n Scheiben von A nach C zu verschieben, verschiebe n-1 Scheiben von A nach B, dann eine scheibe von A nach C, dann n-1 Scheiben von B nach C.

Meine Seminar-Ausarbeitung und -Vortragsfolien vom Hauptseminar exakte Algorithmen (WS2007/08) beim Lehrstuhl für theoretische Informatik (wo ich auch vertiefe und vorhabe, mein Diplom und Doktortitel zu machen)
Mein Thema war das Minimum Quartet Inconsistency Problem (MQI) welches parametrisierbar ist (der Wikipedia Artikel über parametrisierte Algorithmen stammt übrigens von mir :-) ).
Im Rahmen des Seminars habe ich einen viel kürzeren (Widerspruchs-)Beweis für den Hauptsatz aus dem Paper von Niedermeier und Gramm gefunden und die Laufzeit von verbessert auf .

Ein kleines Progrämmchen, das Lösungen für Solitär findet (das Brettspiel, welches im Englischen "Peg Solitaire" heisst - nicht das Kartenspiel Patience, welches im Englischen "Solitaire" heisst).
Blankes Backtracking, aber da es für das Spiel so viele Lösungen gibt, ist so ne Lösung fix gefunden.

Zwei Programme, die den Baum des Pythagoras zeichnen (ein hübsches Fraktal) eins für DOS, das ich mal während der Schulzeit geschrieben habe und (aus nostalgischen Erinnerungen an die Schulzeit) eine Neuauflage für Windows...

Ein Programm, das scramble square puzzles löst. Dadurch, dass immer die Position belegt wird, auf die die kleinste Anzahl von Puzzleteilen passt oder das Puzzleteil platziert wird, für das die kleinste Anzahl von Positionen in Frage kommt (jenachdem, was weniger ist), wird der Verzweigungs-Vektor sehr klein gehalten. Ausserdem werden Situationen erkannt und ausgenutzt, in denen mehrere Puzzleteile identisch sind und es werden symmetrische Lösungen vermieden. Das führt zu sehr guten Laufzeiten - in den Beispielen werden nur etwa 300-400 Rekursionen benötigt, obwohl es Kombinationen gibt. In den Rekursionsaufrufen werden jeweils Schritte benötigt.
Ich habe auch die alte Version noch einmal dazu gepackt, damit man den Unterschied in den Laufzeiten sehen kann.

Ein Programm, das Probleme wie das SEND MORE MONEY Problem löst - allerdings arbeitet das mit ner brute force analyse, also sehr langsam.