sudoku solver

Sudoku-Löser

Ein einfacher Sudoku-Rätsellöser, geschrieben in PHP.

HINWEIS: Dieses Projekt befindet sich noch im Aufbau.

Installation

Führen Sie Folgendes im Stammverzeichnis des Projekts aus, um Sudoku-Solver zu installieren.

 composer install

Terminologie

 Square      One of the m x n values on the puzzle board
Row         Horizontal M squares
Column      Vertical N squares
Region      An m x n subset of squares
Group       M/N number of squares in a row (horizontally or vertically) 

Strategien zum Lösen von Rätseln

Die von diesem Löser verwendeten Strategien basieren auf den von Sudoku Dragon beschriebenen Strategien.

Die Strategien

Strategien sollten wiederholt angewendet werden, bis das Rätsel gelöst ist.

1. Nur Auswahlregel

   • Durchsuchen Sie jede Zeile, Spalte und Region nach einer einzelnen Auswahlmöglichkeit in der Gruppe.

2. Einzelmöglichkeitsregel

   • Durchsuchen Sie jede sich überschneidende Zeile und Spalte nach einer einzelnen Auswahlmöglichkeit in der Gruppe.

3. Nur quadratische Regel

   • Scannen Sie jede Zeile/Spalte mit zwei leeren Zellen.
   • Identifizieren Sie die beiden fehlenden Zahlen A und B.
   • Scannen Sie jede sich überschneidende Zeile, Spalte oder Region und versuchen Sie, Option A auszuschließen.
   • Wenn Option A für eine bestimmte Zelle eliminiert werden kann, füllen Sie Option B in dieser Zelle aus.
   • Füllen Sie Option A in der anderen leeren Zelle aus.

4. Zwei-aus-Drei-Regel

   • Scannen Sie von oben nach unten jeweils drei Zeilen oder Spalten nach einer bestimmten Zahl, beginnend bei 1.

5. Ausschlussregel für Untergruppen

   • TODO

6. Brutale Gewalt

   • Probieren Sie alle Optionen aus, bis eine Lösung gefunden ist :)

Ressourcen

• https://www.educative.io/edpresso/how-to-check-if-a-sudoku-board-is-valid
• https://puzzling.stackexchange.com/questions/158/how-many-minimal-clue-sudoku-puzzles-are-there
• https://www.technologyreview.com/s/426554/mathematicians-solve-minimum-sudoku-problem/