Sudoku-Löser mit Answer Set Programming (ASP)

Dieses Projekt implementiert einen Sudoku-Löser mithilfe von Answer Set Programming (ASP) und Clingo.

Projektstruktur

• sudoku.lp: Die ASP-Regeln für den Sudoku-Löser
• sudoku_instance.lp: Eine Beispiel-Sudoku-Instanz
• format_sudoku.py: Ein Python-Skript zur formatierten Ausgabe der Lösung

Installation

1. Installieren Sie Clingo:

   brew install clingo   # macOS

2. Stellen Sie sicher, dass Python 3 installiert ist.

Verwendung

Um das Sudoku zu lösen:

clingo sudoku.lp sudoku_instance.lp 0 | python3 format_sudoku.py

Wie es funktioniert

ASP-Regeln (sudoku.lp)

• Definiert die Regeln für ein gültiges Sudoku
• Stellt sicher, dass jede Zeile, Spalte und jeder 3x3-Block die Zahlen 1-9 enthält
• Verwendet Constraints, um ungültige Lösungen auszuschließen

Instanz-Datei (sudoku_instance.lp)

• Enthält die vorgegebenen Zahlen des zu lösenden Sudokus
• Format: initial(X,Y,V) wobei X,Y die Position und V der Wert ist

Formatierung (format_sudoku.py)

• Verarbeitet die Clingo-Ausgabe
• Stellt das Sudoku in einem übersichtlichen Raster dar

Beispiel-Ausgabe

┌───────┬───────┬───────┐
│ 7 6 5 │ 8 4 3 │ 2 1 9 │
│ 4 1 2 │ 6 9 7 │ 8 5 3 │
│ 9 3 8 │ 2 5 1 │ 7 6 4 │
├───────┼───────┼───────┤
│ 3 2 4 │ 1 8 6 │ 5 9 7 │
│ 1 8 9 │ 5 7 4 │ 6 3 2 │
│ 6 5 7 │ 9 3 2 │ 4 8 1 │
├───────┼───────┼───────┤
│ 8 7 1 │ 4 6 9 │ 3 2 5 │
│ 5 9 3 │ 7 2 8 │ 1 4 6 │
│ 2 4 6 │ 3 1 5 │ 9 7 8 │
└───────┴───────┴───────┘