Um festzustellen, wie schwierig ein gegebenes Sudoku ist, haben wir einem Python-Programm menschliche Strategien beigebracht und auf Sudokus losgelassen.
(Bild: Thorsten Hübner)
25.03.2025, 13:00 Uhr
Lesezeit: 18 Min.
-
Wie man mit einem Python-Programm die Schwierigkeit von Sudokus bewertet, Teil 2
- Gruppentheorie
- Strategien
- Praxis
- Verstecktes Paar
- Intersection Methode
- X-Wing
- Bewertung
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 und anhören.
Immer mehr Wissen. Das digitale Abo für IT und Technik.
Übersicht über kleine KI-Modelle, die sich für den lokalen Betrieb eignen
Ob für das Feintunen, in einem RAG-System oder für den Offlinebetrieb: Small Language Models eignen sich auch für den lokalen Einsatz und sind einen Blick wert.
MicroSD-Karten ab 1 TByte im Test: Zusatzplatz im MacBook Pro
MacBook-Speicher ist teuer und nachträglich aufrüsten unmöglich. Besitzt Ihr Rechner jedoch einen SD-Kartenslot, können Sie hierüber vergleichsweise aufrüsten.
Wie man fotografische Bildpaare in Szene setzt
Bildpaare fotografisch in Szene setzen: Fotograf Torsten Andreas Hoffmann zeigt spannende Konzepte für Ausstellungen, Hängungen oder Doppelseiten in Büchern.
Fünf KI-Videogeneratoren im Test: Firefly, Kling AI, Luma AI, Runway ML und Sora
KI-Videogeneratoren versprechen realistische Clips zu generieren. Wie gut sind sie wirklich? Wir haben unter anderem OpenAI Sora, Firefly und Kling AI getestet.
Meta Quest 3: Wie Sie PC-Spiele und Windows-Fenster in Mixed Reality streamen
Via WLAN werden PC und Quest 3 (S) zum räumlichen Computer: So streamt man Spiele und virtuelle Displays mit Air Link, Windows, Steam Link und Virtual Desktop.
Einspeisevergütung und Förderung: Was künftige PV-Anlagenbesitzer wissen müssen
Eine PV-Anlage ist eine kostspielige Investition. Es gibt mehrere Möglichkeiten, die abzumildern. Spannend ist das vor allem bei einer bestehenden PV-Pflicht.
