Sudoku Solver
Heute geht es um ein kleines Projekt, das auch schon ein paar Monate zu etwa 95% fertig auf der Festplatte rumlag und jetzt endlich fertiggestellt wurde: Einen Sudoku Solver.
Was macht sowas? Nun, wie der Name schon sagt, löst es Sudokus.
Sudokus und ihre Regeln
Sudokus, für alle die es nicht kennen, sind eine Form von Logikrätsel, mit einem Spielfeld von üblicherweise 9 x 9 Feldern. In jeder Zeile und jeder Spalte dürfen die Ziffern von 1 bis 9 dabei nur einmal vorkommen, ebenso darf in einem „Quadranten“ (3 x 3 Felder große Bereiche) jede dieser Ziffern nur einmal vorkommen. Am Ende darf kein Feld frei bleiben, einige der Ziffern sind fix vorgegeben.
Die Spielregeln sind also im Kern nicht besonders komplex und auch das Programm hinter dem Sudoku Solver ist es eigentlich nicht. Bei dieser kleinen Bastelei ging es nicht um besonders abgefahrenes Programmieren, sondern darum, ein bekanntes Schema in Funktionen und Algorithmen „zu gießen“, um das nachzubilden, was man als Mensch auch beim Lösen macht.
Wie löst man ein Sudoku?
Nun, wie löst man als Mensch ein Sudoku? Man kann natürlich wild drauf losraten und Kombinationen ausprobieren, aber angesichts der Spielregeln empfiehlt sich natürlich ein logischer, formalisierter Ansatz.
Dabei durchläuft man für jedes freie Feld, folgende Schritte:
- Mögliche Ziffern für mein Feld sind 1 bis 9.
- Welche Ziffern sind in der Reihe meines Feldes bereits platziert?
- Diese von den möglichen Ziffern abziehen.
- Welche Ziffern sind in der Spalte meines Feldes bereits platziert?
- Diese von den möglichen Ziffern abziehen.
- Welche Ziffern sind im Quadranten meines Feldes bereits platziert?
- Diese von den möglichen Ziffern abziehen.
- Die übrigen möglichen Ziffern werden für das Feld notiert.
Schauen wir uns das an einem Beispiel an. Sagen wir, unser Feld sieht so aus:
|-------|-------|-------| | 3 4 * | | 5 | | 5 | 4 | 1 3 | | | 8 | 9 7 | |-------|-------|-------| | 6 | 1 | 2 | | 9 | 4 7 | 5 | | 8 | 2 | 7 | |-------|-------|-------| | 5 1 | 2 | | | 7 9 | 1 | 5 | | 3 | | 9 1 | |-------|-------|-------|
Ich möchte die möglichen Ziffern für das Feld mit dem Sternchen finden.
Möglich: 1, 2, 3, 4, 5, 6, 7, 8, 9 Zeile enthält: 3, 4, 5 Möglich: 1, 2, 6, 7, 8, 9 Spalte enthält: 5, 8, 1, 9 Möglich: 2, 6, 7 Quadrant enthält: 3, 4, 5 Möglich: 2, 6, 7
Damit sind die möglichen Ziffern für dieses Feld die 2, die 6 und die 7.
Wenn ich das für mein gesamtes Spielfeld durchgführe, dann finde ich unter Umständen Felder, bei denen nur eine einzige Ziffer möglich ist.
Diese Felder fülle ich mit den Ziffern und erhalte damit ein neues Spielfeld. Für das neue Spielfeld führe ich das gleiche Prozedere erneut durch.
Wenn man etwas Glück hat, dann ist allein durch dieses Vorgehen ein Sudoku vollständig und eindeutig lösbar.
Funktionsweise des Sudoku Solvers
Und genau das probiert auch mein Sudoku Solver.
Er führt auf einem vorgegebenen Spielfeld (das muss man natürlich einmal eintragen) genau diesen Regelsatz aus, solange er „eindeutige Treffer“ (also Felder mit nur einer einzigen möglichen Ziffer) findet.
Findet er keine eindeutigen Treffer mehr, dann hört er auf. Hier fängt nämlich der knifflige Teil an: Durch Ausprobieren der übrigen, möglichen Kombinationen ergeben sich wiederum neue Felder, die sich lösen lassen, oder aber den Regeln widersprechen.
Auch das ließe sich durch einen Bruteforce-Algorithmus abbilden (der probiert dann einfach alle möglichen Kombinationen aus), aber das zu entwickeln, dazu hatte ich bisher keine Lust.
Ausprobieren und Quellcode
Ausprobieren lässt sich der Sudoku Solver jetzt unter https://www.flomei.de/projekte/sudoku-solver/
Sudokus zum Füttern des Startfeldes gibt es zum Beispiel auf https://sudoku.com/ aber auch in fast jeder Tageszeitung oder sonstwo, wo es auch Kreuzworträtsel gibt. ;-)
Den Quellcode zum Sudoku Solver habe ich auf gitlab veröffentlicht: https://gitlab.com/www-flomei-de/sudoku-solver
Über mich
Ich bin gelernter Mediengestalter, studierter Druck- und Medientechniker und leidenschaftlicher Tüftler und Bastler.
Beruflich beschäftige ich mich mit der digitalen Transformation von Unternehmen, sowie der Automatisierung von Unternehmensprozessen, in der Druck- und Medienbranche. Mehr dazu findet sich im Lebenslauf.
Privat interessieren mich Kaffee(maschinen), Themen rund um Webentwicklung, das Internet im Allgemeinen und Speziellen und vieles, vieles mehr.
Ich freue mich auf Feedback per E-Mail unter kontakt@flomei.de, einen Euro für die Kaffeekasse oder etwas von meiner Amazon Wunschliste.