Wie man mit einem Python-Programm die Schwierigkeit von Sudokus bewertet

Inhaltsverzeichnis

Die Macher von Sudokus vertreten unterschiedliche Auffassungen, wie schwer ein Sudoku ist: Was die einen leicht nennen, kann bei anderen schon schwer sein. Und wie schwer ist schwer? Mittelschwer, teuflisch oder bestialisch? Gut vergleichbar sind die Angaben deshalb nicht. Man kann den Schwierigkeitsgrad herausfinden, ohne das Sudoku dafür selber lösen zu müssen. Stattdessen überlässt man das einem Programm, das ihn anhand der zum Lösen benötigten Strategien berechnet. Wie das in Grundzügen geht, erklärt dieser Artikel.

Der Artikel korrigiert einen Fehler, den wir vor rund zwei Jahren hinterlassen haben: Wir hatten einen Sudoku-Generator programmiert und leichtfertig angenommen, dass die ausgespuckten Rätsel umso schwieriger sind, je mehr leere Felder sie haben. Weil 17 Zahlen nötig sind, um ein Sudoku eindeutig lösen zu können, muss eines mit 64 freien Feldern logischerweise das schwerste Sudoku ergeben, oder?

c't kompakt

• Es ist gar nicht so leicht festzustellen, wie schwer ein gegebenes Sudoku ist, die Anzahl leerer Felder bestimmt den Schwierigkeitsgrad jedenfalls nicht.
• Ein Bewertungsalgorithmus müsste möglichst viele der Strategien beherrschen, die auch ein Mensch beim Lösen anwendet.
• Je komplizierter der Lösungsweg, umso schwieriger ist das Sudoku.

Mehr zum Programmieren mit Python

• Wie man mit einem Python-Programm die Schwierigkeit von Sudokus bewertet, Teil 2
• Wie man mit einem Python-Programm die Schwierigkeit von Sudokus bewertet
• Mit Pydantic nur noch die richtigen Typen in Python verwenden
• Einen Sudoku-Generator in Python programmieren
• Jupyter-Alternative: Python-Apps schnell und einfach mit Marimo erstellen
• PySimpleGUI: komplexe Bedienoberflächen mit wenig Code erstellen
• Python 3.13: Mehr Performance ohne GIL
• Pakete tracken mit der Python-Bibliothek Silenium
• Editor Neovim mit den richtigen Plug-ins zur Python-IDE aufrüsten
• Programmieren lernen mit ChatGPT-o1
• Große DataFrames performant mit Polars bearbeiten

Das ist ein weitverbreiteter Irrglaube, denn die Schwierigkeit eines Sudokus hängt nicht von der Anzahl der gegebenen Zahlen ab. Es gibt leichte Sudokus mit 17 Zahlen und extrem schwere mit zum Beispiel 30 Zahlen. Um also ein Sudoku vernünftig einordnen zu können, muss ein Programm das Sudoku wie ein Mensch angehen und schauen, welche Strategien notwendig sind, um das Sudoku zu lösen.

Das war die Leseprobe unseres heise-Plus-Artikels "Wie man mit einem Python-Programm die Schwierigkeit von Sudokus bewertet". Mit einem heise-Plus-Abo können sie den ganzen Artikel lesen und anhören.