Anhand des Logikrätsels Sudoku (Wikipedia) soll das Rücksetzverfahren (engl. Backtracking) als Problemlöseverfahren in der Algorithmik erklärt werden.
Backtracking (Wikipedia) geht nach dem Versuch-und-Irrtum-Prinzip (engl. trial and error) vor, das heisst, es wird versucht, eine erreichte Teillösung zu einer Gesamtlösung auszubauen. Wenn absehbar ist, dass eine Teillösung nicht zu einer endgültigen Lösung führen kann, wird der letzte Schritt zurückgenommen und es werden stattdessen alternative Wege probiert. Auf diese Weise ist sichergestellt, dass alle in Frage kommenden Lösungswege ausprobiert werden können. Mit Backtracking-Algorithmen wird eine vorhandene Lösung entweder gefunden (unter Umständen nach sehr langer Laufzeit), oder es kann definitiv ausgesagt werden, dass keine Lösung existiert. Backtracking wird meistens rekursiv implementiert und ist ein prototypischer Anwendungsfall von Rekursion.
Das Backtracking zum Lösen eines Sudoku ist ein einfacher rekursiver Algorithmus. Dessen Funktionsweise und Umsetzung in der Programmiersprache Python werden in diesen, sehr empfehlenswerten Videos gut erklärt:
Das folgende Sudoku ist eine grafische Umetzung des Algorithmus. Dank der Timeout-Funktion von Javascript ist es möglich, die Geschwindigkeit des Programms so zu drosseln, dass das Löseverfahren mitverfolgt werden kann.
In der Folge wird an diesem Beispiel der Algorithmus Schritt für Schritt erklärt.
Sudoku aufsetzen
Zuerst definieren wir das Sudoku-Feld mit den vorgegebenen Zahlen. Wir definieren dazu ein verschachteltes Array:
var sudoku =[[0, 0, 7, 0, 0, 9, 0, 4, 5],[9, 3, 0, 7, 0, 8, 2, 6, 0],[6, 0, 0, 0, 5, 0, 0, 0, 7],[0, 9, 0, 0, 8, 0, 5, 7, 0],[0, 0, 1, 4, 0, 7, 0, 3, 0],[7, 2, 4, 0, 6, 3, 9, 1, 0],[0, 7, 9, 2, 0, 5, 0, 0, 6],[0, 6, 0, 9, 1, 0, 7, 0, 3],[1, 0, 3, 0, 0, 6, 4, 0, 0]];
Das Array sudoku besteht aus 9 weiteren Arrays, ein Array pro Zeile. Diese inneren Arrays enthalten
9 Zahlen, eine pro Spalte. Die Zahl 0 bedeutet, dass das Feld leer ist.
Damit lässt sich die Zahl eines jeden Feldes wie folgt auslesen:
var field = sudoku[0][2]In Javascript (wie in anderen Programmiersprachen auch) beginnt man beim Zählen bei der 0. Oben wird also auf das Feld der 1. Zeile und der 3. Spalte zugegriffen, was die Zahl 7 zurückgibt.
Die Hauptfunktion
Wir definieren die Hauptfunktion backtracking(). Sie wird das Sudoku lösen, welches wir als Parameter
übergeben:
function backtracking(sudoku) {…}
Der Algorithmus beginnt damit, das erste freie Feld zu bestimmen. Dazu definieren wir eine zweite Funktion
nextEmptyField() und übergeben ihr das Array sudoku als Parameter:
function backtracking(sudoku) {var emptyField = nextEmptyField(sudoku);if (emptyField == null) {return true;}}
Die Funktion nextEmptyField liefert ein Array aus zwei Zahlen, der Zeilen- und der Spaltennummer des
ersten freien Felds im Sudoku. Dazu liest sie die Tabelle von oben links nach unten rechts aus und stoppt, wenn sie ein
leeres Feld findet. Ist kein freies Feld mehr vorhanden, gibt die Funktion null zurück.
In Zeile 4 prüfen wir daher, ob der Rückgabewert von nextEmptyField gleich null ist. Ist dem
der Fall, gibt backtracking den Wert true zurück. Damit ist das Sudoku gelöst.
Das nächste freie Feld
Nun kümmern wir uns um die Funktion nextEmptyField. Wir übergeben ihr sudoku und sie durchläuft
für jede Zeile von 0 bis 8 jede Spalte von 0 bis 8. Dies geschieht mittels zweier ineinander verschachtelter Schleifen:
function nextEmptyField(sudoku) {for (var row = 0; row < 9; row++) {for (var column = 0; column < 9; column++) {if (sudoku[row][column] == 0) {return [row, column];}}}return null;}
Die Variable emptyField enthält nun also ein Array des nächsten freien Feldes. Wir weisen die Werte den
Variablen row und column zu (Zeile und Spalte), welche wir in der Folge vermehrt brauche:
function backtracking(sudoku) {var emptyField = nextEmptyField(sudoku);if (emptyField == null) {return true;}var row = emptyField[0];var column = emptyField[1];}
Tiefensuche
Im Beispiel ist das nächste (erste) freie Feld [0, 0], also das Feld in der ersten Zeile und der ersten Spalte. Der Algorithmus prüft nun, welches die kleinste erlaubte Zahl für dieses Feld ist.
Wenn Menschen Sudokus lösen, dann prüfen sie in der Regel alle möglichen Zahlen für ein bestimmtes Feld. Der Algorithmus geht anders vor. Er sucht die kleinste erlaubte Zahl und setzt diese als gegeben für das Feld fest. Von da an versucht er dann, das restliche Sudoku zu lösen. In der Informatik wird dieses Verfahren Tiefensuche (Wikipedia) genannt.
Mithilfe eines Lösungsbaums kann das Prinzip der Tiefensuche visualisiert werden:
Wir sehen, dass wir fürs Feld [0, 0] zwei erlaubte Zahlen haben: 2 und 8. Die übrigen Zahlen sind entweder in der Zeile 0 oder der Spalte 0 oder im 3×3-Quadrat bereits enthalten. Nach den Sudoku-Regeln dürfen diese Zahlen also in diesem Feld nicht verwendet werden.
Bei der Tiefensuche wird nun eine der möglichen Zahlen für das Feld [0, 0] betrachtet und daraus die weiteren Möglichkeiten für die weiteren freien Felder eruiert. Der Algorithmus wählt dazu die jeweils kleinste mögliche Zahl. Hier also die 2. Daraus entwickeln sich die Äste des Baums nach unten.
Im zweiten freien Feld [0, 1] gibt es dann wiederum zwei mögliche Zahlen, 1 und 8. Der Algorithmus wählt auch hier die kleinere von beiden, also die 1. Im dritten freien Feld [0, 3] bleiben die Zahlen 3 und 6 als erlaubte Möglichkeiten, wobei die 3 gesetzt wird.
Im nächsten freien Feld [0, 4] kommt es dann zum Problem. Keine der Zahlen 1 bis 9 sind noch erlaubt. Der Algorithmus ist in eine Sackgasse geraten. Deshalb versetzt er sich selbst eine Stufe zurück (backtracking) und wählt bei Feld [0, 3] die nächst kleinere erlaubte Zahl, also die 6 aus. Und damit findet er dann auch im Feld [0, 4] eine mögliche Zahl, nämlich die 3. Würde er auch da in eine Sackgasse geraten, hätte er eine Stufe zurückversetzt, im Feld [0, 3] keine weiteren Möglichkeiten mehr und müsste nochmals eine Stufe zurückgehen zum Feld [0, 1] und dort die nächste erlaubte Zahl, die 8, setzen.
Tiefensuche bedeutet also, dass ein Algorithmus in einem Lösungsbaum immer nur eine Möglichkeit betrachtet und von da aus den Lösungsbaum nach unten durchläuft, bis er auf eine Sackgasse oder auf die Lösung stösst. Erst wenn er in einer Sackgasse gelandet ist, wählt er einen neuen Ast des Lösungsbaums.
Wir haben nun den Lösungsbaum für die ersten vier freien Felder betrachtet. Das Beispiel-Sudoku enthält 40 freie Felder. Der Lösungsbaum wird also enorm gross. Visuell lässt sich dies kaum darstellen. Aber der Algorithmus kann diese unzähligen Möglichkeiten problemlos alle durchlaufen, bis er eine Lösung gefunden hat.
Ist die Zahl erlaubt?
Zurück bei unserer backtracking-Funktion. Wir haben das nächste (erste) freie Feld bestimmt. Nun müssen
wir prüfen, welche kleinste Zahl von 1 bis 9 in diesem Feld erlaubt ist. Wir durchlaufen also eine Schleife von 1 bis 9 und
prüfen jede Zahl auf ihre Gültigkeit (Validität):
function backtracking(sudoku) {var emptyField = nextEmptyField(sudoku);if (emptyField == null) {return true;}var row = emptyField[0];var column = emptyField[1];for (var number = 1; number < 10; number++) {if (isValid(sudoku, row, column, number)) {…}}}
Die Gültigkeit prüfen wir mit einer zusätzlichen Funktion, die wir isValid() nennen. Als Paramter übergeben
wir ihr einerseits das Sudoku, aber auch die Zeile (row) und Spalte (column) des betroffenen Feldes und die Zahl (number),
welche geprüft werden soll. Als nächstes schauen wir uns diese Funktion genauer an.
Die Funktion isValid besteht aus drei Teilen. Zuerst prüfen wir, ob die Zahl in der Zeile bereits vorhanden ist.
Ist dies der Fall, geben wir false zurück, d.h. die geprüfte Zahl ist in diesem Feld ungültig. Als nächstes
prüfen wir, ob die Zahl in der Spalte bereits vorhanden ist. Auch da geben wir false zurück, wenn dies der Fall ist.
Als drittes müssen wir prüfen, ob die Zahl im entsprechenden 3×3-Quadrat bereits vorhanden ist. Denn auch dann wäre
die Zahl ungültig.
Wir gehen schrittweise vor und beginnen mit der Überprüfung der Zeile. Wir kennen Zeile und Spalte des Feldes. Somit können wir alle anderen Felder derselben Zeile mittels einer Schlaufe durchlaufen:
for (var c = 0; c < 9; c++) {if (sudoku[row][c] == number) {return false;}}
Wir verwenden mit c eine sogenannte Laufvariable. C steht für column. Wir lassen also die Spalte von 0 bis 8
durchlaufen und prüfen für jeden Wert, welche Zahl im Feld [row, c] enthalten ist. Die Zeile (row) lassen wir immer gleich. Wir
wollen ja alle Felder derselben Zeile erhalten. Entspricht die Zahl im Feld der Zahl, welche wir prüfen, geben wir
false zurück. Wenn die Zahl nicht bereits vorhanden ist, geht es weiter mit der Überprüfung der Spalte.
for (var r = 0; r < 9; r++) {if (sudoku[r][column] == number) {return false;}}
Dieser Abschnitt funktioniert analog. Wiederum nehmen wir eine Laufvariable, hier nun r für row und lassen die
Spalte (column) immer gleich. Wenn die Zahl auch hier nicht vorhanden ist, geht es weiter mit der Überprüfung des
3×3-Quadrats.
Dieser dritte Teil ist etwas anspruchsvoller. Denn dazu müssen wir zuerst wissen, in welchem Quadrat wir uns befinden. Dazu ermitteln wir das Feld oben links des Quadrats. Betrachten wir dazu vorerst nur die Zeile (die Spalte funktioniert danach genau gleich). Als Zeilenwerte haben wir die Werte 0 bis 8. Ihnen ordnen wir die entsprechende Zeile des gesuchten oberen linken Feldes zu:
| Zeile im Sudoku [Zs] | Zeile im Quadrat | |
|---|---|---|
| 0 | 0 | 0.00 |
| 1 | 0 | 0.33 |
| 2 | 0 | 0.67 |
| 3 | 3 | 1.00 |
| 4 | 3 | 1.33 |
| 5 | 3 | 1.67 |
| 6 | 6 | 2.00 |
| 7 | 6 | 2.33 |
| 8 | 6 | 2.67 |
Mathematisch gesehen geht es darum, eine Beziehung der Zeile im Sudoku und der Zeile im Quadrat herzustellen. In der dritten Spalte der Tabelle wird die Zeile im Sudoku durch 3 geteilt (weil wir 3×3-Quadrate haben). Lässt man bei den Quotienten die Nachkommastellen weg (man spricht dann auch von einer Ganzzahldivision) und multipliziert dann noch mit 3, so erhalten wir genau den gesuchten Wert, nämlich die Zeilenzahl des oberen linken Feldes eines Quadrats. Dasselbe können wir auch für die Spalte tun. Für die Funktion bedeutet das, dass wir das obere linke Feld eines Quadrats wie folgt bestimmen können:
var quadratStartRow = Math.floor(row / 3) * 3;var quadratStartColumn = Math.floor(column / 3) * 3;
Anders als z.B. in Python gibt es in Javascript keinen Operator für die Ganzzahldivision. Wir führen daher eine gewöhnliche
Division durch und runden das Ergebnis mit der Funktion Math.floor() auf die nächste ganze Zahl ab.
Nun kennen wir das linke obere Feld des 3×3-Quadrats, in welchem sich das zu prüfende Feld befindet. Von diesem oberen linken Feld aus können wir nun die alle 9 Felder des Quadrats überprüfen:
for (var r = 0; r < 3; r++) {for (var c = 0; c < 3; c++) {if (sudoku[boxStartRow + r][boxStartColumn + c] == number) {return false;}}}
Wir nutzen für die beiden Schleifen wiederum Laufvariablen (r für row und c für column) und lassen
diese die Werte 0, 1, 2 durchlaufen. Die Laufvariablen addieren wir zum zuvor berechneten Startwert des oberen linken Feldes
dazu. Damit werden die 9 Felder des Quadrats durchlaufen. Auch hier geben wir false zurück, wenn die Zahl eines
Feldes der Zahl entpricht, die wir prüfen sollen.
Fügen wir die drei Teile zusammen, so sieht die Funktion isValid nun so aus:
function isValid(sudoku, row, column, number) {for (var c = 0; c < 9; c++) {if (sudoku[row][c] == number) {return false;}}for (var r = 0; r < 9; r++) {if (sudoku[r][column] == number) {return false;}}var quadratStartRow = Math.floor(row / 3) * 3;var quadratStartColumn = Math.floor(column / 3) * 3;for (var r = 0; r < 3; r++) {for (var c = 0; c < 3; c++) {if (sudoku[boxStartRow + r][boxStartColumn + c] == number) {return false;}}}return true;}
Am Ende der Funktion, wenn für die zu prüfende Zahl kein Verstoss ausgemacht werden konnte, wird true
zurückgegeben. Damit wissen wir, dass die übergebene Zahl im entsprechenden Feld erlaubt ist.
Rekursion
Zurück in der backtracking-Funktion. Wir prüfen also, ob eine bestimmte Zahl in einem bestimmten freien Feld
erlaubt ist. Was passiert nun, wenn die Zahl erlaubt ist? In diesem Fall soll die Zahl in das entsprechende Feld eingetragen
werden und der Algorithmus soll mit dem nächsten freien Feld weiterfahren.
function backtracking(sudoku) {var emptyField = nextEmptyField(sudoku);if (emptyField == null) {return true;}var row = emptyField[0];var column = emptyField[1];for (var number = 1; number < 10; number++) {if (isValid(sudoku, row, column, number)) {sudoku[row][column] = number;var solved = backtracking(sudoku, grid);if (solved) {return true;}}}}
In Zeile 13 wird also die Zahl in das Feld geschrieben. Danach soll der Algorithmus das nächste freie Feld suchen und bei
diesem die Prozedur von vorne beginnen. Dazu müssen wir keinen weiteren Code schreiben. Denn wir können dem Algorithmus
mitteilen, dass er einfach die Funktion backtracking erneut aufruft. Damit ruft die Funktion sich selber auf.
Dieses Vorgehen nennt man Rekursion.
In Zeile 14 rufen wir also backtracking() erneut auf. Den Rückgabewert speichern wir in der Variable
solved. Wir prüfen solved sodann (Zeile 16) auf den Wahrheitsgehalt (true). Die
backtracking-Funktion gibt true zurück, wenn kein freies Feld mehr vorhanden ist, das Sudoku also
gelöst ist.
Bleibt noch die Frage, was zu tun ist, wenn solved stattdessen false zurückgibt. Dazu müssen wir
zuerst wissen, wann backtracking() überhaupt false zurückgibt. Wir befinden uns ja noch immer in der
Schleife, welche für ein freies Feld die Zahlen 1 bis 9 überprüft (Zeile 11 im Code oben). Wenn wir also am Ende der Schleife
angelangt sind, ohne eine gültige Zahl gefunden zu haben, geben wir false zurück:
function backtracking(sudoku) {var emptyField = nextEmptyField(sudoku);if (emptyField == null) {return true;}var row = emptyField[0];var column = emptyField[1];for (var number = 1; number < 10; number++) {if (isValid(sudoku, row, column, number)) {sudoku[row][column] = number;var solved = backtracking(sudoku);if (solved) {return true;}sudoku[row][column] = 0;}}return false;}
Gehen wir nun wieder in die Zeile 16 des Codes zurück. Wir haben backtracking() aufgerufen und false
zurückehalten. D.h. der Algorithmus ist im Lösungsbaum in eine Sackgasse geraten. Betrachten wir als Beispiel im Lösungsbaum
oben das Feld [0, 3]. Der Algorithmus hat die Zahl 3 als gültige Zahl für dieses Feld gewählt. Daraufhin wurde
backtracking() erneut aufgerufen, konnte aber keine gültige Zahl mehr finden.
Was muss der Algorithmus also tun? Er muss die Zahl 3 im Feld [0, 3] wieder entfernen und in der Schleife der Zahlen von 1 bis 9 weitere Möglichkeiten versuchen. Im Code oben schreiben wir also wieder 0 in das Feld (Zeile 20).
Visualisierung des Algorithmus
Dieses Sudoku visualisiert die Funktionsweise des Algorithmus. Lasse den Regler für die Geschwindigkeit ganz links und klicke auf «Sudoku lösen». Die Schritte des Algorithmus werden wie folgt dargestellt:
- Die Funktion
nextEmptyFieldhebt das zu prüfende freie Feld blau hervor. - In das blaue Feld werden nun die Zahlen von 1 bis 9 eingetragen.
- Die Funktion
isValidprüft der Reihe nach die Zahlen derselben Zeile und Spalte. Sie werden jeweils gelb hervorgehoben. - Tritt ein Konflikt auf, wird das Feld rot hervorgehoben und blauen Feld wird mit der nächsten Zahl weitergefahren.
- Tritt kein Konflikt auf, wird das blaue Feld zu einem grünen Feld und die Zahl wird eingetragen. Das nächste freie Feld wird danach blau hervorgehoben.
Ausblick
Die visuelle Umsetzung wurde erweitert um die Möglichkeit, ein leeres Sudoku selbst auszufüllen. Durch Antippen eines Felds lassen sich Zahlen von 0 bis 9 eingeben (0 für ein freies Feld).
Der Algorithmus wurde entsprechend um eine weitere Funktion ergänzt, um zu prüfen, ob ein Sudoku mit den vorgegebenen Zahlen überhaupt zu lösen ist.
Vollständiger Code
var sudoku =[[0, 0, 7, 0, 0, 9, 0, 4, 5],[9, 3, 0, 7, 0, 8, 2, 6, 0],[6, 0, 0, 0, 5, 0, 0, 0, 7],[0, 9, 0, 0, 8, 0, 5, 7, 0],[0, 0, 1, 4, 0, 7, 0, 3, 0],[7, 2, 4, 0, 6, 3, 9, 1, 0],[0, 7, 9, 2, 0, 5, 0, 0, 6],[0, 6, 0, 9, 1, 0, 7, 0, 3],[1, 0, 3, 0, 0, 6, 4, 0, 0]];function backtracking(sudoku) {var emptyField = nextEmptyField(sudoku);if (emptyField == null) {return true;}var row = emptyField[0];var column = emptyField[1];for (var number = 1; number < 10; number++) {if (isValid(sudoku, row, column, number)) {sudoku[row][column] = number;var solved = backtracking(sudoku);if (solved) {return true;}sudoku[row][column] = 0;}}return false;}function nextEmptyField(sudoku) {for (var row = 0; row < 9; row++) {for (var column = 0; column < 9; column++) {if (sudoku[row][column] == 0) {return [row, column];}}}return null;}function isValid(sudoku, row, column, number) {for (var c = 0; c < 9; c++) {if (sudoku[row][c] == number) {return false;}}for (var r = 0; r < 9; r++) {if (sudoku[r][column] == number) {return false;}}var quadratStartRow = Math.floor(row / 3) * 3;var quadratStartColumn = Math.floor(column / 3) * 3;for (var r = 0; r < 3; r++) {for (var c = 0; c < 3; c++) {if (sudoku[boxStartRow + r][boxStartColumn + c] == number) {return false;}}}return true;}
Publiziert im Oktober 2024