Rekursion, fürsorgliche Browser, vorherbestimmte Zufallszahlen
oder
Wie man den Stack verschont

Auch wenn die Spielregeln von Sudoku vielen Menschen bekannt sein sollten, möchte ich sie schon allein wegen der im Code verwendeten Namenskonvention kurz vorstellen.

Gegeben sei eine (vorzugsweise kleine) positive ganze Zahl, die hier mit SMALL_LINE bezeichnet werden wird. 1 führt zu trivialen Ergebnissen, aber 2 ist durchaus geeignet, 3 wird in den meisten Sudokus verwendet, 4 wäre auch möglich. Größere Zahlen eignen sich prinzipiell genauso, stellen aber menschliche wie maschinelle Rätsellöser vor kaum überwindbare quantitative Probleme. Das Quadrat von SMALL_LINE werde als LINE bezeichnet, das Quadrat von LINE wiederum als TOTAL. Demnach gilt SMALL_LINE4 = TOTAL. Das Spielfeld ist ein aus TOTAL Einzelfeldern bestehendes Quadrat mit LINE Reihen und LINE Spalten, welches in LINE kleine Quadrate mit der Kantenlänge SMALL_LINE eingeteilt wird, so daß sich die kleinen Quadrate nicht überlappen und das gesamte Spielfeld lückenlos bedecken. In einem gelösten Sudoku sind die Zahlen von 1 bis LINE so auf die Einzelfelder verteilt, daß in jeder Reihe, jeder Spalte und in jedem kleinen Quadrat jede dieser Zahlen genau einmal vorkommt1.

Der Begriff gelöstes Sudoku deutet schon an, daß noch nicht alles gesagt sein kann. In einem gültigen ungelösten Sudoku sind einige der Zahlen unkenntlich gemacht, und es ist die Aufgabe der Rätsellöser, die fehlenden Zahlen zu rekonstruieren. Es gilt die Regel, dem Spieler höchstens so viele Zahlen vorzuenthalten, daß die Lösung eineindeutig bleibt - anders ausgedrückt: ein gültiges Sudoku hat genau eine Lösung.
Es ist auffällig, daß für Sudokus mehr oder weniger immer Zahlen als Symbole verwendet werden, obwohl sie hier keinen Zahlwert haben; beliebige unterscheidbare Zeichen wären genauso geeignet2.

Aus rein mathematischer Sicht ist die Lösung eines Sudoku im Prinzip3 sehr einfach. Entgegen landläufiger Vorstellungen ist die Mathematik oft gar nicht so pingelig, was Zahlen angeht, und unterteilt sie lediglich in endlich und unendlich. Ein mathematischer Ansatz könnte in etwa sein:

Da die zweite und die dritte Bedingung die erste nicht infrage stellen, kann man die Aufgabe auf ein aus dem Bereich der Kombinatorik bekanntes Problem zurückführen - das heißt, man probiere die im ersten Punkt genannten Möglichkeiten vollständig durch; das erste gefundene gültige Sudoku muß die Lösung sein.

Die Überlegung ist völlig korrekt; ihre Umsetzung scheitert aber an dem Umstand, daß schon bei einem 81teiligen Sudoku unter Verwendung eines aktuellen Computers die benötigte Rechenzeit die Lebenserwartung desjenigen, der auf die Lösung wartet, bei weitem übersteigt (vom benötigten Speicherplatz für alle Kombinationsmöglichkeiten ganz abgesehen).

Unter menschlichen Rätsellösern gilt (vom nicht zu bewältigenden Aufwand abgesehen) Herumprobieren als ausgesprochen unelegant4. Ich bin durchaus kein Experte, aber meines Wissens folgt eine als effizient geltende Lösungsstrategie ungefähr diesem Schema:

Mit einem hat die Mathematik aber zumindestens prinzipiell6 recht: Das Lösen von Sudokus ist keine ehrenvolle Aufgabe für eine elektronische Apparatur. Schließlich liegt der Reiz einer Lösung seitens eines Menschen gerade in dessen begrenzten Ressourcen (sprich den Schwierigkeiten, sich über einen längeren Zeitraum zu konzentrieren) begründet. Maschinen können aber sehr hilfreich bei der Konstruktion neuer Rätsel, die Humanoiden Freude bereiten, sein. Für diese Aufgabenstellung soll im folgenden ein geeigneter Algorithmus gefunden werden.


 zurück: Programmiertechnische Grundlagenweiter: Schema eines Algorithmus 

1 Mit nur geringfügigen Änderungen ließen sich die Regeln auch auf rechteckige nicht-quadratische Spielfelder übertragen, was aber hier nicht weiter behandelt werden soll; um es mit Harry Potter zu sagen: Die meisten Muggle sind nicht daran gewöhnt.  ↑ 

2 Diese Erkenntnis hat weitreichende Konsequenzen. Zum einen bedeutet das, Zahlen gegeneinander austauschen zu dürfen, ohne den Charakter eines bestimmten Sudoku zu verändern (natürlich müssen dann alle gleichen Zahlen ausgetauscht werden). Zum anderen führt es dazu, sich von allen Ideen verabschieden zu müssen, die die Lösung eines Sudokus zu berechnen beabsichtigen. Zur Bestätigung dieser Aussage stelle man sich vor, alle Einsen durch Fünfen zu ersetzen, alle (ursprünglichen) Fünfen durch Achten und alle (ursprünglichen) Achten durch Einsen. Falls es irgendjemandem gelingen sollte, eine Rechnung aufzustellen, die gegen solche Vertauschungen invariant ist, wäre ich über eine Benachrichtigung dankbar. Die Möglichkeit, Zahlen immerhin nacheinander aufzählen zu können, kann trotzdem dankbar angenommen werden.  ↑ 

3 Seien Sie wachsam, wenn Sie den Begriff prinzipiell aus dem Mund eines Mathematikers hören! In der wirklichen Welt ist oft das Gegenteil der Fall.  ↑ 

4 Der betreffende Abschnitt bei Wikipedia gebraucht die Formulierung amateurhaft, die mich verwundert hat, da sie die Existenz von Menschen, die mit dem Lösen von Sudokus ihren Lebensunterhalt verdienen, nahelegt. Bevor ich falsch verstanden werde: Ich hätte nichts dagegen einzuwenden.  ↑ 

5 Schätzungen können Fehleinschätzungen sein. Im Gegensatz zu manchen anderen Rätseln führt jedoch hier eine falsche Beurteilung am Anfang nicht zu exponentiell ansteigenden Bearbeitungsschritten oder gar dem Nicht-Auffinden der Lösung, sondern lediglich zur Verpflichtung zu ein paar zusätzlichen Gedankengängen.  ↑ 

6 Schon wieder diese Formulierung! Ich habe Sie gewarnt, siehe Fußnote 3.  ↑