Der Sudoku-Solver

Noch im Bett gelegen fand ich ein Youtube-Video, welches mir die Implementierung eines Sudoku-Solvers erklärte. Überraschend war der stupide Ansatz, der dies ermöglicht.

Um mir eine weitere Challenge zu setzen, begann ich das ganze "schön" in VueJS zu implementieren. Gerade da VueJS aktuell das Framework ist, kleine Webseiten zu erstellen, fand ich diesem Weg passend um meinen Horizont zu erweitern.

Der Algorithmus basiert auf Backtracking und Rekursion, also definitiv kein Anfängerproblem zum Lösen. Doch einmal verstanden erscheint es einem zu dumm, als dass es funktionieren sollte, denn das Programm probiert wortwörtlich jede Zahlenkombination aus. Wir fangen oben links im Sudoku an und arbeiten uns komplett nach unten durch. Jede Zahl wird probiert und überprüft, ob diese aktuell überhaupt möglich wäre. Die erste passende Zahl nehmen wir und probieren das nächste Feld.

Beim ersten Mal wird das Programm wahrscheinlich keine Lösung direkt finden. Deshalb, sobald im aktuellen Feld keine Zahl mehr möglich ist, gehen wir einen Schritt zurück (zum vorherigen Feld) und setzen die nächste mögliche Zahl ein. Im Worst-Case gehen wir bis zum Anfang zurück und probieren im ersten Feld die nächste Zahl. Entweder finden wir am Ende  eine Kombination, oder das Sudoku ist nicht lösbar.

Der Pseudo-Code sieht so aus:

for all cells:
 for all number from 1 to 9:
   if number is valid in cell:
     try next cell
   else
     try next number in previous cell

Das Projekt habe ich auf GitHub veröffentlicht: https://github.com/scorixear/SudokuSolver
Eigene Sudokus kann man auf https://kellerus.de/sudokusolver lösen.