Hier geht es direkt zum Spiel 

Allgemein

Bis 2004 hatte ich noch nie von Sudoku gehört. Erst während des Pflichtpraktikums im Studium lernte ich einen Kollegen kennen, den das Sudoko-Fieber bereits gepackt hatte. Als Student der Computerwissenschaft wollte ich natürlich nicht selbst ein Sudoku lösen, sondern den PC für mich arbeiten lassen.

Der erste Versuch scheiterte am fehlenden, praktischen Wissen der Programmierung, vor allem aber am fehlenden Verständnis für Algorithmen mit deren Hilfe diese Art von Problemen einfach zu lösen sind. Diese persönliche Niederlage sollte mich über die nächsten zehn Jahre verfolgen.

Erst 2014 kam wieder Leben in das Thema, nachdem ich mit ähnlichen Algorithmen den auf meiner Webseite vorhandenen Spieleklassiker Vier Gewinnt  programmiert hatte. Die Lösung eines Sudoku besteht aus zwei Schritten.

Automatisierte Lösung

Einfache Elimination

Zuerst werden Felder gesucht, die auf Basis der Spielregeln und der gegebenen Werte anderer Felder nur noch einen möglichen Zielwert annehmen können. Der eindeutige Wert wird jetzt der Zelle zugeordnet. Dieser Schritt wird wiederholt, bis keine weiteren Felder mit einer eindeutigen Lösung identifiziert werden können. Ist das Sudoku nach diesem Schritt bereits löst, handelt es sich um ein sehr einfaches Sudoku, welches auch durch unerfahrene Spieler schnell gelöst werden kann. Ist das Sudoku nicht vollständig gelöst, dann existieren unbelegte Felder die mehrere mögliche Zielwerte einnehmen können. Diese Felder müssen im zweiten Schritt gelöst werden.

Backtracking

Für die restlichen Felder wird der komplette Suchbaum (Wikipedia: Externer Link ) abgegangangen. Die Suchtiefe entspricht der Anzahl leerer Felder zu Beginn des Backtracking. Wird auf der untersten Ebene ein gültiges Blatt im Suchbaum gefunden, gilt das Sudoku als gelöst, wenn nicht wird der Suchbaum weiter abgegangen. Die maximale, expotentielle Dauer der Suche wird durch die Breite und Tiefe des Suchbaums festgelegt, daher hilft die einfache, lineare Elimination die Suchzeit des Backtracking zu reduzieren.

Knackpunkte

Neues Sudoku erstellen

Mein erstes Ziel war die Berechnung einer Lösung für ein existierendes Sudoku (z.B. aus einer Tageszeitung). Es war nur logisch im nächsten Schritt nicht nur der "Spoiler" zu sein, sondern auch den Sudoku-Fans unter Euch die Möglichkeit zu geben Sudokus auf meiner Seite selbst zu lösen. Daher wurde das Paradigma umgedreht, ich muss ein Sudoku generieren.

Das Konzept ist einfach, zuerst generiert man ein zufälliges, gültiges, vollständig gelöstes Sudoku. Im zweiten Schritt werden Werte bei zufällig ausgewählten Feldern entfernt. Der Knackpunkt liegt im Stichwort "zufällig". Der zuvor beschriebene Lösungsalgorithmus bestimmt die im Suchbaum ERSTE valide Lösung. Das kann einfach nachvollzogen werden: Klickt man unten im Sudoku bei einem leeren Spielfeld auf "Lösen", wird immer das gleiche, einfachste Sudoku in einem Suchbaum angezeigt. "Zufällig" bedeutet in diesem Fall unter alle möglichen Sudokus ein zufälliges, gültiges zu finden. Dies ist in vertretbarer Zeit aufgrund der Komplexität nicht berechenbar. Mit folgender Hilfe kann doch in vertretbarer Zeit ein Sudoku generiert werden:

1. Im ersten Block links oben werden die Ziffern 1 bis 9 zufällig verteilt, eine Prüfung ist nicht notwendig, da noch keine Abhänigkeiten zu anderen Blöcken oder Zeilen und Reihen bestehen.
2. Das Gleiche erfolgt unter Berücksichtigung der Spielregeln für Block 2 und 3. Da allerdings der Suchbaum immer Aufsteigend sortiert ist, muss dafür gesorgt werden, dass innerhalb eines Blocks kein Muster entsteht, bei dem das Feld links oben zu sehr hoher Wahrscheinlichkeit einen kleineren Wert enthält als das Feld rechts unten. Daher wird die Lösungsreihenfolge der Felder innerhalb eines Blocks randomisiert.
3. Sind die ersten drei Reihen mit Ziffern gefüllt, kann jetzt Block für Block der Suchbaum aufgebaut und die Felder zufällig befüllt werden. So erhält man ein zufälliges, unsortiertes Sudoku innerhalb vertretbarer Rechenzeit.

Komplexitätsberechnung

Die Frage hinter der Komplexitätsberechnung ist, wie Ihr als Spieler beurteilt, ob es sich um ein schweres oder eher leichteres Sudoku handelt und wie man dieses "Empfinden" objektivieren und damit berechnen kann. Hier ein paar Fragen und erste Erkenntnisse zu diesem Thema, falls Ihr Euch bei dem Thema besser auskennt, freue ich mich über Feedback 

Kann die Komplexität mit der Anzahl

• leerer Felder
• aller möglichen Werte auf allen Feldern
• der Felder, in die ein bestimmter Wert eingetragen werden könnte,

bestimmt werden?

Es gibt hier verschiedene Ideen und Ansätze, eine Entscheidung habe ich für meine Version noch nicht getroffen. In meiner Version entscheidet aktuell nur die Anzahl der leeren Felder. Dazu folgendes Gedankenbeispiel: Bei Sudoku A und B sind jeweils 15 Felder frei. Sudoku A kann rein über einfache Eliminierung gelöst werden, bei Sudoku B besteht die Möglichkeit nicht, der Spieler muss durchprobieren. An dem Beispiel sieht man, dass rein die Anzahl leerer Felder nicht ausschlaggeben ist.

Jetzt erstmal viel Spaß beim spielen.

Spielen & Lösen

• Erstellen - wählt einen Schwierigkeitsgrad aus und lasst Euch ein neues Sudoku zum knobeln erstellen.
• Prüfen - nachdem ihr ein Sudoku gelöst habt, lasst Euch die Eingabe überprüfen.
• Lösen - tragt in ein leeres Spielfeld die Vorgaben aus einem anderen Sudoko ein und lasst es automatisch lösen.
• Leeren - setzt das gesamte Spielfeld wieder in einen vollständig leeren und bearbeitbaren Zustand.