Sudoku

Der Lösungsalgorithmus

Das Lösen eines Sudokus ist relativ einfach. Zunächst überlegen wir uns, welche Rückgabewerte die Solve-Funktion haben soll. Sie muss melden, wenn es keine Lösung gibt, eine Lösung oder mehr, also ein Zahlenwert zwischen 0 und 2. Damit der Algorithmus relativ schnell ist, prüfen wir, ob es mehr eingetragene Zahlen in der linken oberen oder rechten unteren Ecke gibt. Im Folgenden, die einzelnen Schritte des Algorithmus:

  1. Freies Feld suchen (For-Schleife horizontal und vertikal, Abbruch bei freiem Feld)
  2. Mögliche Zahlen für dieses Feld herausfinden (Überprüfung von Spalte, Zeile und 3er-Quadrat). Bei 0 möglichen Zahlen Abbruch (falsche Lösung).
  3. Für alle möglichen Zahlen die Prozedur rekursiv aufrufen mit entsprechend ausgefülltem Feld.
  4. Wenn kein Feld mehr frei ist, Lösung auf Richtigkeit überprüfen und Lösungsanzahl um 1 erhöhen.
  5. Wenn Lösungsanzahl größer gleich 2 ist, Abbruch.

Für ausführlichere Informationen, schauen Sie sich den beigelegten Quellcode an.

Zurück zum Erstellungsalgorithmus | Zum Tutorial-Anfang



Kontakt - Impressum - Datenschutz
Alle Grafiken, Bilder, Texte und Dokumente sind urheberrechtlich geschützt und dürfen nicht ohne schriftliche Genehmigung verwendet werden. Copyright © 1998-2008 by Martin Walter.
Alle Rechte vorbehalten. all rights reserved.