Hi,

ich habe ein kleines Sudoku-Programm geschrieben.



hilft beim Lösen von Sudokus (Einblenden der noch möglichen Werte für jedes Feld, schrittweises Lösen von eindeutigen Einträgen bis hin zu intelligentem Backtracking in rasend schneller Zeit).

Ich selbst bin Autodidakt in Sachen Delphi. Falls also ein "gelernter" Programmierer Hilfe zum Programmierstil hat, wäre ich dankbar.

Im Anhang ist der Source, einige Testdateien mit Sudokus und die ausführbare EXE.

Viele Grüße und viel Spass beim "rumspielen" mit dem Programm wünscht

Andreas Welzien

[EDIT]

Hier jetzt die neue Version mit folgenden Erweiterungen:

- Schrittweises Lösen unter Logik zeigt immer nur eine nächste Ziffer
- Bei Start des Back-Trackings wird ein Pop-Up-Fenster mit Abbruch-Möglichkeit eingeblendet
- Ist ein Sudoku unlösbar (= es existiert keine gültige Lösung), so wird dies angezeigt
- Datei öffnen, speichern... ermöglicht jetzt das öffnen/Anlegen individueller Dateien
- Nach Batch-Load wird angezeigt, in welche Datei die Lösung geschrieben wurde (*.sdv)
- Über Lösungen/Datei öffnen kann diese Batch-Lösungsdatei angzeigt werden
- Die einzelnen Sudoku-Textdateien enhalten jetzt entsprechede Dateierweiterungen:
sde = Sudoku-Einzeldatei
sdb = Sudoku-BatchDatei (mit vielen Sudokus als Aufgabe)
sdv = Sudoku-Lösungsdatei (mit ursprünglicher Aufgabe, Lösung, Einzel- und Gesamtzeit)

Dank an alle Aktiven für die Verbesserungsvorschläge.

[EDIT]

Jetzt die Version 1.0 mit folgenden - finalen - Veränderungen:

- Ausdruck der Sudokus ist möglich (falls man diese auf Papier selbst lösen möchte)
- Eingabe wurde drastisch vereinfacht

[EDIT]

Neu in Version 1.3:

- Generieren von Sudokus mit 7 verschiedenen Schwierigkeitsgraden ("sehr einfach" bis "vergiss es")


Viel Spass wünscht

Andreas

- Schön währe noch eine Anzeige des Fortschritts nach Start des Backtracking.
- Gut währe auch, wenn mann die max. Anzahl der Schritte fürs Backtracking begrenzen könnte oder Du baust alternativ eine Abbruchmöglichkeit ein.
- Planst Du noch weitere Lösungsalgorithmen zu implementieren?

Hallo Quake User,

Quake User hat folgendes geschrieben:

- Schön währe noch eine Anzeige des Fortschritts nach Start des Backtracking.

Na ja, da die Lösung eines minimalen Sudokus (schwerer gehts nicht) ca. 30 Millisec. dauert, würde ein Fortschrittsbalken ziemlich kurz aufblitzen

Für den BatchLoad, bei dem alle 101 Sodukos mit Lösung in die PR_Soulution.txt geschrieben werden, wäre das allerdings eine gute Idee (dauer immerhin ca. 3 Sekunden!! für alle Lösungen). Ich schaue mal, wie ich das einbaue (vermutlich mit Hochzählen der gelösten Sudokus).

Quake User hat folgendes geschrieben:

- Gut währe auch, wenn mann die max. Anzahl der Schritte fürs Backtracking begrenzen könnte oder Du baust alternativ eine Abbruchmöglichkeit ein.

Warum? Siehe erste Antwort.

Quake User hat folgendes geschrieben:

- Planst Du noch weitere Lösungsalgorithmen zu implementieren?

Mmhm, im Moment löst er jedes beliebige Sudoku. Die bisher längste Lösungszeit für ein Sudoku lag bei 609 Millisec. Dies hier war es übrigens (links die Aufgabe, rechts die Lösung inkl. Lösungszeit):

901060000 941762358
080000200 583914267
000000000 267358941
070205000 379245186
400000003 456189723
000000090 812673495
000090010 634597812
020000500 128436579
700800000 795821634
609 Millisec.


Hast Du irgendwelche Ideen für weitere Lösungsalgorithmen?

Viele Grüße,

Andreas Welzien

- Trage bitte mal 5 Zahlen in Dein Sudoku ein und versuche es dann mal. (Ich breche den Prozess dann meist nach einer Min. ab.)

- Kann es sein, dass Du davon aus gehts, dass das Sudoku nur eine Lösung haben kann?

Hi,

ich habe jetzt diverse 5er Sudokus ausprobiert, u.a. dies hier:

020000000
000000000
000000000
000030000
000000050
000000000
000000000
010004000
000000000

Die Lösung wird meist in 0 Millisec. gefunden (AMD64 3,2 GHz). Vermutlich reicht die Genauigkeit von TickCount hier einfach nicht mehr aus.

Tatsächlich findet zeigt das Programm immer die erste gefundene Lösung an (auch wenn es bei 5 gesetzten Felder wohl noch etliche andere Lösungen gibt).

Bei den mitgelieferten 100 minimalen Sudoukus (aus der Datei PR.txt) existiert dagegen nur eine einzige korrekte Lösung. Diese liegen nach dem BatchLoad dann ja auch in der PR_Solution.txt.

Inzwischen ist das Programm noch etwas optimiert worden, so dass auch die kompletten 100 Sudokus in ca. 0,3 Sekunden gelöst werden. Damit scheidet der Fortschrittsbalken endgültig aus.

Aber wenn bei dir eine Lösung mehr als 1 Minute erfordert, dann poste sie doch mal hoch.

Gruß, Andreas

So, jetzt die neue Version V0.753 mit 0,282 Sekunden Lösungszeit für 100 minimale Sudokus.

Gleichzeitig habe ich nun eine Prüfung, ob eine Eingabe überhaupt zulässig ist (falls jemand 5 x die 2 in ein Quadrat eingeben möchte, wird daraus nunmehr nichts).

Ich glaube, sehr viel schneller geht es jetzt wirklich nicht mehr.

Die meisten Sudokus werden in 0 Millisec. gelöst

Viel Spass wünscht Andreas

Bei mir sind diese Blauen Hintergründe hinter den Zahlen viel dunkler, sodass man kaum was erkennen kann.

Kanns sein, dass du da irgendne Systemfarbe nimmst, weil ich hab nen Aero Style drauf.

jakobwenzel hat folgendes geschrieben:

Bei mir sind diese Blauen Hintergründe hinter den Zahlen viel dunkler, sodass man kaum was erkennen kann. Kanns sein, dass du da irgendne Systemfarbe nimmst, weil ich hab nen Aero Style drauf.

Ja, ich nutze clInactiveCaptionText. Erschien mir ganz nett. Aber ändere doch einfach die folgende Zeile aus der Procedure Stringgrid1.DrawCell auf eine dir angenehmere Farbe (z.B. clSkyBlue)



Gruß, Andreas

Gravitar hat folgendes geschrieben:

Hi, ... Tatsächlich findet zeigt das Programm immer die erste gefundene Lösung an (auch wenn es bei 5 gesetzten Felder wohl noch etliche andere Lösungen gibt). ... Aber wenn bei dir eine Lösung mehr als 1 Minute erfordert, dann poste sie doch mal hoch. ...

Du hast den Test nicht durchgeführt. Dein Algorithmus ist NUR bei einfachen Lösungen "schnell". Wenn Du nur 5 Zahlen eintragen würdest, würde sich ein sehr großer Baum aufspannen. Das muss der Nutzer vorab begrenzen können oder alternativ abbrechen.

Quake User hat folgendes geschrieben:

Gravitar hat folgendes geschrieben: Hi, ... Tatsächlich findet zeigt das Programm immer die erste gefundene Lösung an (auch wenn es bei 5 gesetzten Felder wohl noch etliche andere Lösungen gibt). ... Aber wenn bei dir eine Lösung mehr als 1 Minute erfordert, dann poste sie doch mal hoch. ... Du hast den Test nicht durchgeführt. Dein Algorithmus ist NUR bei einfachen Lösungen "schnell". Wenn Du nur 5 Zahlen eintragen würdest, würde sich ein sehr großer Baum aufspannen. Das muss der Nutzer vorab begrenzen können oder alternativ abbrechen.

Häh,

ich habe dir doch direkt geantwortet. Dort ist doch als Beispiel ein 5er Sudoku drin. Alle 5er die ich ausprobiert habe wurden in 0 Millisec. gelöst.

Wie schon gesagt, wenn du ein 5er hast, das länger als - na sagen wir mal 1 Sek. - dauert, dann bitte hier veröffentlichen.

Gruß, Andreas

P.S.: 5er sind viel zu einfach. Die wirklich schwierigen Sudokus sind minimale mit 17 Feldern.

Manchmal bekomme ich beim back-tracen falsche Lösungen, die mehrere gleiche Zahlen in einer Spalte / Zeile haben.

GTA-Place hat folgendes geschrieben:

Manchmal bekomme ich beim back-tracen falsche Lösungen, die mehrere gleiche Zahlen in einer Spalte / Zeile haben.

Bitte das entsprechende Sudoku bereitstellen (CTRL+S und Datei Sudoku.txt posten), damit ich mich auf die Fehlersuche machen kann. Eigentlich sollte das aber nicht vorkommen, da ausschließlich zulässige Zahlen in ein Feld gesetzt werden (über Hilfe werden diese ja auch eingeblendet).

Gruß, Andreas

Zitat:

Häh, ich habe dir doch direkt geantwortet. Dort ist doch als Beispiel ein 5er Sudoku drin. Alle 5er die ich ausprobiert habe wurden in 0 Millisec. gelöst. Wie schon gesagt, wenn du ein 5er hast, das länger als - na sagen wir mal 1 Sek. - dauert, dann bitte hier veröffentlichen. Gruß, Andreas P.S.: 5er sind viel zu einfach. Die wirklich schwierigen Sudokus sind minimale mit 17 Feldern.

OK, ich hänge eine Aufgabe an, bei der sich dein Algo scheinbar "tod läuft"

[quote="Quake User"]

Zitat:

OK, ich hänge eine Aufgabe an, bei der sich dein Algo scheinbar "tod läuft"

Ah, jetzt verstehe ich was du meinst!

In der Tat läuft sich das Backtracking bei fehlerhaften Sudokus (die 2 taucht in der gleichen Spalte mehrfach auf) tot.

Also habe ich in der neuen Version (die Ver. 0.753) eine Prüfung eingebaut, die die Eingabe von ungültigen Sudokus verhindert. Macht ja auch irgendwie keinen Sinn ein Sudoku zu lösen, was von vornherein ungültig ist.

Gruß, Andreas

So weit, so gut.

Das ist aber nur der erste Schritt. Du kannst nicht davon ausgehen, dass Du ALLE möglichen Eingaben, die der Algo nicht abarbeiten kann, von vornherein ausschließt. Deshalb hatte ich Dir ganz am Anfang zwei Ratschläge gegeben.

Diese besitzen, nach wie vor, Gültigkeit.

Quake User hat folgendes geschrieben:

So weit, so gut. Das ist aber nur der erste Schritt. Du kannst nicht davon ausgehen, dass Du ALLE möglichen Eingaben, die der Algo nicht abarbeiten kann, von vornherein ausschließt. Deshalb hatte ich Dir ganz am Anfang zwei Ratschläge gegeben. Diese besitzen, nach wie vor, Gültigkeit.

Ja, du hast Recht. ALLE Eingabe kann ich nicht vorhersehen. Durch die Vers. 0.753 ist zumindestens abgefangen worden, dass von vornherein fehlerhafte Sudokus eingegeben werden können.

Aber durch die bisher gesammelten Erfahrungen mit dem Programm, bin ich immer noch der Meinung, dass kein Fortschrittsbalken notwendig ist, da die Lösung bisher bei reinem Back-Tracking niemals länger als 2 Sekunden und über Logik/alle Eindeutigen und danach Back-Tracking unter 100 Millisec. dauerte.

Des weiteren ist ein Fortschrittsbalken schwierig zu realisieren, da ja am Anfang der Suche nicht klar ist, in wievielen Iterationsschritten die Lösung vorliegen wird. Also kann man nur eine Art "Pseudo-Fortschritssbalken" einblenden, der Stück für Stück wächst und keinen Rückschluss auf die prozentuale Abarbeitung des Problems zuläßt.

Insgesamt also viel Aufwand, wenig Nutzen.

Aber ich will ja nicht ignorant wirken. Wenn irgendjemand mit der Version V0.753 ein zulässiges Rätsel findet, dessen Lösung per Back-Tracking länger als 2-3 Sekunden dauert, dann bitte über CTRL+S speichern, Sudoku.txt posten und ich baue in wahnsinniger Geschwindigkeit einen Fortschrittsbalken ein.

Bis dahin jedoch, halte ich die Finger (rein progammiertechnisch gesehen) still.

Gruß, Andreas

Ich hab das Programm jetzt (noch) nicht getestet, aber wie wäre es anstatt eines Fortschrittbalkens ein kleines "Popup" in dem steht "Bitte warten, wird gelöst..." und unten drunter ein Abbrechen-Button.

So schlägst du zwei Fliegen mit einer Klappe. Man kann abbrechen und der Benutzer sieht das gearbeitet wird.

dein algo scheint nicht alle unlösbaren sudokus zu erkennen, bzw nicht auszugeben, dass er sie erkannt hat.

z.b.

1
2
3
4
5
-9
6
7
8


das sind erste und zweite spalte. der rest ist leer.
Das Programm hängt sich entweder auf oder versucht irgendwas rumzurechnen oder gibt einfach nichts aus.
Eine Meldung: sudoku nicht lösbar wäre ganz nett.

Gruß

JackF

Jack Falworth hat folgendes geschrieben:

dein algo scheint nicht alle unlösbaren sudokus zu erkennen, bzw nicht auszugeben, dass er sie erkannt hat. z.b. 1 2 3 4 5 -9 6 7 8 das sind erste und zweite spalte. der rest ist leer. Das Programm hängt sich entweder auf oder versucht irgendwas rumzurechnen oder gibt einfach nichts aus. Eine Meldung: sudoku nicht lösbar wäre ganz nett. Gruß JackF

Hi Jack,

danke für den Tipp. Eine Meldung mit "unlösbar" werde ich demnächst einbauen.

Das Prgramm zeigt bei dem o.g. Beispiel einfach nur "1 Step in 0 Millisec." an und scheinbar ist nichts passiert. Allerdings hat der Algorithmus auf der ersten Iterationsstufe bereits ein Feld entdeckt, in dem keine weiter Möglichkeit zum setzen eines Feldes existiert. Deshalb wird bereits nach einem Iterationsschritt (1 Step) erkannt, dass diese Sudoku keine Lösung haben kann.

Aber das ist natürlich nicht sonderlich benutzerfreundlich.

Gruß, Andreas

Hi,

so, die neue Version (V0.76) ist fertig (im ersten Eintrag aktualisiert).

Danke für die Anregungen von Chatfix, Jack und Quake User.

Falls keine Fehler mehr gefunden werden, würde ich (nach einigen kosmetischen Anpassungen) das Ganze auf 1.00 setzen und unter GPL veröffentlichen.

Hat jemand Erfahrung damit? Muss man irgendwelche Fallen/Tretminen beachten?

Gruß, Andreas