Christian V. - So 15.04.07 00:20
Titel: Class TSudoku

---

Sudoku

Hallo DF - Community

Mir war es heute(mittlerweile gestern :wink:) langweilig, deshalb habe ich beschlossen meinen Sudoku Algorithmus(Es sind sogar 2 :wink:) in ein Objekt zu verwandeln um sie damit leichter benutzbar zu machen und ihn hier zur Verfügung zu stellen.

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:
  
  
  Delphi-Quelltext

  1:	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 :D

Jakob Schöttl - So 15.04.07 12:42
Titel: Re: Class TSudoku

---

invulnerabilis hat folgendes geschrieben:

Werte ins Objekt laden. Dies geschieht per .Setvalue[0,1..81]:=Integer

ist das eine Array-Eigenschaft? Sieht so aus. In Eigenschaften sollten aber normalerweise nicht die Präfix Set oder Get stehen, weil die ja für die (Set-/Get-)Methoden dann davor gestellt werden. Und es sieht ja auch blöd aus, wenn man die Werte abfragt, und da dann steht i := obj.SetValue[0,8];

Das würde ich vllt noch ändern...

Christian V. - So 15.04.07 13:37

---

Tut mir leid, da habe ich wohl einen kelinen Fehler in meiner anleitung, bei GetValue braucht es 3 Varablen.

SetValue ruft eine Prozedur auf mit drei Variabeln. Die erste ist um das gewünschte Sudoku anzusprechen(Standard ist 0, da hier die erste lösung gespeichert wird, 1 wenn eine 2. Lösung vorhanden ist usw, dieses Feature wird aber noch nicht unterstützt.), der 2. Parameter dient dazu das gewünschte Feld zu bestimmen, der dritte um den gewünschten Wert zu setzen.

Du kannst damit keine Werte abfragen
Um einen Wert abzufragen rufst du die Funktion GetValue auf, die Analog zu SetValue funktioniert. Unterschied ist halt, dass du einen Rückgabewert begkommst, und deshalb auch nur 2 Parameter mitgeben musst.

Jakob Schöttl - So 15.04.07 13:59

---

Aber die Syntax ist mit Eckigen Klammern [ ] ?
Dann würde ich an deiner Stelle eine Array-Eigenschaft draus machen.
Obwohl ich jetzt ehrlich gesagt gar nicht weiß, ob es überhaupt mehrdimensionale Array-Eigenschaften gibt...

Christian V. - So 15.04.07 14:06

---

Ja sind natürlich normale () für Parameter. Ich war heute Morgen wohl ein bisschen müde. :D

Danke für dein Aufmerksames lesen der Anleitung. :wink:

Christian V. - So 15.04.07 20:50

---

Ich habe dann mal die Beschreibung meiner Funktionen ein wenig erweitert.

//Edit: rund 70 hits, erst 2 Downloads und erst ein Benutzer meldet sich weil ihm was an der Anleitung ins Auge gestochen ist? :(

Martok - So 15.04.07 23:01

---

Christian V. hat folgendes geschrieben:

//Edit: rund 70 hits, erst 2 Downloads und erst ein Benutzer meldet sich weil ihm was an der Anleitung ins Auge gestochen ist? :(

Tjahaha.... wer braucht schon einen Sudoku-Löser?

Das Problem ist ja, dass es davon tausende gibt...hättest du mich nicht 'gezwungen', hätte ich mir den auch nie angeguckt ;)

Wann hast du eigentlich deinen Nick geändert? In der SB steht noch invulnerabilis drin (*EinenBugVermut*)... :roll:

Christian S. - So 15.04.07 23:05

---

Martok hat folgendes geschrieben:

In der SB steht noch invulnerabilis drin (*EinenBugVermut*)... :roll:

Das ist "as desigend". Die Shoutbox braucht die aktuellen Daten nicht, weil die Anzeige eine sehr geringe Halbwertzeit hat. Daher werden die Daten angezeigt, die zum Zeitpunkt des Shouts aktuell waren. Die Daten werden in der SHoutbox-Tabelle gecached.

Christian V. - Mo 16.04.07 13:47

---

Zitat:

Tjahaha.... wer braucht schon einen Sudoku-Löser?

Ich weiss, das braucht fast niemand. Ich habe es geschrieben da jemand Hilfe mit sienem Sudoku-Programm hatte. :wink:.
Allerdings ist war das auch eine gute Übung für mich, da ich wieder mal seit längerem nichts programmiert habe.