Sudoku Logik

[hans ditter]

Erstmal danke für deine Antwort... aber jetzt geht das Prog leider gar nicht mehr...

Wenn man jetzt auf neues Spiel klickt, dann hängt sich das Programm auf. Im TaskManager steht dann "Keine Rückmeldung". Bin mal mit dem Debugger rübergegangen, da haben auch alle Funktionen richtig funktioniert, aber leider war hing das Prgramm nach 10 min noch...

Vlt könntest du dir nochmal den Quelltext anschauen.

Delphi-Quellcode:

function CreateNewSudoku(Size: integer) : integer;
var
  x,y,nr: Integer;
begin
  Randomize;
  PrepareMap(Size);
  nr:=0;
  for x := 0 to Size - 1 do //for1
  begin
    for y := 0 to Size - 1 do //for2
    begin
      while not (DigitIsOk(x,y,Size-1,nr)) do
      begin
        nr:=random(4)+1;
      end;
      Form1.Map.Cells[y,x]:=IntToStr(nr);
    end; //for1
  end; //for2 
end;

function DigitIsOK(X,Y,Size,Digit: integer):boolean;
var
  i: Integer;
begin
  Result:=True;

  if not(Digit = 0) then
  begin
    for i := 0 to Size do
    begin
      if (Digit = StrToInt(Form1.Map.Cells[X,i])) OR
         (Digit = StrToInt(Form1.Map.Cells[i,Y])) then
        begin
          Result:=False;
          Break;
        end;
    end;
  end
  else
    Result:=false;
end;

[JasonDX]

Zitat von hans ditter:

Erstmal danke für deine Antwort... aber jetzt geht das Prog leider gar nicht mehr...

Wenn man jetzt auf neues Spiel klickt, dann hängt sich das Programm auf. Im TaskManager steht dann "Keine Rückmeldung". Bin mal mit dem Debugger rübergegangen, da haben auch alle Funktionen richtig funktioniert, aber leider war hing das Prgramm nach 10 min noch...

Ein Fehler im Code ist folgender:

Zitat von hans ditter:

nr:=random(4)+1;

Statt der 4 sollte ein Size hin, ansonsten würde das Generieren nur mit 4x4-Sudokus funktionieren.
Zudem fehlt das Backtracking in deinem Algorithmus. Mal angenommen du willst ein 4x4-Sudoku generieren, und dein Programm ist bei folgendem Sudoku angelangt:

Code:

1 2 3 4
2 3 1 x

Ist soweit alles gültig, bloß wird dein Programm hier für x keine Zahl finden, für die das Sudoku gültig ist. Also sucht der Algorithmus (per Zufall) ewig nach einer Zahl, die es nicht gibt.

Btw:

Zitat von hans ditter:

Leider bekomme ich im Moment nichtmal das generieren eines neuen Sudokus hin...

Das Generieren von Logikpuzzeln ist um Welten schwieriger als das Lösen

greetz
Mike

[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