optimieren einer Prozedur die ein Sudoku lösen kann

[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;