SUDOKU Algorithmus

Logisches Denken

Ein Grund für den Erfolg von Sudoku ist sicher, dass zum Finden der Lösung ausschließlich logisches Denken erforderlich ist. Man benötigt kein auswendig gelerntes Wissen, kein Mathematikdiplom und kein Spezialwerkzeug - ein Bleistift und eine Sitzgelegenheit reichen aus.

Wie geht man nun am besten die Lösung eines Sudoku Rätsels an? Eine Möglichkeit ist das »Ausschließungsverfahren«: So sind auf dem links abgebildeten Rätsel bereits vier Felder mit der Ziffer 8 vorbelegt - zur Veranschaulichung hier jeweils rot eingekreist. Da nun die Regel besagt, dass jede Ziffer nur einmal pro Zeile und Spalte auftreten darf, sperren die vorhandenen Achten jeweils ihre komplette Zeile und Spalte für andere Achten. Im Bild sind diese Sperrungen durch dicke rote Linien markiert.

Betrachtet man nun den 3x3 Block in der Mitte links etwas genauer, dann fällt auf, dass dort die Ziffer 8 noch nicht vorhanden ist, andererseits aufgrund der gesperrten Zeilen und Spalten nur noch eine mögliche Position für die 8 übrig ist. Wir können hier sofort also eine 8 neu eintragen - in der Abbildung ist sie grün hervorgehoben.

Auf diese Art und Weise kann man sich schrittweise der Lösung nähern. Wie findet man nun die Ziffern, die für eine Ausschließung in Frage kommen? Zum Beispiel können das Zahlen sein, die sehr oft vorkommen oder die regelmäßig auf dem Spielfeld verteilt sind. Nach einiger Übung stellt sich eine gewisse Routine beim Entdecken aussichtsreicher Kandidaten ein.

Der Computer »denkt« anders

Spielverderber

Der Sudoku Spielverderber verwendet einen wesentlich einfacheren Lösungsalgorithmus. Das ist möglich, da ein moderner Computer deutlich schneller als ein Mensch verschiedene Möglichkeiten durchprobieren kann und sich vor allem von Fehlversuchen nicht frustieren lässt.

Das Lösungsprogramm sucht zunächst das erste freie Feld und probiert dann nacheinander alle Ziffern beginnend mit der Eins aus. Wenn eine Ziffer gefunden wurde, die die Spielregeln nicht verletzt, dann wird der Algorithmus mit dem nächsten freien Feld wiederholt. Wenn es kein freies Feld mehr gibt, dann ist das Rätsel gelöst. Falls jedoch keine der Ziffern 1 bis 9 in das Feld passt, dann geht das Programm ein Feld zurück und wiederholt das ganze mit der nächsten dort möglichen Ziffer.

Der Algorithmus lässt sich sehr elegant rekursiv formulieren, das heißt es gibt eine Lösungsfunktion solve(), die sich immer wieder selbst aufruft.

Generator

Besitzt man nun einen solchen Lösungsalgorithmus, dann kann auch ein Sudoku Generator relativ einfach programmiert werden:

Der Generator benutzt einen Zufallszahlengenerator, um ein beliebiges freies Feld zu ermitteln und eine Zahl für dieses Feld auszuwürfeln. Diese Zahl darf natürlich die Spielregeln nicht verletzen, falls doch, nimmt man einfach die nächste.

Nun wird versucht, das Rätsel zu lösen. Gibt es genau eine Lösung, dann ist ein neues Rätsel kreiert und der Generator kann sich beenden. Gibt es mehr als eine Lösung, dann wird der Schritt mit dem nächsten zufällig ausgewählten Feld wiederholt. Wenn keine Lösung möglich ist, geht man einen Schritt zurück und versucht sein Glück mit der nächsten Ziffer.

Auch dieser Algorithmus lässt sich als rekursives Programm aufschreiben.