Erweiterung des Sudoku Solvers ============================== **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. Neu in dieser Version: Das System wurde erweitert, um neben klassischen 9x9-Sudokus auch hexadezimale Sudokus (16x16) zu verarbeiten und zu lösen. 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 - die Erweiterbarkeit für verschiedene Sudoku-Formate (z. B. 16x16) **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 sowie die eingesetzten Datenformate und die Projektstruktur. Allgemeine Spielregeln und Logik von Sudoku ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Sudoku ist ein logikbasiertes Zahlenspiel, das traditionell 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. In der erweiterten Variante – dem hexadezimalen Sudoku – wird das Spielfeld auf ein 16×16-Gitter vergrößert. Hier müssen die Zeichen 0–9 und A–F so verteilt werden, dass jedes in Zeile, Spalte und in einem 4x4-Block nur einmal vorkommt. 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. ein Symbol 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 bzw. Zeichen ausprobieren (z. B. 1–9 oder 0–F) 3. Für jedes Symbol: Prüfen, ob es gültig ist 4. Bei gültigem Symbol: Rekursiv mit nächstem leeren Feld fortfahren 5. Wenn kein Symbol gültig ist: zurückspringen (*Backtracking*) Obwohl der Algorithmus auf den ersten Blick ineffizient erscheint, funktioniert er bei klassischen wie auch hexadezimalen Sudokus sehr effizient, 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 - ``gui_main.py``: Grafische Darstellung und visuelles Feedback mit Hilfe der Bibliothek Tkinter - ``solver.py``: Kernmodul mit Backtracking-Lösung für verschiedene Sudoku-Größen - ``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 GUI unterstützt sowohl 9x9- als auch 16x16-Sudokus. 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, um Sudokus systematisch zu lösen. Dabei handelt es sich um eine rekursive Methode, die jede Zelle des Rasters nacheinander durchläuft und alle möglichen Zeichen testet. Die Schritte im Detail: - Suche die nächste leere Zelle im Raster. - Füge ein Zeichen (abhängig vom Spielfeld: 1–9 oder 0–F) ein und prüfe: - Ist das Zeichen gültig? (Keine Duplikate in Zeile, Spalte oder Block) - Wenn ja: Weiter zur nächsten Zelle. - Wenn nicht: Backtracking → Zurück zur vorherigen Zelle und nächstes Zeichen ausprobieren. - Wenn das ganze Feld ausgefüllt ist: Lösung gefunden. Schrittweise Erklärung des Algorithmus ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Initialisierung ``````````````` Das Sudoku wird als 2D-Array übergeben: .. code-block:: python 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.Für hexadezimale Sudokus gilt: leere Zellen sind ebenfalls als 0 codiert, belegte Felder enthalten ganzzahlige Werte von 0–15 (intern). Wichtige Funktionen in ``solver.py`` ```````````````````````````````````` **1. find_empty(grid)** Sucht die nächste leere Zelle im Grid. **2. is_valid(grid, value, pos)** Prüft, ob ein Symbol an Position (i, j) erlaubt ist – dynamisch je nach Gittergröße. **3. solve(grid)** Rekursiver Algorithmus mit variabler Gittergröße (z. B. 9 oder 16). Modulübersicht ~~~~~~~~~~~~~~ **solver.py** - Enthält die zentrale ``solve(grid)``-Funktion mit Backtracking. - Unterstützt variable Gittergrößen (klassisch 9x9 und 16x16) - Validierungsfunktionen berücksichtigen Blockgrößen (3x3 bzw. 4x4) **io_utils.py** - Ein- und Ausgabe von Sudoku-Daten im JSON-Format - Unterstützt dynamische Prüfung von Gittergrößen **gui_main.py** - Visualisiert 9x9- und 16x16-Gitter - Interaktive Eingabe, Steuerung, Highlighting - Erweiterung: Hexadezimale Darstellung von 0–F **api_main.py** - REST-API mit Flask - Endpunkt ``/solve`` erkennt automatisch die Gittergröße (9 oder 16) Sudoku-Datenstruktur ~~~~~~~~~~~~~~~~~~~~ Ein Sudoku-Datensatz wird im JSON-Format gespeichert: .. code-block:: python { "id": "016x", "difficulty": "hard", "board": [[...], [...], ...], "solution": [[...], [...], ...], "createdAt": "2024-05-01T00:00:00Z" } .. list-table:: Sudoku JSON-Felder :header-rows: 1 :widths: 15 25 60 * - Feld - Typ - Beschreibung * - ``id`` - ``string`` - Eindeutige Kennung des Sudoku-Rätsels. * - ``difficulty`` - ``string`` *(optional)* - Schwierigkeitsgrad, z. B. ``"easy"``, ``"medium"``, ``"hard"`` * - ``board`` - ``int[n][n]`` - Sudoku-Gitter beliebiger Größe (z. B. 9×9, 16×16). Leere Felder = ``0``. * - ``solution`` - ``int[n][n]`` \| ``null`` - Lösung des Sudoku (keine Nullen erlaubt) oder ``null``. * - ``createdAt`` - ``string (ISO 8601)`` - Erstellungsdatum des Rätsels. **Streamlit-basierte Sudoku-Anwendung** ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Die im Projekt entwickelte Sudoku-Anwendungsanimation basiert auf zwei Streamlit-Skripten, die unterschiedliche Funktionalitäten zur Lösung und Visualisierung von Sudokus bereitstellen. Nachfolgend wird der Aufbau der beiden Skripte beschrieben. [#streamlit] Backtracking-Solver ``````````````````` Dieses Skript implementiert einen Backtracking-Algorithmus zur Lösung eines Sudoku-Rätsels. Es arbeitet schrittweise und prüft für jede Zelle alle möglichen Zahlen von 1 bis 9. Dabei wird nach jeder Zuweisung rekursiv weiterverzweigt, bis das Rätsel vollständig gelöst ist oder keine Lösung gefunden werden kann. Über die Methode ``solve_step_by_step()`` wird zusätzlich eine schrittweise Lösung ermöglicht, die es erlaubt, jeden Versuch visuell darzustellen. Die Anzahl der Lösungsversuche (``valid``-Aufrufe) wird gezählt und am Ende der Lösung ausgegeben. Dies bietet eine nützliche Kennzahl zur Einschätzung der Schwierigkeit eines Rätsels, die später für die Implementierung einer Schwierigkeitsbewertung herangezogen wird. Interaktive GUI mit Animation ````````````````````````````` Dieses Skript bildet die zentrale Benutzeroberfläche zur interaktiven Eingabe und Visualisierung eines Sudoku-Rätsels. Nutzer können entweder ein Beispielrätsel laden oder manuell ein Rätsel eingeben. Über die Animation kann der Lösungsprozess Schritt für Schritt verfolgt werden, wobei das aktuelle Feld hervorgehoben wird. Technisch wird ein HTML-basiertes Sudoku-Raster erzeugt, das zur Laufzeit aktualisiert wird. Dabei können Nutzer die Animationsgeschwindigkeit variieren, den Lösungsprozess pausieren oder zurücksetzen. Zusätzlich wird die Anzahl der ``valid``-Aufrufe und die geschätzte Schwierigkeit angezeigt, um die Effizienz des Lösungsalgorithmus nachvollziehbar darzustellen. Die Implementierung der beiden Skripte erfolgt vollständig in Streamlit, was eine einfache Integration von Interaktionen, Animationen und Benutzereingaben ermöglicht. Durch die Trennung in Solver- und GUI-Skript bleibt die Struktur übersichtlich und modular erweiterbar. Zum Testen und Ausprobieren ist die Anwendung über Streamlit Cloud unter der folgenden URL öffentlich zugänglich: `Sudoku Solver Showcase `_. Diese Hosting-Lösung ermöglicht es, die App ohne lokale Installation direkt im Browser auszuführen und so die interaktive Funktionalität selbst zu erleben. Ein ähnlicher Solver ist unter [#solver]_ zu finden. **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 – nun auch bei hexadezimaler Spielfeldgröße. 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. Die Erweiterung auf 16x16-Sudokus erforderte nur moderate Anpassungen, konnte aber nahtlos integriert werden. 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. .. [#streamlit] https://streamlit.io .. [#solver] https://sodokusolver.com/16x16-sudoku-solver.html