hi,

da ich in letzter Zeit viel mit Sudokus zu tun hatte und auch für die Uni einen Solver schreiben musste, interessiert mich, ob es noch andere hier gibt, die sich mit solchen Algorithmen schon auseinandergesetzt haben und vielleicht den ein oder anderen Tipp haben, da ich meinen Algorithmus gerne verbessern würde.

Mein Algo:

/* Verwendeter Algorithmus: */
/* Backtrack mit intelligenter Suche */
/* -> Anstatt das immer bei Feld(0,0) angefangen wird, wird bei */
/* jedem rekursiven Aufruf das Feld gesucht, in das am */
/* wenigsten Ziffern gesetzt werden dürfen und mit diesem */
/* weitergemacht */
/* */
/* Heuristiken: */
/* - dynamische Kandidatenliste */
/* - Setzen eindeutiger Felder (Felder in denen nur eine Belegung */
/* möglich ist

Mein Programm ist zwar in C++ geschrieben (war so gewollt) aber wenn Interesse besteht, kann ich es hier reinstellen (ist nicht allzu lang). Habe im Moment leider nicht so viel Zeit um das Ganze in Delphi umschreiben zu können.

Damit man mal einen Vergleich hat, sind hier 5 komplexere Sudokus. Ein "guter" Algorithmus sollte sie in recht kurzer Zeit
lösen können.

000100038
200005000
000000000
050000400
400030000
000700006
001000050
000060200
060004000

200100600
009000300
000040000
500000048
000003050
000900000
000200900
400080000
010000000

200100700
040800000
000000000
053006000
060040000
000000100
800000020
100900000
000000056

010050300
000800000
070000000
020400700
600280000
300000100
900000020
000001000
000000080

010050300
000600000
080000000
060400800
700260000
300000100
900000020
000001000
000000060

Die 0 steht dabei für ein leeres Feld. Mein Algorithmus braucht dafür 1.063 Sekunden (Pentium M 2 GHz).

Bin gespannt auf eure Meinungen / Vorschläge /...

MfG

JackF

Hallo,

es geht ohne Intelligenz wesentlich schneller : www.delphi-forum.de/viewtopic.php?t=48567

Gruss Horst

danke für den Link, werd ich mir mal anschauen.

Hi,

ich habe mal deine Sudokus auf mein Programm (mit Delphi) losgelassen.

Ergebnis für Sudoku 2:

Reines Back-Tracking ohne aufwändige Intelligenz

9.768.011 Versuche in 62,609 Sekunden.

Vorheriges identifizieren von eindeutigen Lösungen und danach Back-Tracking (wie oben):

547.328 Versuche in 6,266 Sekunden.

Interessant ist, das ein vorheriges Sortieren der Back-Tracking-Feldliste nach Anzahl der möglichen Versuche (fange also zuerst mit dem Feld an, das nur noch wenige gültige Varianten enthält) deutlich länger dauert!!! (in diesem Fall 1.531.805 Versuche in 19,906 Sekunden).

Mit ca. 6 Sekunden für Sudoku 2 bin ich glaube ich ganz gut dabei.

Ist denn deine Zeit als Gesamtzeit für alle Sudokus zu verstehen?

Gruß, Andreas

Also da muss dein "Sortieren" aber schlecht implementiert sein, wenn man beim rekursiven Abstieg immer mit dem Feld mit den wenigsten Möglichkeiten weitermacht, erhöht das schon ordentlich die Geschwindigkeit.

Inzwischen habe ich mein Programm an diversen Stellen optimiert, sodass das 100er File im Anhang in 0,4 Sekunden gelöst wird.
Die Sudokus von oben sind Teil davon.

Gruß

JackF

Hey, Wahnsinn, 100 knifflige Sudokus in 0,4 Sekunden, RESPEKT.

Kannst du das Programm mal bereitstellen, damit ich sehen kann, wo mein sortieren schiefläuft?

Gruß, Andreas

Sind das jetzt 100 Sudokus oder ein großes Sudoku?

@Chryzler: Das sind 100 Sudokus. Was vielleicht komisch aussieht sind die Zeilenumbruchszeichen. Einfach das File in einem Browser öffnen und dort speichern. Dann sind die Zeichen weg.

@Gravitar: Meinst du den Quellcode? Kann ich machen, jedoch ist das ganze in C++ geschrieben (war für die Uni) und ich hab im Moment keine Zeit das umzuschreiben.

Jack Falworth hat folgendes geschrieben:

@Gravitar: Meinst du den Quellcode? Kann ich machen, jedoch ist das ganze in C++ geschrieben (war für die Uni) und ich hab im Moment keine Zeit das umzuschreiben.

Na Quellcode (ruhig in C++) und EXE, um

a) zu schauen wie es funzt

b) die angegebene Zeit auf meinem Rechner zu testen

Besten Dank im Voraus,

Gruß Andreas

Der Sudoku-Solver ist ein Konsolenprogramm. Kann noch sein, dass in der "Menuführung" noch der ein oder andere Bug ist.
Der Algorithmus ist aber einwandfrei.

Gruß

JackF

Hallo Jack,

dein Programm hat mich wirklich einige Nerven gekostet!

Der Algorithmus ist kurz, effizient und rasend schnell (auch wenn ich c nicht so recht verstehe).

Inzwischen habe ich an meinem Delphi-Programm so einige Effizienzbremsen eliminiert (Ausgabe während der Berechnung in ein Stringgrid, vorheriges Abspeichern aller leeren Felder in ein Array etc. etc.).

Der wirkliche Durchbruch ist mir dann erst bei der Optimierung der eindeutigen Lösungen gelungen.

Jetzt läuft mein Programm durch die 100 Sudokus in 0,249 Sekunden (dein Programm braucht auf meinem Rechner 0,844 Sekunden).

Wie sieht es aus?

Schafft es jemand, noch höhere Geschwindigkeiten zu erreichen?

Gruß,

hi Gravitar,

also wenn du gefragt hättest, hätte ich dir den Algorithmus auch beschreiben können, wäre wohl einfacher gewesen.
Naja wenn man kein c++ kann, ist so manches wohl nicht so verständlich, obwohl ich denke ich hab ausreichend kommentare geschrieben.

Hab mal kurz über dein Programm geschaut. Also ich finde dein Programmierstil ziemlich grausam. Wenig Kommentare und vor allem keine eigene Klasse oder zumindest eigene Funktionen. Alles in Form1 zu packen ist wirklich sehr unschön. Aber daran kann man ja noch arbeiten

Zum Programm selbst, irgendwie ist mir schleierhaft was die Funktionen 'öffnen' und 'batchload' bedeuten. Wäre es bei 'öffnen' nicht besser, wenn der Benutzer selbst über einen OpenDialog eine Datei angeben kann?

Achja die 400ms bei mir waren auf einem Pentium M 2 Ghz.
Natürlich könnte man noch weiteroptimieren bis die Schwarte kracht (Präprozessor-Makros, GCov-Abdeckung, GProf,...) aber dazu fehlt mir im Moment einfach die Zeit (mache momentan ein Vollzeit-Softwarepraktikum an der Uni). Außerdem ist das Ganze auch schon eine Weile her.

Und was sagte Kernighan and Pike in 'The practice of programming' zum Grundprinzip des Optimierens? "Lass es sein"

Hi Jack,

ja, das mit den Klassen habe ich nie wirklich kapiert. Eigentlich ignoriere ich den objektorientierten Ansatz komplett.

Wie sähe das Programm denn mit einer eigenen Klasse aus?

Das Thema Batch-Load lädt die pr.txt und löst die dort enthaltenen Sudokus sukzessive. Die Lösung wird dann wieder in pr_solution.txt geschrieben. Dort sind auch die Lösungszeiten je Sudoku und Gesamtzeit vertreten.

Zum Thema Öffnen-Dialog: Ja, kommt irgendwann wenn ich wieder Zeit dazu gewinne.

Gruß,

Eigentlich ist das Sinn und Zweck einer OOP, dass man Objekte erstellen kann und so Funktionen, Attribute, Methoden kapseln kann.
wenn du noch nie vorher was mit Klassen gemacht hast, würde das hier wohl zu weit führen.

In meinem Programm hab ich beispielsweise eine eigene Sudoku-Klasse geschrieben. Das ganze ist auch später fürs Verständnis besser. Damit kapsle ich beispielsweise die Dateioperationen und den Benutzerdialog von dem Sudoku-Solver ab.
Für den generellen Aufbau kannst du dir ja einfach mal die Form1 in deinem Quellcode anschauen, dann siehst du mal den generellen Aufbau von einer Klasse (exemplarisch). Wenn du dich dafür interessierst, würde ich mir Klassen-Tutorials anschauen oder vielleicht ein Delphi Buch zulegen.

Achja noch kurz zu meinem Programm (ist mir eben aufgefallen): es wirkt langsamer als es ist. Die Zeit, die ich ausgebe, beinhaltet alles, also Dateieingabe und -ausgabe + Verwaltung + lösen. Wenn ich die reine Lösungszeit zusammenzähle ist das Teil noch ein gutes Stück schneller.

MfG JackF

Hi Jack,

na dann werde ich mich mal um die Klassen kümmern!

Übrigens, wenn ich die Gesamtlösungszeit ermittle (also init, Dateien lesen, lösen, schreiben...) bin ich bei ca. 0,4 Sekunden. Damit immer noch doppelt so schnell wie dein Programm (0,8 Sekunden auf meinem Rechner).

Insofern mag der Stil gewöhnungsbedürftig sein, die Effizienz ist aber o.k.

Gruß, Andreas

ähm ich weiß ja nicht was du für einen Rechner hast, aber ein Batchload dauert bei mir 2,6-2,7 sec .
Wie kommst du auf 0,2 sec?
Du schreibst selbst in deinem anderen Thread Klick, dass du etwa 3 sec brauchst (was mit meinem Ergebnis übereinstimmt).

Ich will mich jetzt nicht mit dir streiten, aber generell gilt dass Optimierung immer erst der letzte Schritt ist und nie die Stabilität, Modularität, etc. beeinträchtigen soll.

Grüße
JackF

Hi,

die Version aus dem anderen Thread (0.75) ist älter als die in diesem (0.752). Ich habe die Version dort noch nicht nachgezogen (aber schön, dass du sie dort gefunden hast ).

Mit den Zeiten ist das in der Tat allerdings merkwürdig. Mein Rechner (AMD64 3.2 GHz) nudelt dein Programm in 0,844 Sekunden und meins (Version 0.752) in den genannten 0,2xx Sekunden durch.

Auf deinem Rechner (Pentium M mit 2GHz) läuft dein Programm in 0,4xx Sekunden und meins benötigt über 2,7 Sekunden??? Hast Du denn wirklich die Version aus dieser Sparte verwendet oder die aus der Sparte "Freeware"?

Aber egal, irgendwann hast Du ja die Frage gestellt, ob an deinem Programm noch eine Effizienzsteigerung möglich ist. Dazu kannst Du ja einfach in den Source schauen.

Viele Grüße,

Andreas