Gestelltes Problem
Um 2000 herum stiess ich auf ein Spiel namens “Clickomania”, das ein Klon von SameGame ist. Dabei muss man Gruppen aneinandergrenzender Spielsteine gleicher Farbe “sprengen”. Darüberliegende Steine fallen in die entstandene Lücke und am Ende sollte möglichst kein Stein mehr übrig bleiben. Das machte Spass! Da bei mir immer so viele Steine übrig blieben, grübelte ich schon damals darüber, wie man wohl für eine gegebene Stellung eine optimale Lösung finden könnte. Als ich dann mit den Handyspielen anfing, dachte ich mir, dass es interessant sein könne, einen SameGame-Solver fürs Handy zu schreiben.

Programm
Bevor ich mit dem Solver anfangen konnte, musste ich erst einmal das Spiel selbst programmieren. Das war nicht schwer, deshalb legte ich einen Schwerpunkt auf eine saubere Animation und verschiedene Designs der Spielsteine. Dazu sollte die Anzahl der noch vorhandenen Spielsteine als Siebensegmentanzeige ausgegeben werden. Dafür besorgte ich mir eine technische Zeichnung einer solchen Anzeige und übertrug die Koordinaten der einzelnen Segmente in eine Java-Klasse. Wie immer alles Handarbeit (in den untigen Screenshots aus einem Nokia 6260-Emulator ist die Anzeige etwas zu gross, auf meinem Nokia 6300 ist das besser).

Solver habe ich dann zwei gemacht, erstmal einen dummen, der einfach nur Stellen sucht, wo man klicken kann. Danach dann einen, der für jede anklickbare Gruppe den “Nachher”-Zustand ermittelt und dann zählt wieviele “verwaiste” Steine es gibt. Die Gruppe, bei der die wenigsten Waisen anfallen, wird dann geklickt. Das ist schon recht passabel aber noch nicht optimal.

Screenshots: