Sudoku Logik

[hans ditter]

Ah ja... hatte ich schon fast befürchtet, dass das in die Richtung geht.... -.-

Kannst du mir was zu Backtracking erzählen? Backtracking = zurück suchen ?? Ich würd mir drunter vorstellen, dass man alle Schritte irgendwie speichert und dann rückgehen schaut, ob das ganze funktionieren kann. Aber ich hab definitiv keine Ahnung wie das gehen soll!!

lg, hans ditter

[JasonDX]

Zitat von hans ditter:

Kannst du mir was zu Backtracking erzählen? Backtracking = zurück suchen ?? Ich würd mir drunter vorstellen, dass man alle Schritte irgendwie speichert und dann rückgehen schaut, ob das ganze funktionieren kann.

Grob beschrieben ist das Backtracking. Man trifft Entscheidungen, und wenn man an einen Widerspruch/Fehler gerät, ändert man eine (normalerweise die letzte) Entscheidung und probiert dann weiter. Wikipedia hat auch nen eigenen Eintrag dazu.
Auf Sudoku angewand würde das ca. so aussehn (der Einfachheit halber rekursiv beschrieben):

Code:

SetzeFeld(i)
  Wenn i > Size*Size
    return true; //Abbruchbedingung
  GültigeEntscheidungen = {1..Size}
  solange Anzahl(GültigeEntscheidungen) > 0
    Wähle zufällige, gültige Entscheidung x //(z.B. x=3, d.h. ins i-te Feld wird eine 3 geschrieben)
    Wenn EntscheidungGültig(i, x) //x ist auf dem i-ten Feld gültig
      Setze(i, x)
      Wenn SetzeFeld(i+1) //Probieren, das restliche Sudoku zu füllen
        return true;      //Sudoku konnte gefüllt werden, also Funktion "erfolgreich" beenden
    Entferne x aus GültigeEntscheidungen //Weil x keine gültige Entscheidung war
  return false //keine Gültige Entscheidung gefunden, also muss in den vorherigen Feldern was geändert werden

Das ist dann eine sehr einfache Implementierung von Backtracking. Dadurch, dass man Rekursion anwendet, muss man auch nicht ehemalige Entscheidungen speichern, bzw. der Compiler&Stack erledigen das für einen.
Wie schnell dieser Code dann läuft hängt sehr davon ab, wie man die Gültigkeit einer Entscheidung überprüft. Diese muss natürlich false zurückgeben, (genau dann) wenn die Zahl nicht gültig ist. Hier ist aber bspw. auch bereits viel Optimierungs-Potential drin. Im weiter oben genannten Beispiel könnte die Funktion auch bereits erkennen, dass die 1 im 7. Feld nicht gültig ist. Hierfür können dann die verschiedensten Methoden zum Einsatz kommen.

greetz
Mike

[hans ditter]

Danke Mike,

deine Beschreibung hört sich erstmal reichlich wirr an, werd mich aber mal ransetzten und probieren die umzusetzten. Ich poste dann mein Endergebnis hier, wenn man da dann nochmal rüberschauen könnte, wäre das klasse!

LG, hans ditter

[hans ditter]

Hi Mike,

hab mich mal mit deinem Beitrag beschäftigt. Da sind allerdings 2 Fragen aufgetaucht:
1.) Wenn i > Size * Size --> wofür braucht man das? was bedeutet es?
2.) Gueltige Entscheidung = {0..Size} --> was ist das? ein Array? wie ist es aufgebaut?

Zu 2.: Ich dachte schonmal an ein Array of Array, dass man dann ein 4x4 Array z.B. anlegt, für jedes einzelne Feld im Sudoku und in dem Arrayfeld dann ein weiters Array oder Record speichert, für alle zulässigen Zahlen dieses Feldes. Wäre das praktikabel und sinnvoll?

LG, hans ditter

P.S.: Mein Quelltext zu deinem Post soll heute noch folgen, also vlt heute abend nochmal reinschauen... würd mich freuen!

[JasonDX]

Zitat von hans ditter:

1.) Wenn i > Size * Size --> wofür braucht man das? was bedeutet es?

Das ist die Abbruchbedingung. i zählt mit, das wievielte Feld gerade gefüllt wird. Wenn i dann größer als Size*Size ist, dann hat man bereits alle Felder gefüllt.

Zitat von hans ditter:

2.) Gueltige Entscheidung = {0..Size} --> was ist das? ein Array? wie ist es aufgebaut?

Das ist eine Liste oder ein Array (in dem Fall eigentlich egal), und enthält, welche Entscheidungen gültig sind, bzw. noch nicht durchprobiert wurden.

Zitat von hans ditter:

Zu 2.: Ich dachte schonmal an ein Array of Array, dass man dann ein 4x4 Array z.B. anlegt, für jedes einzelne Feld im Sudoku und in dem Arrayfeld dann ein weiters Array oder Record speichert, für alle zulässigen Zahlen dieses Feldes. Wäre das praktikabel und sinnvoll?

Durchaus - allerdings muss man damit aufpassen, wenn man zu viel damit optimiert. Nehmen wir an der Algorithmus trifft eine Entscheidung, und deshalb ist eine Zahl in einem späteren Feld nicht mehr gültig. Die Entscheidung wird aber rückgängig gemacht - dann muss diese Zahl in dem späteren Feld wieder zu den gültigen Zahlen hinzugefügt werden. Entweder indem alle gültigen Zahlen erneut berechnet werden, oder indem man speichert, wegen welcher Entscheidung eine Zahl als ungültig markiert wurde.
Die beschriebene rekursive Methode vereinfacht diesen Prozess. Man kann dort, bevor man beginnt verschiedene Entscheidungen durchzuprobieren, offensichtlich ungültige Entscheidungen entfernen. Ums Zurücksetzen von Entscheidungen muss man sich dann nicht kümmern - das wird durch die Rekursion direkt erledigt.

greetz
Mike

[hans ditter]

Hi,
danke für deine Antwort.

Ich sehe jetzt schon deutlich klarer. Aber eine Sache ist noch nicht ganz "aus dem Nebel aufgetaucht"...
Wird versucht, in SetzeFeld das gesamte Sudoku zu füllen? Es sieht für mich gerade so aus, dass immer wieder SetzeFeld aufgerufen wird, wenn eine Entscheidung gültig war. Das würde dann aber bedeuten, dass ich am Anfang nur einmal sagen muss, dass er für Feld 1 SetzeFeld aufrufen soll, weil sich der Rest dann eh alleine erledigt... hab ich das richitg verstanden?

So, dann mach ich mich wohl mal an den Quelltext ran...

LG, hans ditter

[hans ditter]

Delphi-Quellcode:

function SetDigit(X,Y,Size: integer) : boolean
var ValidDigit: [0..Size] as array of integer;
    nr: integer;
begin
   if (X > Size) OR (Y > Size) then
      Result:=true;
   while ValidDigit > 0 do
   begin
      nr:=random(length(ValidDigit))
      if DigitIsOk(X,Y,nr) then
      begin
         StringGrid1.Cells[X,Y]:=nr;
         if SetDigit(X+1,Y,Size) then
            Result:=True;
      end
      else
         Delete(nr);
   end
   else
      Result:=false;
end

so, nun nochmal einige Anmerkungen:
- ich hab diesen Code noch nicht selbst getestet
- ... dass hab ich noch nicht, weil ich noch ein paar Schwierigkeiten hab
- ... diese liegen vor allem im Umgang mit dem Array, was ich hier erstellen wollte
- ... und als letztes noch in der Frage, ob es für eine while-Schleife auch einen else-Zweig gibt.

angenehme Nachtruhe,
hans ditter

[JasonDX]

Zitat von hans ditter:

Hi,
Wird versucht, in SetzeFeld das gesamte Sudoku zu füllen? Es sieht für mich gerade so aus, dass immer wieder SetzeFeld aufgerufen wird, wenn eine Entscheidung gültig war. Das würde dann aber bedeuten, dass ich am Anfang nur einmal sagen muss, dass er für Feld 1 SetzeFeld aufrufen soll, weil sich der Rest dann eh alleine erledigt... hab ich das richitg verstanden?

Ja Du rufst SetzeFeld für das 1. Feld auf, und das füllt dann durch die rekursiven Aufrufe das gesamte Sudoku.

Hier mal die Fehler die mir beim groben Überfliegen aufgefallen sind:

Zitat von hans ditter:

while ValidDigit > 0 do

Die Variable GültigeEntscheidungen aus dem PseudeCode ist eine Menge; Die Bedingung für die While-Schleife ist an die Anzahl der Elemente in dieser Menge geknüpft. Am einfachsten gehts hier tatsächlich mit einer Liste.

Zitat von hans ditter:

nr:=random(length(ValidDigit))

ValidDigit enthält ja alle noch gültigen Entscheidungen, aus der eine gewählt werden sollt. Folglich wäre das hier richtig:
nr:=ValidDigit[random(length(ValidDigit))]

Zitat von hans ditter:

Delphi-Quellcode:

if SetDigit(X+1,Y,Size) then
  Result:=True;

Zum einen: X+1 geht nur solange gut, bis X > Size wird; Dann muss die nächste Zeile genommen werden (Y+1). Zum anderen reicht ein result := true; nicht - Die Funktion muss komplett beendet werden.

Zitat von hans ditter:

Delete(nr);

Deswegen würde ich auf eine Liste zurückgreifen. Hier kann man dies einfacher implementieren.

Zitat von hans ditter:

- ... und als letztes noch in der Frage, ob es für eine while-Schleife auch einen else-Zweig gibt.

Nein Eine While-Schleife kennt kein else.

greetz
Mike