Sudoku Logik

[hans ditter]

Hallo alle zusammen,

sorry, dass ich erst jetzt schreib. Die Schule frisst einen auf...
Ich hab den Quellcode nach euren Angaben verbessert. Jetzt scheint es auch zu funktionieren. Allerdings kommt zwischendurch mal ein Sudoku, wo die letzte Reihe nur mit Nullen gefüllt ist. Ich häng das Projekt nochmal ran.

Wenn ihr möchtet, könnt ihr ja gerne auch nochmal testen, ob das bei euch auch funktioniert... würde mich freuen!

LG, hans ditter

[Deep-Sea]

Was gibt es neues an der Sudoku-Front?

[Jumpy]

In der letzten Version gibt es einen Logikfehler irgendwo, aber ich konnte ihn nicht finden.
Hab mal die Ideen von Hans in einer abgewandelten Version eingebaut. Kommt nicht an deine damalige Version dran, aber Hans (und mir auch) ging es glaub ich um den Lerneffekt. Meine Variante scheint zu laufen, drum häng ich sie mal hier an.

[hans ditter]

Hm, ja, scheint wirklich zu laufen. Das mit dem logischen Fehler hab ich auch schon entdeckt, aber ich weiß nicht, wo der Fehler ist... hast du ja auch nicht rausgefunden.
Ich werd mir deine Version und meine die Tage nochmal anschauen. Hoffe, ich finde den Fehler.

LG und danke für die Hilfe,

hans ditter

[Jumpy]

Manchmal hilft es scheinbar, wenn man den ganzen Kram 3 Wochen liegen läßt und dann nochmal draufguckt. Hab den Fehler mMn gefunden: 3. Zeile von unten.
Zudem hab ich mal die Bestimmung von X,Y aus der Schleife rausgenommen. Das muss ja nicht jedes mal neu berechnet werden, da es sich ja nicht ändert.

Delphi-Quellcode:

function SetCell(i: integer) : boolean;
var ValidDecision: TStringList;
  j,X,Y: Integer;
  dig: string;
begin
  if i > (Size * Size - 1) then
  begin
    Result:=true;
    Exit;
  end;

      X:=i mod Size; //hierhin verschoben
      Y:=i div Size;

{.....................................................................}
  ValidDecision:=TStringList.Create;
  for j := 1 to Size do
    ValidDecision.Add(IntToStr(j));
{.....................................................................}
  while ValidDecision.Count > 0 do
  begin
    dig:=ValidDecision[random(ValidDecision.Count)];
    if DigitIsOk(i,StrToInt(dig)) then
    begin
//      X:=i mod Size;
//      Y:=i div Size;
      Form1.Map.Cells[X,Y]:=dig;
      if SetCell(i + 1) then
      begin
        Result:=True;
        Exit;
      end;
    end
    else
      ValidDecision.Delete(ValidDecision.IndexOf(dig));
  end;

  ValidDecision.Free;
  Form1.Map.Cells[0,0]:=dig;//Das ist der Fehler!!! Es muss nicht die 0/0 Zelle gestzt werden,
                            //sondern die X/Y Zelle muss auf 0 gesetzt werden:
  Form1.Map.Cells[X,Y]:='0';
  Result:=False;
end;

Das müsste es doch gewesen sein, oder?

[hans ditter]

@Jumpy
Ich glaube nicht, dass da der Fehler liegt. Ich hatte das (um ehrlich zu sein) bei mir nichtmal in der Unit drin. Weiß nicht, wo das bei dir hergekommen ist. Braucht man ja eigentlich auch nicht, oder?

Ich hab gerade überlegt, ob es möglicherweise woanders dran liegen könnte: Wenn jetzt ein Teilsudoku erstellt wird, bei dem ab einer bestimmten Stelle einfach keine Lösung mehr möglich ist, dann bricht der ja nicht ab. Vlt müsste man da was einstellen, dass wenn die Funktion false zurückliefert man die nochmal von vorne aufruft...

Ich komm auch mit dem Teil noch nicht ganz klar:

Delphi-Quellcode:

while ValidDecision.Count > 0 do
  begin
    dig:=ValidDecision[random(ValidDecision.Count)];
    if DigitIsOk(i,StrToInt(dig)) then
    begin
      Form1.Map.Cells[X,Y]:=dig;
      if SetCell(i + 1) then // müsste hier nicht noch ein else-Zweig rein?
      begin
        Result:=True;
        Exit;
      end;
    end
    else
      ValidDecision.Delete(ValidDecision.IndexOf(dig));
  end;

Bei dem Kommentar, müsste da nicht noch ein else-Zweig rein, was passiert, wenn die Funktion false zurückgibt? Denn wenn sie das tut, wird darauf imho nicht reagiert...

LG, hans ditter

[hans ditter]

HA! Ich glaub ich hab ihn gefunden, den Fehler. Wobei, war weniger ein Fehler als mehr was vergessen...

Also, die Funktion CreateNewSudoku wird ja vom HA aufgerufen und steuert dann die ganze Erzeugung etc.

Delphi-Quellcode:

procedure CreateNewSudoku(PlaygroundSize: integer);
begin
  Size:=PlaygroundSize;
  Randomize;
  PrepareMap(Size);
  if NOT(SetCell(0))
    then SetCell(0);
end;

Ich hab jetzt mal bei SetCell(0) eine if-Bedingung eingebaut. Falls das Sudoku nicht komplett erzeugt werden konnte, wird die Funktion einfach nochmal aufgerufen. Ich halte es eher für unwahrscheinlich, dass zweimal hintereinander ein Sudoku erzeugt wird, was nicht aufgeht.
Bei den Probeläufen hat es jetzt funktioniert! Ausserdem beachte noch den vorigen Post, dass hab ich drin gelassen. Glaube dass das da auch rein muss... Was sagst du?

Häng das Prog jetzt auch nicht ran, ausser du willst es nochmal testen, dann kann ich's nochmal machen...

LG; hans ditter

[Jumpy]

Hallo Hans,

du hast in sofern recht, das mein gefundener Fehler gar nicht bei dir im Programm war. Das hab ich vor 3 Wochen, als du #61 hochgeladen hast, da eingefügt, weil ich dachte, dass es den Fehler beheben würde (es muss, wenn die Fkt. false zurück gibt, auch die Zelle an der Position wieder auf 0 gesetzt werden.

Leider hab ich mich da beim Schreiben vertan und es hat nix gebracht, da ich gerade das auf null setzten da nicht gemacht habe. Mt der Korrektur oben funktioniert es dann aber, ...immer !!!

Was du gemacht hast ist schlecht. Du bekämpft nicht das Problem, sondern du "vertuschst" es. Du läßt das Programm sooft laufen, bis ein Sudoku ohne die Nullen entsteht. Das geht zwar auch, aber hat viele Nachteile:
- Längere Laufzeit (OK fällt bei 2x2 nicht auf, aber bei 4x4)
- Zudem werden auch falsche Sudokus generiert, wo zwar alle Nullen weg sind, aber trotzdem z.B. zwei 4ren in einer Reihe sind. Mach es mal oft genug, dann wirst du so eine Variante sehen.

Denk nochmal drüber nach, wie das rekursive Programm genau abläuft. Dann wird dir auch auffallen, dass du keinen Else-Zweig brauchst!!! Mach mal Gedanklich einen "Schreibtischtest" was an irgendeiener Stelle des Sudokus passiert.

[hans ditter]

Hm, tja, ich fürchte, ich muss wohl das ganze nochmal überarbeiten. Bin fast am überlegen, ob ich die Funktion zum Erstellen des Sudokus nicht einmal komplett lösche und dann neu machen, gleich vernünftig mit array etc. und mir dann vorher überlege, wie die Logik dahinter ist.

Werd's mir auf jeden Fall nochmal anschauen und: Danke für deine Hilfe!

LG; hans ditter