@NicNacMan:
kannst du deinen Algorithmus zum Lösen solcher Gitter mal genauer beschreiben ?
Was ich bis jetzt an deinem Source erkennen konnte ist das er rein kombinatorisch alle Lösungen versucht durchzutesten. Das dürfte aber in diesem Falle ziemlich ineffizient sein. Man kann nämlich schon von Anfang an bestimmte Ausschlußannahmen treffen.
Desweiteren ist mir aufgefallen das deine Datenstrukturen, sprich dein Datenhandling sehr ineffizient ist. Statt eigene und auf Effizienz getrimmte Datenstrukturen zu benutzen, benutzt du Strings und ständige String Konvertierungen. Diese Funktionen sind enorm langsame Vertreter für solche Probleme.
Als aller erstes solltest du also anfang eigene und effizentieren Datenstrukturen aufzubauen. Zb.
Delphi-Quellcode:
type
TFieldNumber = (1..9);
TFieldNumbers = set of TFieldNumber;
TField = record
PossibleNumbers: TFieldNumbers;
ActualNumber: TFieldNumber;
... etc. pp.
end;
Nun kannst du als allererstes vor dem .Solve() das Spielfeld analysieren. Im obigen Link das erst Game hat zb. in Spalte 4 senkrecht die Zahlen 1,3,4,9,2,5 schon gesetzt, also fest. Es verbleiben nur 3 freie Felder in denen die Nummern 6,7,8 reinpassen können. Aber in der Zeile 5 findet man schon die 6 im mittleren 3x3 Kasten, ergo kann dort eben nicht die 6 stehen sondern nur 7 oder 8. Man kann also herausfinden:
1.) mit welcher Zeile/Spalte dein Suchalgorithmus beginnen muß, nämlich mit der Spalte/Zeile die die geringsten Zugmöglichkeiten zulässt.
2.) zu jedem Feld in deinem Brett kannst du wie oben schon angedeutet von Anfang an ermitteln welche Zahlen überhaupt möglich wären und welche sozusagen von vorhinein ausgeschlossen werden müssen. Im obigen Type -> TField.PossibleNumbers würden diese drinnen stehen. Dies Taktik reduziert enorm die Anzahl der möglichen Kombinationen die dein Algo. druchprobieren muß.
So, nun zum Suchalgo. Dieser sollte sozusagen parallel arbeiten. Das bedeutet, statt immer eine komplette Kombination eines Spielanfanges bis zum maximalen Ende durchzutesten geht man Parallel vor. Dabei muß man aber die Möglichkeit haben
1.) eine ganze Reihen von Kombinationsmöglichkeiten als Zugreihenfolge zu speichern
2.) gleiche Kombinations-Wege auszuschließen, also nicht doppelt/mehrfach zu berechnen
3.) jeder Kombinations-Möglichkeit ein Punktezahl zu vergeben die angibt wie wahrscheinlich man ausgehend von dieser Startkombiantion eine gültige Lösung finden kann
Der Suchalgo. initialisiert nun eine bestimmte Anzahl solcher Suchwege, und legt diese als Objekte in einem Priority Stack ab. Die Priorität welche dieser vielen Kobinationen nun einen/oder mehrere Schritte weitergerechnet werden häng von deren Punktezahl ab. Nach diesen par Schritten wird dieser Such-Weg anhand seiner Punktezahl neu im Priority Stack geordnet. Somit erhalten also diejenigen Such-Wege eine höhere CPU-Zeit und ergo Such-Tiefe die mit höherer Wahrscheinlichkeit eine korrekte Lösung finden werden.
Du musst das sogar so machen wenn du zb. kompliziertere Gitter in sehr kurzer zeit lösen möchtest.
Auf alle Fälle mach weiter, such nach besseren Datenstrukturen und Algorithmen, denn zum Erlernen von komplexen Spielmaschinen und eventuell KI's ist dieses Rätsel idel geeignet. Hast du dich schon mal mit genetischen Algorithmen befasst ? Das könnte dir eventuell weiterhelfen.
Gruß Hagen