Sudoku

Hall DP - Community

Ich möchte hier meinen Sudoku-Lösungsalgorithmus(Es sind sogar 2) vorstellen und zur Nutzung anbieten.(Mit einem Hinweis auf mich selbstverständlich)
Das ganze habe ich in einem Objekt gekapselt um es einfach ansprechbar zu machen.

Die bisherigen Funktionen:

Heuristik
Löst das Sudoku mit Hilfe einer programmierten Logik. Diese Löst schwere Sudoku's von "Die Zeit" in Sekundenbruchteilen.
Backtracking
Falls die Heuristik mal nicht weiter weiss, gibt es noch die Backtracking Methode. Diese Löst jedes Sudoku, bisher aber nur die "erste" Lösung. Diese Methode ist langsamer, das merkt man aber nicht. Selbst ein Sudoku ohne! vorgegebene Zahlen wird in einem Sekundenbruchteil gelöst.

Funktion zum Berechnen weiterer Lösungen folgt.

Anleitung:

1. Unit USudoku einbinden über uses
2. Variable vom Typ TSudoku erstellen.
3. .create methode aufrufen
4. Werte ins Objekt laden. Dies geschieht per .Setvalue(0,1..81,val) //Wert 0 für leeres Feld!
5. Gewünschte Lösungsfunktion starten .SolveLogic / .SolveAdvanced
6. Auf Fehler überprüfen per .ErrorNumber 0=Kein Fehler, 1=Regelverletzung
7. Falls 1, dann steht Feldnummer die den Fehler verursach hat in ind .ErrorValue
8. Mit der Funktion GetValue(0,1..81) kann man einen Wert abfragen.
9. .free

Anmerkungen
Die Funktionen zum Setzen/Abrufen der Werte brauchen als ersten Paramter eine 0, damit auf die erste lösung zugegriffen wird. Ich bin gerade debei eine Funktion hinzuzufügen, die noch weitere Möglichkeiten berechnen kann, und diese in einem anderen Array abspeichert.

Es ist egal ob die Werte Zeile um Zeile, oder Spalte um Spalte ins Objekt geschrieben werden, solange sie in der gleichen Reihenfolge wieder ausgelesen werden.

Funktionsweise

• Gemeinsames:
  
• Datenstruktur:
  Ich arbeite mit einem Array Impossible(Boolean) mit 4 Dimensionen, die erste Dimension ist um zwischen den
  verschiedneen Lösungen zu unterscheiden, die 2. ist die X Koordinate, 3. Dimension ist die Y-Koordinate und die 4. Dimension die Zahl Für die die Möglichkeit abgespeichert werden soll.
  Beispiel:
  impossible[0,1,8,3]:=false; Setze Möglichkeit für Ziffer 3 in Feld mit Koordinaten 1/8 auf möglich.
  
  Analog zu Impossible existiert ein Array namens owner(Integer). Darin wird das Feld eingetragen, das die Möglichkeiten für eine Ziffer setzt. So kann ich sichergehen das beim Rückgängigmachen der Möglichkeiten keine falschen Möglichkeiten gelöscht werden, sonst würde es falsche Lösungen geben.
  Der Array Quadrant(Boolean) hat auch vier Dimensionen analog zu Impossible, hat aber für X und Y nur [1..3] zur verfügung, es gibt ja auch nur 3*3 Quadranten. Dieser Array dient dazu, sich zu merken ob die Zahl schon im Quadranten verwendet wurde.(Dieser Überprüfung wird nur in der Heuristik durchgeführt, beim Backtracking ist sie unnötig).
  Es existiert ein Array namens Sudoku(Integer). Dimensionen: 2, die Erste für die verschiedenen Lösungen, und die Zweite für den index[1..81]. Darin wird der Wert für ein Feld gespeichert.
  In der Variable Count wird die Zahl der ausgefüllten Felder gespeichert.
  Sie kann über die Methode .GetCount ausgelesen werden.
  
  Zu Begin werden die Möglichkeiten für die bereits eingetragenen Felder Gesetzt, und count erhöht. Zudem wird auch der FeldIndex aus der Menge der editierbaren Felder used(:use=1..81) entfernt. Diese menge wird beim Backtracking verwendet. Später datu mehr.
• Heuristik(.SolveLogic):
  In der Heuristik wird Hauptsächlich mit For Schleifen und If's gearbeitet.
  Um den Ganzen Block hat es eine While-Schleife, die solange wiederholt wird, bis die Variable found(boolean) auf false ist. Immer wenn eine gültige Zahl gefunden wird, wird sie auf true gesetzt. Diese wird zu Beginn der Schleife immer wieder mit false Initialisiert. Die Schleife Prüft der Reihe nach die Zahlen 1-9 für jeden Quadranten. Falls eine Zahl noch vorkommen kann, wird geprüft, ob sie nur noch in einem Feld innerhalb des Quadranten möglich ist. Falls die Möglichkeiten auf 2 ansteigen, wird aus der Schleife hinausgesprungen, um zur Überprüfung des nächsten Quadranten zu gelangen. Wird eine Zahl gefunden die diese Bedingungen erfüllt, so werden für diese die Möglichkeiten aktualisiert. Falls keine Zahl mehr gefunden werden kann (das heisst found ist am Ende der While-Schleife false), kommt die nächste Überprüfungsmethode zum einsatz. Diese prüft ob nur noch eine Zahl in einer Reihe vorkommen kann, bzw fehlt. Falls eine gefunden wird, wird wieder von vorne begonnen.
  
  Mit dieser Methode konnte ich schwere Sudokus von der Zeitung "Die Zeit" lösen.
• Backtracking(.SoleAdvanced):
  Der Backtracking Algorithmus ist langsamer als die Heuristik, und kommt zum Einsatz, falls die Heuristik nicht mehr weiterkommt.(Muss allerdings man allerdings selbst aufrufen(.SolveAdvanced).
  Zu beginn werden auch die Möglichkeiten der bereits gesetzen Felder gesetzt. Der Menge used[1..81] wird der Indexwert des Feldes abgezogen, das schon Standardmässig belegt ist.
  In diesem Algorithmus wird nur geprüft, ob ein Wer vorkommen kann, nicht auf Eindeutigkeit wie bei der Heuristik. Zu beginn ist der Index i auf 1 gesetzt. Es wird geprüft ob i in used enthalten ist, falls ja wird eine Fallunterscheidung gemacht:
  • Falls das zu bearbeitende Feld noch Leer ist, werden alle Werte von 1-9 geprüft, ob sie noch eingesetzt werden können. Dann werden die Möglichkeiten gesetzt, die dieses Feld auslöst. Count und i werden um eins erhöht. Wird kein passender Wert gefunden, so wird I dekrementiert, und bei der nächsten Wiederhohlung kommt der zweite Fall zur anwendung.
  • Falls das Feld nicht mehr leer ist, bedeutet das, dass der Wert nicht stimmen kann. Die Möglichkeiten, die dieses Feld gesetzt hat, werden gelöscht(dies ist der Punk, wo der Array owner ins spiel kommt). dann wird geprüft ob ein Wert im Bereich((Aktuellerwert+1) bis 9) noch eingesetzt werden kann. Falls ja, werden die Möglichkeiten aktualisiert, count und i inkrementiert. Falls kein weiterer Wert gefunden wird, wird das Feld auf 0 gesetzt, count und i werden dekrementiert.
• Zusätzliche Infos zum Backtracking:
  Immer wenn ein Wert gefunden wird der passt, wird found auf true gesetzt. Falls ein schritt zurückgegangen werden muss, wird found auf false gesetzt. Wenn i nicht in der Menge vorkommt, wird i dadurch nochmals dekrementiert(bei false) oder eben inkrementiert(bei true) wird.
  
  Der Ganze Baktracking Algo befindet sich in einer Schleife, die ausgeführt wird, solange count nicht 81 ist.

Ich freue mich auf Feedback.

Nicht hauen wegen GOTO's, das ist schneller