120 lines
4.3 KiB
Markdown
120 lines
4.3 KiB
Markdown
# Sudoku
|
|
|
|
Ein in Go geschriebener Sudoku-Löser, der Rätsel mit nachvollziehbaren,
|
|
menschlichen Lösungsstrategien bearbeiten soll. Neben dem gelösten Feld soll
|
|
langfristig auch der Lösungsweg mit Kandidaten, Änderungen und Markierungen
|
|
verfügbar sein.
|
|
|
|
> [!NOTE]
|
|
> Das Projekt befindet sich weiterhin in einer frühen Entwicklungsphase. Die
|
|
> Basis ist getestet und die Demo läuft, der menschliche Solver unterstützt aber
|
|
> bisher nur vier grundlegende Strategien.
|
|
|
|
## Voraussetzungen
|
|
|
|
- Go 1.25.10 oder neuer (siehe `go.mod`)
|
|
- keine externen Go-Abhängigkeiten
|
|
|
|
## Ausführen
|
|
|
|
Die Demo in `main.go` liest derzeit fest das dritte Rätsel aus
|
|
`data/sudoku-exchange-puzzle-bank/easy3.txt`, zeigt das Ausgangsfeld an und
|
|
startet anschließend den Solver:
|
|
|
|
```sh
|
|
go run .
|
|
```
|
|
|
|
Der Pfad und die Rätselauswahl sind momentan noch nicht über
|
|
Kommandozeilenargumente konfigurierbar.
|
|
|
|
## Entwicklung
|
|
|
|
Alle Pakete bauen und testen:
|
|
|
|
```sh
|
|
go test ./...
|
|
```
|
|
|
|
Code formatieren und statisch prüfen:
|
|
|
|
```sh
|
|
gofmt -w main.go field/*.go parser/*.go logic/*.go logic/strategies/*.go sudoku/*.go
|
|
go vet ./...
|
|
```
|
|
|
|
Die Pakete `field`, `parser`, `logic`, `logic/strategies` und `sudoku` besitzen
|
|
Unit- und Regressionstests. Neue Funktionalität sollte weiterhin mit paketnahen,
|
|
vorzugsweise tabellengesteuerten `*_test.go`-Tests ergänzt werden.
|
|
|
|
## Architektur
|
|
|
|
| Pfad | Aufgabe |
|
|
| --- | --- |
|
|
| `main.go` | Kleine Demo und Zusammenbau von Parser, Solver und Strategien |
|
|
| `field/` | Spielfeld, Zellen, Positionen, Zeilen, Spalten, Blöcke, Kandidaten und Änderungsprotokoll |
|
|
| `parser/` | Parser-Schnittstelle und Import des Sudoku-Exchange-Puzzle-Bank-Formats |
|
|
| `logic/` | Ablaufsteuerung des Solvers |
|
|
| `logic/strategies/` | Lösungsstrategien und gemeinsame Strategie-Basis |
|
|
| `sudoku/` | Fassade, die Parser, Feld und Solver zu einem Spiel verbindet |
|
|
| `data/` | Mitgelieferte Beispielrätsel samt eigener Herkunfts- und Lizenzhinweise |
|
|
| `todo.md` | Offene technische Ideen und Aufgaben |
|
|
| [`ROADMAP.md`](ROADMAP.md) | Priorisierter Fahrplan bis zum stabilen Solver |
|
|
|
|
Der Datenfluss der Demo ist:
|
|
|
|
```text
|
|
Puzzle-Bank-Datei -> parser.PuzzleBank -> field.Field
|
|
-> sudoku.Game -> logic.Solver
|
|
-> Strategien -> Änderungen am Feld
|
|
```
|
|
|
|
Eine Strategie implementiert `strategies.Strategy`. `SearchProgressableCells`
|
|
sammelt mögliche Änderungen, `ApplyAll` oder `ApplyNext` übernimmt sie in das
|
|
Feld. Wird eine Zahl gesetzt, entfernt das Feldmodell den entsprechenden
|
|
Kandidaten automatisch und ohne Duplikate aus der zugehörigen Zeile, Spalte und
|
|
dem Block.
|
|
|
|
Derzeit in `main.go` aktiv:
|
|
|
|
- Kandidaten eintragen (`Notes`)
|
|
- letzte fehlende Zahl eines Bereichs (`LastDigit`)
|
|
- einzelner Kandidat einer Zelle (`NakedSingle`)
|
|
- nur einmal vorkommender Kandidat eines Bereichs (`HiddenSingle`)
|
|
|
|
Weitere Strategietypen sind bereits als Gerüste angelegt, aber noch nicht
|
|
implementiert.
|
|
|
|
## Eingabedaten
|
|
|
|
`parser.PuzzleBank` erwartet das Format der
|
|
[Sudoku Exchange Puzzle Bank](data/sudoku-exchange-puzzle-bank/README.md): pro
|
|
Zeile einen 12-stelligen Hash, 81 Ziffern für das Rätsel und eine
|
|
Schwierigkeitsbewertung. Hash, Zeichenzahl, Ziffern, Rating und Ausgangsbelegung
|
|
werden geprüft. `0` steht für ein leeres Feld. LF und CRLF werden unterstützt,
|
|
leere Zeilen werden übersprungen.
|
|
|
|
Für einzelne Rätsel steht außerdem `parser.PuzzleString` zur Verfügung. Er
|
|
akzeptiert genau 81 Ziffern. Parser-Zugriffe liefern bei einem ungültigen Index
|
|
einen Fehler; bei mehreren Puzzle-Bank-Einträgen wird der Index explizit an
|
|
`sudoku.New` übergeben.
|
|
|
|
Die Datensätze unter `data/sudoku-exchange-puzzle-bank/` stehen unter der dort
|
|
beiliegenden separaten Lizenz.
|
|
|
|
## Bekannte Einschränkungen
|
|
|
|
- `logic.Solver.GetSolutionPath` liefert noch keinen Lösungsweg.
|
|
- Mehrere fortgeschrittene Strategien sind nur als leere Typen vorhanden.
|
|
- Der Solver besitzt noch kein gemeinsames Interface für menschliche,
|
|
Backtracking- und DLX-Implementierungen.
|
|
- Die Demo verwendet weiterhin einen fest kodierten Dateipfad und Puzzle-Index.
|
|
- Der alte öffentliche Bezeichner `InitStragies` bleibt vorerst als
|
|
Kompatibilitätsalias bestehen.
|
|
|
|
## Lizenz
|
|
|
|
Der Programmcode steht unter der [GNU General Public License v3.0](LICENSE).
|
|
Für die mitgelieferten Rätseldaten gelten die Hinweise im jeweiligen
|
|
Unterverzeichnis.
|