optimieren einer Prozedur die ein Sudoku lösen kann

[Melvyn]

Hallo Leute,

ich bin gerade dabei einen Sudokulöser mit Delphi7 zu schreiben. Er lässt sich bereits starten, aber funktioniert noch nicht obwohl Delphi keinen Fehler anzeigt. Kann mir jemand helfen den Fehler im Quelltext zu suchen?

Danke bereits im Vorraus
Melvyn

[DeddyH]

Dazu kann ich nur sagen: viel Glück.

[Melvyn]

was meinst du?

[Mithrandir]

Und wieder einer, der den Sinn eines Internetforums nicht erkannt hat. Hängt hier irgendwo ein Schild? :gruebel:


Btw,

Willkommen :dp:

//Edit:
Smiley repariert. :roll:

[Melvyn]

Ja, ich kenne den Sinn eines Forums. Aber den ganzen Quelltext zu diskutieren hat wenig Sinn...

Aber eine Frage: Kannst du mir helfen?

[shmia]

Zitat:

Zitat von Melvyn

(Ich verschicke dann Quelltext und Screen per Mail, da ich vor der Fertigstellung des Programms den Quelltext nicht veröffentlichen möchte)

So geht das nicht.
Niemand möchte ein nichtfunktionierendes Sudokuprogramm nach Fehlern durchsuchen und die Kommunikation über EMail führen.
(und auch noch seine EMail-Adresse preisgeben)
Du stellst möglichst konkrete Fragen und bietest dafür so viel Information wie nötig.
Im optimalen Fall lieferst du ein halbfertiges Programm mit Sourcecode und bekommst dafür Tipps und Hilfe.
Hier im Forum entsteht dann ein mehr oder weniger funktionierendes Programm von dem Jeder profitieren und lernen kann.
>> Aber den ganzen Quelltext zu diskutieren hat wenig Sinn
Man kann jedes Problem in Teilprobleme zerlegen und du darfst auch gerne den gesamten Sourcecode (bitte ohne DCU und ~*-Dateien) als Zip-Archiv anhängen.

[Mithrandir]

Zitat:

Zitat von Melvyn

Aber eine Frage: Kannst du mir helfen?

Bestimmt. So wie viele andere hier. Stelle den Quelltext rein, warte, bis jemand (oder mehrere) Zeit und Lust gefunden hat, da mal einen Blick drauf zu werfen, und schwuppdiewuppdi ist anderen Neulingen auch geholfen. ;)

Privataudienzen gibts natürlich auch, allerdings nur gegen Gebühr. ;)

Sorry, aber auf die Art und Weise nach Hilfe fragen ist kein guter Start in einem Forum. Erstelle einen neuen Thread unter "Open-Source" mit deinem Programm.

[DeddyH]

Bei der Gelegenheit könntest Du gleich den ersten Beitrag editieren und einen anderen Titel wählen, der das Problem zumindest im Ansatz beschreibt (Hilfe suchen hier so ziemlich alle ;))

[Melvyn]

Gut dann werd ich mal konkretisieren. Die Lösen-Funktion des Sudokus funktioniert noch nicht. Beim drücken des Buttons zur laufzeit hängt sich das programm dann auf. Im moment sieht diese Prozedur jetzt so aus:

Delphi-Quellcode:

procedure TForm1.BitBtn3Click(Sender: TObject);
var x,y,bes:integer;
    n:string;
    function SIndex(x,y:integer):integer; begin result:= (x+(y*9))+1; end;
begin
 Start();
 for y:=0 to 8 do
  for x:=0 to 8 do
   begin
    bes:=Bestaetigen(StringGrid1.Cells[x,y]);
    if bes>0 then
     begin
      if WertSetzen(SIndex(x,y), bes) then
       begin
        S[SIndex(x,y)].a:=bes;
        S[SIndex(x,y)].b:=false;
       end else
       begin
        MessageBox(self.Handle, 'Falsche Eingabe!','Bitte erneut eingeben', mb_iconerror);
        exit;
       end;
     end else
      if bes<0 then
       begin
        n:='Ungültige Eingabe:' + StringGrid1.Cells[x,y];
        MessageBox(self.Handle, pchar(n), 'Fehler', mb_iconerror);
        exit;
       end;
   end;
 Loesen();
 for y:=0 to 8 do
  for x:=0 to 8 do
   StringGrid1.Cells[x,y]:=IntToStr(S[SIndex(x,y)].a);
end;

die ausgabe hab ich dann noch für mojidoku umegebastelt, aber auch das funktioniert noch nicht

Delphi-Quellcode:

StringGrid1.Cells[x,y]:=chr(ord(S[SIndex(x,y)].a)+26);

Loesen() ist eine eigenständige Prozedur

Delphi-Quellcode:

procedure Loesen();
var
 c:integer;
begin
 c:=1;
  while c<=81 do
   begin
    if S[c].b then
     begin
      if S[c].a<9 then
       begin
        inc(S[c].a);
        if WertSetzen(c,S[c].a) then
         begin
          inc(c);
         end else
         if S[c].a=9 then
          repeat
           if S[c].b then S[c].a:=0;
           dec(c);
           if S[c].b then WertFreigeben(c,S[c].a);
          until S[c].b
         end else
         begin
          WertFreigeben(c,S[c].a);
          repeat
           if S[c].b then S[c].a:=0;
           dec(c);
           if S[c].b then WertFreigeben(c,S[c].a);
          until S[c].b
         end;
      end else inc(c);
   end;
end;

so ich hoffe ihr könnt mir helfen. ich habe anfangs eine offene schleife vermutet aber keinen anhaltspunkt dafür gefunden.

[edit=mkinzler]Code-Tags durch Delphi-Tags ersetzt Mfg, mkinzler[/edit]

[shmia]

Das sieht für mich aus wie ein Brute-Force Algorithmus.
Dabei sind mal so ganz grob ~ 600 Mio. Lösungsschritte notwendig.
Im englischen Wikipedia wird berichtet, dass diese Lösungsstrategie ca. 30 bis 45 Min benötigt.
http://en.wikipedia.org/wiki/Algorit...y_backtracking

[Melvyn]

mmh das kann sein. ich bin sehr ungeduldig... allerdings kann es auch sein das mein rechner dafür zu lahm ist.

[alleinherrscher]

Okay, ich hab mir den Wikipediaeintrag jetzt nicht ganz durchgelesen. Aber wäre es nicht grundsätzlich besser, das Problem auf lineare Gleichungssysteme zu bringen (jedes leere Feld ist eine Variable) und dann einen Gaußalgorithmus zur Lösung zu verwenden. Ich denke, das sollte deutlich schneller gehen als 30-40 Minuten ;-)

[igel457]

Also mein Brute-Force Algorithmus klappt bei sehr vielen Rätseln - und auch recht schnell (bis auf einige ausnahmen). Das Programm (ist schon vier Jahre alt) findet sich hier. Der Quelltext ist recht gut kommentiert. Vielleicht hilft es ja bei der Lösung des Problems:

http://www.delphipraxis.net/internal...ct.php?t=70493

Edit:
Normalerweise würde ich heutzutage das Rätsel über einen binären Baum lösen.

[omata]

Meine Variante besitzt zwei unterschiedliche Lösungsalgorithmen klick

[Gravitar]

Zitat:

Zitat von Melvyn

mmh das kann sein. ich bin sehr ungeduldig... allerdings kann es auch sein das mein rechner dafür zu lahm ist.

So wie ich das sehe gehst du Feld für Feld von links oben nach rechts unten vor und versuchst über Brute-Force/Backtracking eine Lösung zu finden.

Das kann in der Tat sehr lang dauern.

Ich habe ebenfalls einen Brute-Force-Algorithmus entwickelt, der allerdings nicht stumpf die Felder von links nach rechts abarbeitet, sondern sich in der jeweiligen Rekursionsstufe immer das Feld sucht, in dem die geringsten Antwortmöglichkeiten existieren.

Wenn man so vorgeht, liegt die Antwortzeit im Millisekundenbereich. Meine längste Lösungszeit lag glaube ich bei 197 Millisekunden. I.d.R. liegt die Lösung allerdings in 18 Millisekunden vor.

Das müßte auch für ungeduldige ausreichen :wink:

Gruß, Andreas

[Melvyn]

hmm es funktioniert schon so wie ich es hatte ;) ich hatte bloß ein sehr schweres Sudoku genommen für das er sehr lange gebraucht hätte. mit einem einfachen is die lösung auch innerhalb von ms da.

weil ich dieselbe prozedur auch für ein Mojidoku möchte, hab ich die ausgabe zeile verändert:

Delphi-Quellcode:

StringGrid1.Cells[x,y]:=chr(ord(S[SIndex(x,y)].a)+26);

allerdings müsste ich dann ja immernoch zahlen eingeben. ich möchte aber auch buchstaben eingeben können.
Müsste das dann so lauten? :

Delphi-Quellcode:

StringGrid1.Cells[x,y]:=chr(ord(S[SIndex(x,y)].a)-26);

meine frage ist jetzt wo ich diese zeile platzieren müsste.
die prozedur ist:

Delphi-Quellcode:

procedure TForm1.BitBtn6Click(Sender: TObject);
var x,y,bes:integer;
    n:string;
    function SIndex(x,y:integer):integer; begin result:= (x+(y*9))+1; end;
begin
 Start();
 for y:=0 to 8 do
  for x:=0 to 8 do
   begin
    bes:=Bestaetigen(StringGrid1.Cells[x,y]);
    if bes>0 then
     begin
      if WertSetzen(SIndex(x,y), bes) then
       begin
        S[SIndex(x,y)].a:=bes;
        S[SIndex(x,y)].b:=false;
       end else
       begin
        MessageBox(self.Handle, 'Falsche Eingabe!','Bitte erneut eingeben', mb_iconerror);
        exit;
       end;
     end else
      if bes<0 then
       begin
        n:='Ungültige Eingabe:' + StringGrid1.Cells[x,y];
        MessageBox(self.Handle, pchar(n), 'Fehler', mb_iconerror);
        exit;
       end;
   end;
 Loesen();
 for y:=0 to 8 do
  for x:=0 to 8 do
   StringGrid1.Cells[x,y]:=chr(ord(S[SIndex(x,y)].a)+26);
end;