Delphi-PRAXiS
Seite 2 von 2     12   

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)
-   Object-Pascal / Delphi-Language (https://www.delphipraxis.net/32-object-pascal-delphi-language/)
-   -   Delphi optimieren einer Prozedur die ein Sudoku lösen kann (https://www.delphipraxis.net/133888-optimieren-einer-prozedur-die-ein-sudoku-loesen-kann.html)

Melvyn 11. Mai 2009 20:23

Re: optimieren einer Prozedur die ein Sudoku lösen kann
 
mmh das kann sein. ich bin sehr ungeduldig... allerdings kann es auch sein das mein rechner dafür zu lahm ist.

alleinherrscher 11. Mai 2009 20:28

Re: optimieren einer Prozedur die ein Sudoku lösen kann
 
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 11. Mai 2009 20:34

Re: optimieren einer Prozedur die ein Sudoku lösen kann
 
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 11. Mai 2009 22:06

Re: optimieren einer Prozedur die ein Sudoku lösen kann
 
Meine Variante besitzt zwei unterschiedliche Lösungsalgorithmen klick

Gravitar 12. Mai 2009 14:56

Re: optimieren einer Prozedur die ein Sudoku lösen kann
 
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 12. Mai 2009 19:10

Re: optimieren einer Prozedur die ein Sudoku lösen kann
 
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;


Alle Zeitangaben in WEZ +1. Es ist jetzt 01:47 Uhr.
Seite 2 von 2     12   

Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz