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

[Sani93]

ähm sorry das ich frag, aber ich bin ganz neu hier und hab KEINE ahnung wie man ein eigenes thema erstellt. ich bin hier am verzweifeln -.-
wäre sehr nett, wenn mir jmd sagen könnte (am besten via nachricht) wie ich das mache

[LWChris]

Zitat von Sani93:

ähm sorry das ich frag, aber ich bin ganz neu hier und hab KEINE ahnung wie man ein eigenes thema erstellt. ich bin hier am verzweifeln -.-
wäre sehr nett, wenn mir jmd sagen könnte (am besten via nachricht) wie ich das mache

Geh ins Allgemeine Forum, wähle das zu deiner Frage passende Unterforum aus, und klicke dort auf den großen Button "Neues Thema erstellen".

Zur Topic: ich hab mal einen ganz anderen Ansatz für euch, den ich mir mal für das automatisierte Lösen von Sudokus bis 9x9 überlegt habe: Ihr erzeugt entsprechend der Größe des Sudokus ein mehrdimensionales Array of String, in den String schreibt man alle möglichen Werte, und löscht sie beim Setzen aus den anderen Feldern raus. Sobald ein Feld leer ist, ist die Erstellung des Sudokus gescheitert.

So könnte man das Sudoku rekursiv füllen: Setze Feld für Feld einen der möglichen Werte zufällig ein. Versuche dann, den nächsten Wert zu setzen. Stellst du fest, dass es nicht mehr lösbar ist, breche ab mit Ergebnis false. Wähle in diesem Fall (wieder in der übergeordneten Ebene) einen anderen der noch möglichen Werte aus. Ist kein Wert mehr möglich, breche wieder ab mit Ergebnis false.

Delphi-Quellcode:

type TSudoku: Array[1..9] of Array[1..9] of String[9];

procedure NeuesSudoku(var Sudoku: TSudoku);
var a, b: Integer;
begin
  for a:=1 to 9 do
    for b:=1 to 9 do
      Sudoku[a][b]:='123456789';
end;

function FeldIstGesetzt(var Sudoku: TSudokuZeile, Spalte: Integer): Boolean;
begin
  result:=Length(Sudoku[Zeile][Spalte])=1;
end;

procedure BlockeWertInFeld(var Sudoku: TSudoku; Zeile, Spalte: Integer; Wert: Char);
begin
  Feld:=Sudoku[Zeile][Spalte];
  Sudoku[Zeile][Spalte]:=Copy(Feld,1,Pos(Wert,Feld)-1)+Copy(Feld,Pos(Wert,Feld)+1,Length(Feld));
end;

function Erstellbar(var Sudoku: TSudoku): Boolean;
var a, b: Integer;
begin
  result:=true;
  for a:=1 to 9 do
    for b:=1 to 9 do
      if Length(Sudoku[a][b])=0 then
        result:=false;
end;

function Erstellt(var Sudoku: TSudoku): Boolean;
var a, b: Integer;
begin
  result:=true;
  for a:=1 to 9 do
    for b:=1 to 9 do
      if Length(Sudoku[a][b])>1 then
        result:=false;
end;

function SetzeFeld(var Sudoku: TSudoku; Zeile, Spalte: Integer; Wert: Char): Boolean;
var a, b: Integer;
begin
  if Pos(Wert,Sudoku[Zeile][Spalte])>0 then
    begin
      Sudoku[Zeile][Spalte]:=Wert;
      // Wert für alle Felder in Zeile und Spalte blocken;
      for a:=1 to 9 do
        begin
          BlockeWertInFeld(a,Spalte,Wert);
          BlockeWertInFeld(Zeile,a,Wert);
        end;
      // Wert für Quadrat blocken
      Zeile:=((Zeile-1) DIV 3)*3+1;
      Spalte:=((Spalte-1) DIV 3)*3+1;
      for a:=Zeile to Zeile+2 do
        for b:=Spalte to Spalte+2 do
          BlockeWertInFeld(a,b,Wert);
      result:=true;
    end
  else
    result:=false;
end;

function ErstelleSudoku(var Sudoku: TSudoku; Zeile, Spalte: Integer): Boolean;
var Klon: TSudoku; a, b: Integer; M: String; Wert: Char;
begin
  result:=false;
  if Erstellbar(Sudoku) then
    begin
      if Spalte=10 then
        begin
          Spalte:=1;
          Inc(Zeile);
        end;
      if Zeile=10 then
        result:=true // Alle Zeilen und Spalten voll
      else
        begin
          M:=Sudoku[Zeile][Spalte]; // Mögliche Werte
          while (M<>'') and (not result) do
            begin
              for a:=1 to 9 do
                for b:=1 to 9 do
                  Klon[a][b]:=Sudoku[a][b];
              Wert:=M[Math.Random(Length(M))];
              SetzeFeld(Klon,Zeile,Spale,Wert);
              M:=Copy(M,1,Pos(Wert,M)-1)+Copy(M,Pos(Wert,M)+1,Length(M));
              result:=ErstelleSudoku(Klon,Zeile,Spalte+1);
            end;
          if result then
            for a:=1 to 9 do
              for b:=1 to 9 do
                Sudoku[a][b]:=Klon[a][b];
        end;
    end;
end;

procedure ErstelleNeuesSudoku(var Sudoku: TSudoku);
begin
  NeuesSudoku(Sudoku);
  ErstelleSudoku(Sudoku,1,1);
end;

Das ist mein Beitrag, ungetestet, rein auf Logik und theoretischer Vorstellung basierend. Eurer Part wäre es jetzt, das Ding zu prüfen, ggf. zu reparieren und/oder variabel hinzubiegen und auf die StringGrid anzupassen.

Chris

[Kalakmul]

Zu dem Themenkomplex Backtracking-Algorithmus/Sudoku-Solver gibt es übrigens hier http://academicearth.org/lectures/ba...ing-pseudocode eine wie ich finde sehr interessante Vorlesung der Stanford University als Video.

Als Programmiersprache wird zwar nicht Delphi verwendet, sondern zumeist einfache Java- bzw. Pseudocodekonstrukte, die sich aber in jede Sprache leicht übertragen lassen sollten. Auch die anderen Videos sind sehenswert.

[hans ditter]

Hi Chris.

Interessanter Ansatz! Daran hab ich auch schonmal gedacht, ein Array of Array zu erzeugen. Aber so wie es im Moment ist, ist es erstmal einfacher für mich. Das muss ich erstmal hinbekommen, dann versuch ich mich vielleicht an deiner Idee...

Denn wie es hesst es so schön:
Immer langsam mit den jungen Pferden!

LG, hans ditter