Sudoku Logik

[hans ditter]

Moin moin,

ich habe mich gestern mal an einem Sudokuspiel versucht. Leider bekomme ich im Moment nichtmal das generieren eines neuen Sudokus hin...
Es hapert anscheinend ein wenig an der Logik, wie ich da ran gehe.

Für das Spielfeld benutzte ich ein Stringgrid. Ich dachte mir, ich schreib in das Feld[0,0] eine zufällige Zahl, dann schreib ich in das Feld[0,1] eine zufällige Zahl und überprüfe, ob diese mit irgendeiner anderen Zahl in der Reihe, Spalte oder dem Quadrat kolidiert.

Die Überprüfung des Quadrats hab ich noch nicht, weil ich bis jetzt nochnichtmal die Reihe / Spalte überprüft bekomme.

Digit: zufällige Zahl
Size: Größe (z.B. 4x4)
X, Y: Koordinaten des Felds[x,y] in das geschrieben werden soll

Delphi-Quellcode:

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

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

Hoffe ihr könnt mir auf die Sprünge helfen...

bd, hans ditter

[himitsu]

Entweder vor der schleife das Result auf True setzt.
Sonst überschreibst du ständig den letzen Fund, außer es ist zufällig letzte Zahl der Spalte.

Oder du brichst die Schleife mit Break; ab, nachdem dort False gesetzt wurde.
Hierbei ebenfalls vorher auf True setzen (einmal reicht ja).

Oder mit Exit; die Funktion abbrechen und, falls die Schleife komplett durchlaufen werden konnte (also nix gefunden), dann nachher auf True setzen.

Delphi-Quellcode:

function DigitIsOK(X,Y,Size,Digit: integer):boolean;
var
  i: Integer;
begin
  if not(Digit = 0) then
  begin
    Result:=True;
    for i := 0 to Size do
      if (Digit = StrToInt(Form1.Map.Cells[X,i])) 
          or (Digit = StrToInt(Form1.Map.Cells[i,Y])) then
        Result:=False;
  end
  else
    Result:=false;
end;

Die Verwendung von Form1. gibt schonmal einen deutlichen Hinweis darauf, daß diese Funktion besser zu einer Methode der Form gemacht werden sollte.

[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

[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