Wie man mit einem Python-Programm die Schwierigkeit von Sudokus bewertet, Teil 2
Um festzustellen, wie schwierig ein gegebenes Sudoku ist, haben wir einem Python-Programm menschliche Strategien beigebracht und auf Sudokus losgelassen.
(Bild: Thorsten HĂĽbner)
Angetrieben von der Frage, wie man die Schwierigkeit von Sudokus feststellt, haben wir einen Sudoku-Bewertungsalgorithmus programmiert, der ein gegebenes Sudoku mit menschlichen Strategien von leicht bis schwierig löst und am Ende einen Score ausgibt. Die Grundlage eines solchen Algorithmus haben wir an anderer Stelle erklärt.
Der in Teil 1 vorgestellte Algorithmus kann lediglich leichte Sudokus lösen. Um Zahlen einzusetzen, geht er nach zwei Prinzipien vor: Entweder es gibt für ein Feld nur einen einzigen Kandidaten oder er konnte die Zahl für ein Feld via Ausschlussprinzip ermitteln. In der Sudoku-Welt heißen die Strategien "offensichtlicher Single" und "versteckter Single" (engl. naked single und hidden single). Damit das Programm jedoch auch anspruchsvollere Sudokus lösen kann, müssen wir es mit weiteren Strategien füttern.
- Ein Programm löst Sudokus unvoreingenommen und kann anhand der verwendeten Strategien dessen Schwierigkeit bewerten.
- Unser erweitertes Skript beherrscht offensichtliche und versteckte Singles, zusätzlich offensichtliche und versteckte Paare sowie zeigende Paare und X-Wings.
- Um den Bewertungsalgorithmus zu testen, haben wir ihn gegen Menschen und andere Solver antreten lassen.
Deshalb erklären und implementieren wir in diesem Artikel vier weitere Methoden: offensichtliches Paar (naked pair), verstecktes Paar (hidden pair), zeigendes Paar (pointing pair) und X-Wing. Das gesamte Projekt finden Sie im GitHub-Repository. Für die Theorie der Strategien haben wir uns an etablierten Sudoku-Webseiten- und -Lösern wie HoDoKu, Sudokuwiki, sudoku.coach und dem Buch "The Logic of Sudoku" von Andrew C. Stuart orientiert.
Das war die Leseprobe unseres heise-Plus-Artikels "Wie man mit einem Python-Programm die Schwierigkeit von Sudokus bewertet, Teil 2". Mit einem heise-Plus-Abo können Sie den ganzen Artikel lesen.
