Sudoku im Zorn lösen

Ich vermute, dass die meisten von Ihnen mit Sudoku vertraut sind. Diese Rätsel erscheinen jeden Tag in meiner Zeitung und ich muss sagen, dass mich jedes dieser halbmathematischen Rätsel fasziniert und ich dazu neige, süchtig zu werden. Und wenn ich süchtig werde, denke ich an ein Computerprogramm, um die Rätsel zu lösen. Dieses Gefühl ist am stärksten, wenn meine menschlichen Unfähigkeiten (Unachtsamkeit, Eifer) mich unfehlbar dazu verleiten, eines der Rätsel zu vermasseln. Als ich letzte Woche eines Abends ein weiteres Rätsel vermasselt habe, konnte ich nicht widerstehen und habe den Computer eingeschaltet. Es hat fast die ganze Nacht gedauert (es war etwa 6 Uhr, als ich endlich ins Bett kam), aber die Rätsel, die mir meine Zeitung bringt, werden mich nicht länger verfolgen: Ich habe ein Java-Programm implementiert, das Sudokus löst. Das Modell dieser Spiele ist ziemlich einfach. Um es ein wenig allgemeiner zu machen, halte ich mich an diese Beschreibung:

1. Es gibt ein Spiel, das aus einer rechteckigen Anordnung von Feldernbesteht.
2. Den Feldernkann ein Wert zugewiesen werden, der ein beliebiges Wort sein kann, aber normalerweise eine der Zahlen "1" bis "9" ist.
3. Das Spiel enthält auch eine Reihe von Gruppen. Diese Gruppen bestehen aus einem oder mehreren Feldernund können denselben Wert (der einem dieser Felderzugewiesen ist) nicht mehrmals enthalten.

Dies ist eine recht lose Beschreibung des Rätsels. Sie schränkt die Gruppen nicht auf eine Größe ein, die der Anzahl der zuzuordnenden Werte entspricht, und spricht auch nicht von einer begrenzten Menge zuzuordnender Werte. Diese Merkmale eines normalen Sudoku-Spiels sind jedoch nicht unbedingt notwendig, um ein Modell des Rätsels zu implementieren. Sie sind jedoch notwendig, um eine Gewinnstrategie zu implementieren! Beachten Sie, dass ein Spiel in dieser Implementierung dafür verantwortlich ist, zu überprüfen, ob ein Wert einem Feld gemäß Regel 3 zugewiesen werden kann. Die allgemeine Idee einer Strategie für dieses Rätsel ist, dass eine Strategie auf der Grundlage aller bisherigen Züge (Zuweisungen von Werten zu Feldern) einen weiteren Zug vorschlagen kann. Um einen Zug vorschlagen zu können, muss die Strategie alle bisherigen Züge abhören und eine bestimmte Statistik über die Felder des Spiels führen, die ihr helfen könnte, einen möglichen oder sogar obligatorischen Zug zu bestimmen. Die Schnittstelle für eine MoveStrategy in dieser Implementierung ist recht einfach:

public interface MoveStrategy {
/**
* Führen Sie einen Umzug durch, falls Sie einen vorschlagen können.
*
* @Rückgabe, ob eine Bewegung stattgefunden hat.
*/
boolean doMove();
/**
* Benachrichtigt die Strategie, dass ein Zug gemacht wurde.
*
* @param field Das Feld, das einen Wert erhalten hat.
*/
void notifyMove (Feld Feld);
/**
* Löscht den gesamten Status der Strategie.
*/
void reset ();
}

Wenn wir nun über die tatsächliche Umsetzung einer Strategie nachdenken, lassen Sie uns mit der einfachen Variante beginnen. In den 3x3 Spielen unten bilden die Spalten und Zeilen Gruppen und die Menge der zuweisbaren Werte besteht aus den Zahlen "1", "2" und "3". Es ist leicht zu erkennen, dass die Zahl "3" der letzten Zelle in der ersten Spalte zugewiesen werden muss, da ihr sonst ein Wert zugewiesen werden muss, der bereits einem Feld in der Spalte zugewiesen ist. Diese Strategie wird LastValueStrategy genannt, da sie den letzten freien Wert dem letzten freien Feld in einer Gruppe zuweist. Um diese Strategie umzusetzen, behalten wir die Anzahl der freien Werte für jede Gruppe im Auge. Beginnend mit einem leeren Spiel sind alle zuweisbaren Werte freie Werte für alle Gruppen. Sobald ein Feld einen Wert zugewiesen bekommen hat, verringern wir die Anzahl der freien Werte für jede Gruppe, in der sich das Feld befindet. Sobald eine Gruppe nur noch einen freien Wert hat, finden wir das (eine?) freie Feld in dieser Gruppe. Die Strategie schlägt nun vor, den freien Wert diesem Feld zuzuordnen. Natürlich ist diese Strategie nicht in der Lage, auch nur das einfachste Sudoku-Rätsel zu lösen. Es handelt sich jedoch um eine sehr einfache und leicht zu berechnende Strategie. Sehen wir uns das folgende Spiel an. Keinem Feld in der ersten Zeile dieses Spiels kann der Wert "1" zugewiesen werden. Keinem Feld in der zweiten Spalte kann der Wert "2" zugewiesen werden. Das bedeutet, dass dem Feld in Zeile 1 und Spalte 2 der Wert "3" zugewiesen werden muss (Dasselbe gilt für das Feld in Spalte 1 und Zeile 3). Diese Strategie wird PossibleValueForFieldStrategy genannt. Um sie umzusetzen, verwaltet die Strategie eine Reihe möglicher Werte für alle Felder. Immer, wenn einem Feld ein Wert zugewiesen wird, wird dieser zugewiesene Wert aus der Menge der möglichen Werte für alle Felder entfernt, die sich in einer Gruppe mit dem zugewiesenen Feld befinden. Immer wenn es nur einen einzigen Wert für ein Feld gibt, schlägt die Strategie vor, diesen Wert dem Feld zuzuweisen. Diese Strategie scheint ziemlich mächtig zu sein, aber sie verstummt im nächsten Spiel, obwohl es einen obligatorischen Zug zu machen gibt. Keinem Feld in der ersten Spalte kann der Wert "1" zugewiesen werden, auch keinem Feld in der zweiten Spalte. Das bedeutet, dass die ersten beiden Felder in der zweiten Zeile nicht den Wert "1" enthalten können. Daher muss dem letzten Feld in dieser Zeile dieser Wert zugewiesen werden (jemand muss ihn nehmen...). Diese Strategie wird PossibleFieldForValueInGroup genannt. Die Strategie verwaltet eine Reihe von freien Feldern für jeden Wert, pro Gruppe. Für die Gruppe, die aus der ersten Spalte des Spiels besteht, gibt es zwei freie Felder für den Wert "2" und zwei für den Wert "3". Für den Wert "1" gibt es keine freien Felder, da er in dieser Gruppe noch nicht zugewiesen wurde. In der letzten Spalte gibt es nur ein freies Feld für den Wert "1". Um den korrekten Zustand für diese Strategie beizubehalten, werden jedes Mal, wenn einem Feld ein Wert zugewiesen wird, alle Felder, die sich in einer Gruppe mit dem zugewiesenen Feld befinden, zu "verbotenen" Feldern; der zugewiesene Wert kann keinem der Felder zugewiesen werden. Für jede Gruppe im Spiel werden diese Felder aus den möglichen Feldern für den zugewiesenen Wert entfernt. Außerdem wird das zugewiesene Feld als mögliches Feld für alle Werte in allen Gruppen entfernt. Ich dachte immer noch über Ratestrategien nach, bei denen ein Feld und ein Wert ausgewählt und dann zurückverfolgt werden, wenn eine Unstimmigkeit gefunden wird, aber als ich diese drei Strategien gegen die Rätsel antreten ließ, die mir meine Zeitung gebracht hatte, waren sie in nur wenigen Millisekunden gelöst! Ich muss zugeben, dass die Art des Sudoku-Spiels recht typisch und eigentlich recht einfach ist. Bei den in der Zeitung veröffentlichten Rätseln gibt es vier zusätzliche Gruppen. Diese bestehen aus einem Block von 9 Zellen, die gleichmäßig im Spiel verteilt sind. Es gibt eine GameSpecification-Schnittstelle und eine GroupSpecification-Schnittstelle, mit deren Hilfe Sie andere Arten von Spielen konstruieren können (indem Sie die zusätzlichen Gruppen weglassen und/oder neue hinzufügen). Die Schnittstelle zu diesem Spiel ist derzeit sehr einfach. Es gibt einen ConsolePlayer, der einen Kommandozeilen-Client startet. Er kann einfache Spiele aus Textdateien lesen oder Anweisungen befolgen. Dies ist sicherlich ein Bereich, der verbessert werden kann. Bei weiteren Experimenten habe ich festgestellt, dass jede der beiden letztgenannten Strategien alle Rätsel lösen kann. Außerdem können die "klassischen" Sudoku-Rätsel (ohne die zusätzlichen Gruppen) auch mit diesen einfachen Strategien gelöst werden. Bis jetzt habe ich noch kein einziges Sudoku-Rätsel gefunden, das sich mit diesen Strategien nicht lösen lässt. Vielleicht können Sie helfen? Haftungsausschluss: Ich weiß, dass es andere Programme gibt, die Sudoku-Rätsel lösen, aber ich mag meine einfache, kleine Implementierung immer noch genug, um sie mit Ihnen allen zu teilen.