Sudoku Solver

Einleitung

Mit der zunehmenden Leistungsfähigkeit moderner KI-Modelle stellt sich nicht nur die Frage, wie kreativ oder vielseitig sie sind, sondern auch, inwieweit sie bei der Lösung klassischer algorithmischer Probleme unterstützen können.

Eines dieser Probleme ist das Sudoku. Es ist ein logikbasiertes Zahlenspiel, das sich gut eignet, um Programmierkonzepte wie Backtracking, Validierung und GUI-Integration zu demonstrieren.

In unserem zweiten Experiment entwickeln wir einen vollständigen Sudoku-Solver. Ziel ist es, ein Programm zu erstellen, das beliebige Sudoku-Rätsel aus einer JSON-Datei einliest, auf Korrektheit prüft und, sofern lösbar, automatisch auf grafischer Oberfläche darstellt und löst.

Dabei liegt der Fokus auf mehreren Aspekten:

  • Dem Einlesen und Validieren der Spieldaten

  • Der Implementierung eines Lösungsalgorithmus

  • Die Einbindung in eine grafische Benutzeroberfläche

Zusätzlich wollen wir untersuchen, wie man Programmteile so strukturiert, dass sie leicht testbar und wiederverwendbar sind.

Zielsetzung

Ziel dieses Versuchs ist es, ein modulares und robustes System zur Lösung von Sudokus zu entwickeln. Dabei sollen sowohl die technische Umsetzung als auch die Benutzerfreundlichkeit berücksichtigt werden.

Der Aufbau des Projekts erfolgt in mehreren Schritten, von der Datenverarbeitung über die Spiellogik bis hin zur visuellen Darstellung.

Besonderes Augenmerk legen wir auf:

  • die Validierung der Eingabedaten

  • die Effizienz des Lösungsalgorithmus

  • die klare Trennung der Funktionsbereiche innerhalb des Programmcodes

Grundlagen

In diesem Kapitel werden die wichtigsten Konzepte und Technologien erläutert, die dem Aufbau unseres Sudoku-Solvers zugrunde liegen. Neben den logischen Grundlagen des Spiels Sudoku werden die Funktionsweise gängiger Lösungsalgorithmen dargestellt. Zudem beschreiben wir die im Projekt verwendeten Softwaretechnologien wie Python, die grafische Benutzeroberfläche mit Tkinter [#tkinter]_ sowie die eingesetzten Datenformate und die Projektstruktur.

Allgemeine Spielregeln und Logik von Sudoku

Sudoku ist ein logikbasiertes Zahlenspiel, das auf einem 9×9-Gitter basiert, das wiederum in neun 3×3-Blöcke unterteilt ist. Ziel des Spiels ist es, das Gitter so mit den Ziffern 1 bis 9 zu füllen, dass jede Zahl genau einmal in jeder Zeile, jeder Spalte und in jedem der neun Blöcke vorkommt.

Dabei sind zu Beginn bereits einige Zahlen vorgegeben, die sogenannte Startkonfiguration.

Das Lösen eines Sudokus erfordert logisches Denken und manchmal auch strategisches Raten. Für Computerprogramme bedeutet das: Die Lösung muss unter Berücksichtigung klarer Konsistenzregeln gefunden werden. Ein ungültiger Spielstand entsteht, wenn z. B. eine Zahl doppelt in einer Zeile oder einem Block vorkommt. Das muss frühzeitig erkannt und vermieden werden.

Lösungsstrategien und Algorithmen

Für das automatisierte Lösen von Sudokus gibt es verschiedene Ansätze. Die bekannteste Methode ist Backtracking, ein rekursiver Algorithmus, der systematisch alle möglichen Zahlenkombinationen ausprobiert und bei ungültigen Zuständen zurückspringt. Dieser Algorithmus wird auch in unserem Projekt verwendet.

Vereinfacht gesagt:

  1. Leeres Feld finden

  2. Alle möglichen Zahlen (1–9) ausprobieren

  3. Für jede Zahl: Prüfen, ob sie gültig ist (nicht doppelt in Zeile, Spalte, Block)

  4. Bei gültiger Zahl: Rekursiv mit nächstem leeren Feld fortfahren

  5. Wenn keine Zahl gültig ist: zurückspringen (Backtracking)

Obwohl der Algorithmus auf den ersten Blick ineffizient erscheint, funktioniert er bei klassischen Sudokus sehr schnell, da viele ungültige Kombinationen frühzeitig ausgeschlossen werden können.

Technologischer Aufbau des Projekts

Das Projekt wurde vollständig in Python umgesetzt und ist in mehrere Module unterteilt:

  • main.py: Einstiegspunkt des Programms, übernimmt den Ablauf

  • io_utils.py: Ein- und Ausgabe von Sudoku-Daten im JSON-Format inkl. Validierung RFC 8259 [#rfc8259]_

  • gui_main.py: Grafische Darstellung und visuelles Feedback mit Hilfe der Bibliothek Tkinter

  • hints.py, difficulty.py: Zusatzfunktionen für Hinweise und Schwierigkeitsanalyse

Die Sudokus werden in JSON-Dateien gespeichert, die neben dem Spielbrett (board) auch die Lösung (solution) enthalten. Diese Dateien dienen sowohl als Eingabe für das Programm als auch als Testbasis zur Überprüfung der korrekten Lösung.

Verwendung von Tkinter für die grafische Benutzeroberfläche

Zur Darstellung des Spielfelds wurde die in Python integrierte GUI-Bibliothek Tkinter verwendet. Damit lassen sich einfache grafische Elemente wie Buttons, Textfelder und Rasterlayouts effizient umsetzen.

In unserem Projekt wird das Sudoku-Gitter als interaktive Oberfläche dargestellt, die es erlaubt, den Lösungsprozess visuell zu verfolgen. Die Umsetzung der GUI war ein wesentlicher Teil des Projekts, da sie nicht nur die Nutzbarkeit erhöht, sondern auch beim Debugging und Testen des Algorithmus unterstützt.

Projektstruktur und Modularität

Das Sudoku-Solver-Projekt ist modular aufgebaut, sodass Einleseroutine, Spiellogik, GUI und Tests klar voneinander getrennt sind. Dies erleichtert nicht nur die Wartung und Weiterentwicklung, sondern ermöglicht auch die Wiederverwendung einzelner Module in anderen Kontexten, z. B. zur Integration in eine App oder für größere KI-Vergleiche mit automatischer Bewertung.

Versuchsdurchführung

Der Sudoku-Solver verwendet einen Backtracking-Algorithmus [#sudoku_py]_ , um Sudokus systematisch zu lösen. Dabei handelt es sich um eine rekursive Methode, die jede Zelle des 9x9-Rasters nacheinander durchläuft und alle möglichen Zahlen (1–9) testet.

Die Schritte im Detail:

  • Suche die nächste leere Zelle im Raster.

  • Füge eine Zahl (1–9) ein und prüfe: - Ist die Zahl gültig? (Keine Duplikate in Zeile, Spalte oder 3x3-Block)

  • Wenn ja: Weiter zur nächsten Zelle.

  • Wenn nicht: Backtracking → Zurück zur vorherigen Zelle und nächste Zahl ausprobieren.

  • Wenn das ganze Feld ausgefüllt ist: Lösung gefunden.

Überblick: Was ist Backtracking?

Backtracking ist eine rekursive Problemlösungsmethode, bei der mögliche Lösungen durch sukzessive Erweiterung einer Teillösung konstruiert und bei Ungültigkeit wieder zurückgenommen (zurückverfolgt) werden.

Beim Sudoku bedeutet das:

  • Jede leere Zelle wird mit möglichen Zahlen (1–9) ausprobiert.

  • Wird eine Regel verletzt, wird der Wert wieder gelöscht und die nächste Zahl ausprobiert.

  • Ist das Feld korrekt ausgefüllt, ist die Lösung gefunden.

Schrittweise Erklärung des Algorithmus

Initialisierung

Das Sudoku wird als 2D-Array übergeben:

grid = [
 [5, 3, 0, 0, 7, 0, 0, 0, 0],
 [6, 0, 0, 1, 9, 5, 0, 0, 0],
 ...
]

Leere Zellen sind mit 0 gekennzeichnet.

Wichtige Funktionen in solver.py

1. find_empty(grid) Sucht die nächste leere Zelle im Grid:

for i in range(9):
    for j in range(9):
        if grid[i][j] == 0:
            return (i, j)  # Koordinaten der leeren Zelle

2. is_valid(grid, num, pos) Prüft, ob eine bestimmte Zahl an Position (i, j) erlaubt ist:

  • Ist num bereits in der gleichen Zeile?

  • Ist num bereits in der gleichen Spalte?

  • Ist num bereits im gleichen 3x3-Block?

def is_valid(grid, num, pos):
   # Zeile prüfen
   for i in range(9):
       if grid[pos[0]][i] == num and pos[1] != i:
           return False
   # Spalte prüfen
   ...
   # 3x3 Block prüfen
   ...
   return True

3. solve(grid) Der rekursive Algorithmus:

def solve(grid):
  find = find_empty(grid)
  if not find:
      return True  # Gelöst

  row, col = find

  for num in range(1, 10):
      if is_valid(grid, num, (row, col)):
          grid[row][col] = num

          if solve(grid):
              return True

          grid[row][col] = 0  # Backtrack

  return False

Ablauf:

  • Leere Zelle finden

  • Gültige Zahl einsetzen

  • Rekursiv weitermachen

  • Falls Fehler → letzte Zelle zurücksetzen (Backtrack)

  • Endzustand = vollständig gelöstes Grid

Modulübersicht

solver.py

  • Enthält die zentrale solve(grid)-Funktion mit Backtracking.

  • Validierungsfunktionen: - is_valid(grid, num, pos) prüft, ob eine Zahl in eine Position eingesetzt werden darf.

  • Unterstützt vollständig oder teilweise befüllte Sudoku-Grids (als 2D-Listen).

difficulty.py und hints.py

  • difficulty.py: Bewertet die Schwierigkeit eines Sudokus anhand der Anzahl leerer Felder oder der benötigten Backtracking-Tiefe.

  • hints.py: Generiert logische Hinweise für den nächsten möglichen Schritt → kann z. B. in Lernsoftware verwendet werden.

io_utils.py

  • Ein- und Ausgabe von Sudoku-Daten im JSON-Format.

  • Beispiel: load_grid("001.json") lädt ein Sudoku aus der Datei.

gui_main.py

  • Realisiert eine visuelle Eingabe- und Ausgabemaske mit pygame.

  • Funktionen: - Eingabe per Tastatur - Start des Lösungsprozesses per Mausklick - Visualisierung des Lösungsverlaufs (optional animiert) - Fehler-Highlighting bei ungültigen Eingaben

api_main.py

  • Stellt eine REST-API mit Flask zur Verfügung. [#flask]

  • Endpunkt: /solve - Annahme eines JSON-Rätsels via POST - Rückgabe des gelösten Sudoku ebenfalls als JSON

  • Ermöglicht einfache Integration in Web-Anwendungen oder mobile Apps

Sudoku-Datenstruktur

Ein Sudoku-Datensatz wird im JSON-Format gespeichert und enthält folgende Felder:

{
  "id": "001",
  "difficulty": "easy",
  "board": [[...], [...], ...],
  "solution": [[...], [...], ...],
  "createdAt": "2023-08-01T00:00:00Z"
}
Tab. 1 Sudoku JSON-Felder

Feld

Typ

Beschreibung

id

string

Eindeutige Kennung des Sudoku-Rätsels.

difficulty

string (optional)

Schwierigkeitsgrad, z. B. "easy", "medium", "hard"

board

int[9][9]

9×9 Sudoku-Gitter. Leere Felder = 0.

solution

int[9][9] | null

Lösung des Sudoku (keine Nullen erlaubt) oder null.

createdAt

string (ISO 8601)

Erstellungsdatum des Rätsels.

Funktionen in io_utils.py

import_sudoku(filepath: str) -> list

Lädt ein Sudoku aus einer .json-Datei, validiert die Daten und gibt das Sudoku-Board zurück.

  • Parameter: filepath (str) – Pfad zur Datei

  • Rückgabe: list[list[int]] – Sudoku-Board (0–9)

  • Fehler: FileNotFoundError, ValueError bei ungültiger Struktur

export_sudoku(filepath: str, sudoku_data: dict)

Speichert Sudoku-Daten im JSON-Format.

validate_sudoku_data(data: dict)

Validiert die Struktur des übergebenen Datensatzes: - Pflichtfelder: id, board, solution - board muss 9×9 mit Werten 0–9 - solution muss (wenn vorhanden) 9×9 mit Werten 1–9 - Fehler: ValueError bei falscher Struktur

Beispiel:

from sudoku_utils import import_sudoku

  try:
      board = import_sudoku("sudoku_001.json")
      print("Sudoku erfolgreich geladen!")
  except Exception as e:
      print(f"Fehler: {e}")

Fazit

Mit dem Sudoku-Solver wurde ein vollständiges, modular aufgebautes System zur Lösung logikbasierter Zahlenrätsel realisiert. Das Projekt vereint algorithmische Problemlösung, Datenvalidierung, benutzerfreundliche Visualisierung und flexible I/O-Mechanismen in einer durchdachten Softwarearchitektur.

Durch den Einsatz eines rekursiven Backtracking-Algorithmus konnten Sudokus effizient gelöst werden – selbst bei höheren Schwierigkeitsgraden. Die klare Trennung von Spiellogik, Datenverarbeitung und Benutzeroberfläche förderte nicht nur die Wartbarkeit, sondern ermöglichte auch gezielte Tests und Wiederverwendung einzelner Komponenten.

Besonders hervorzuheben ist die Verwendung von standardisierten Datenformaten wie JSON sowie der Aufbau einer REST-API, die das System auch für webbasierte Anwendungen oder externe Integrationen nutzbar macht.

Der Sudoku-Solver ist damit nicht nur eine praktische Anwendung, sondern auch ein gutes Beispiel für interdisziplinäre Softwareentwicklung zwischen Algorithmik, Usability und Datenverarbeitung.

[#tkinter] https://docs.python.org/3/library/tkinter.html [#rfc8259] https://datatracker.ietf.org/doc/html/rfc8259 [#sudoku_py] https://aurbano.github.io/sudoku_py/ [#flask] https://flask.palletsprojects.com/