Moin, ich hab meinen Sudoku Solver jetzt soweit fertig.

Sudoku, was ist das ? de.wikipedia.org/wiki/Sudoku

Das Besondere an ihm ist sein Lösungsalgorithmus, der ganz ohne Randomizer und Backtracking funktioniert.



Er schreibt in jedes Feld im Ausgabegitter die möglichen Zahlen.

Man beachte die beiden 'Advanced' Checkboxes, mit denen sich (bei mir zumindest) jedes Rätsel,
das nur eine Lösung hat, lösen lässt.

Die einzelnen Schritte schreibt er dann in eine Extra Form,
die sich durch Klick auf den Button unten rechts aufrufen lässt.



Probierts einfach mal aus !

www.fabiman.de.vu/SudokuSolv.exe

Und sagt mir bitte Bescheid wenn er ein Rätsel nicht lösen kann, ich setz mich sofort dran

// Edit: Hab grade selber eins gefunden. Programm entsprechend verändert.

// Edit 2: Beispielknöpfe durch Combobox ersetzt.

// Edit 3: 'Advanced 2' um einiges schneller gemacht.

// Edit 4: Programm gemäß Born-to-Frags Vorschlägen verändert.

mfg Jetstream

Also ich muss sagen, er funktuioniert gut!

Was du vielleicht noch machen solltest, ist, dass man nur eine Zahl pro kästchen reinschreiben kann und er dann automatisch in das nächste springt. Dann kann man es so machen, dass man die zahlen eingibt und wenn was frei sein soll kann man 0 eintippen ( musst halt dann 0 als keine eingabe behandeln, habs nich getestet ob dus so gemacht hast).
Währe für die eingabe wesendlich schneller

greetz

Hallo Jetstream!

Also erstmal, Programm macht einen guten Eindruck!!

Wie Dein Programm ohne Probieren (und Backtracking) ausprobieren kann, wenn mehrere Zwischenlösungen möglich sind, verschließt sich mir völlig. Ich meine, es gibt doch Situationen, in denen für kein einziges leeres Feld eine eindeutige Lösung existiert. M.E. MUSS daraufhin einen systematische Suche innerhalb der Lösungsmöglichkeiten gestartet werden.

Bitte verrate doch, was sich konkret hinter "Advanced 1" und "Advanced 2" verbirgt. Noch besser wäre es, Du würdest kurze, prägnanten Beschriftungen für diese Comboboxen finden und Dein Programm dementsprechend ändern.

Gruß

Delphi-Laie

@Born to Frag:

thx für den Vorschlag, ich habs geändert. Bei Eingabe von Zahlen springt er jetzt automatisch
ein Feld weiter. Bei Enter löst er das Ereignis vom 'Solve'-Button aus.
Gibt man ein anderes Zeichen ein löscht er das Feld und springt ein Feld weiter.

@Delphi-Laie

lass doch mal mittels der 'Advanced'-Boxen (schlag nen besseren Namen vor)
ein Sudoku lösen und klick dann auf den Knopf unten rechts (da wo 'Eindeutige gültige Lösung gefunden' steht).

Dann öffnet sich Fenster wo du genau siehst was die beiden Advanced Boxen machen.

//Edit:

Ok, ich versuchs zu beschreiben:
Advanced 1 prüft, ob in einem Block eine bestimmt Zahl nur in einer Reihe vorkommt. Dann muss sie in der restlichen Reihe gelöscht werden.
Und umgekehrt prüft Advanced 1, ob in einer Linie eine Zahl nur innerhalb eines Blockes vorkommt. Dann wird sie im restlichen Block gelöscht.

Advanced 2 prüft, ob in einer Spalte/Zeile/Block zwei identische Felder mit zwei Möglichkeiten stehen. Diese beiden Zahlen werden dann in den restlichen Feldern gelöscht.
Und umgekehrt prüft Advanced 2, ob in einer Spalte/Zeile/Block zwei Felder die einzigen Möglichkeiten für zwei Zahlen sind.
zB Wenn in einer Zeile die Felder
'26','2367','5','9','4','2367','1','68','28'
stehen, so können die 3 und die 7 nur im zweiten und sechsten Feld stehen.

Also wird die Zeile auf
'26','37','5','9','4','37','1','68','28'
gesetzt.

Ich hoffe, das war verständlich

Super! Jetzt gefälts mir noch besser

@ Jetstream

Danke - das war verständlich!

Dein Programm ist wirklich gut, auch wenn man Sudokus mit Backtracking wesentlich schneller (und eindeutiger) lösen kann.

Mich würde mal interessieren wie du das Eingabegitter realisiert hast (mit welcher Komponente).

Eines stimmt noch nicht: Wenn man ein Gitter eingib, dass mehrere Lösungen hat, steht im Log "-=NOT SOLVED=-"

Und vielleicht noch eine kleine Veränderung: Ein drücken auf Backspace sollte die Eingabe löschen und ein Kästchen zurück, nicht wie bei den anderen Tasten eins vor..
Und ein drücken von Buchstaben etc. wo das Feld leer bleibt sollte dann auf dem gleichen kästchen bleiben

greetz

Hi!

Jo, das Programm ist an sich schon ganz gut. Die leichten und mittelschweren Sudokus kann er jedenfalls eindeutig lösen.

Anders sieht es da bei den üblichen "teuflisch" schweren Sudokus aus. Die haben erst recht eine eindeutige Lösung, dein Programm kann diese jedoch nicht bestimmen und erzählt einem etwas von mehreren Lösungen (die es nicht gibt *g*). Liegt wohl daran, dass teuflische Sudokus mit den von dir beschriebenen Methoden nicht gelöst werden können, da man bei diesem Schwierigkeitsgrad die Wahl bei einem Kästchen hat, um weiterkommen zu können. Wenn man die Zahl dann wählt, muss man schauen, ob man damit dann zu einer Lösung kommt. Bei teuflischen Sudokus landet man dann eigentlich IMMER in einer Sackgasse (und muss alle bisherigen Schritte bis zu der oben genannten Wahl zurückgehen) oder aber an einem weiteren Paar, wo man wählen muss.

Aber sonst ein gutes Programm

Gruß,
Da_Knuddelbaer

PS: Wer mal ein teuflisches Sudoku probieren will (zum selber lösen oder zum gucken was das Prog ausgibt):

8 _ _ 2 _ 9 _ _ 7
_ _ 9 3 _ 6 2 _ _
3 _ _ _ _ _ _ _ 6

_ _ 7 6 _ 1 3 _ _
_ 3 _ _ _ _ _ 5 _
_ _ 8 9 _ 3 6 _ _

1 _ _ _ _ _ _ _ 8
_ _ 3 1 _ 8 7 _ _
9 _ _ 4 _ 7 _ _ 3

Wie gesagt, es ist tatsächlich nur eindeutig lösbar!

Also erstmal ein dickes DANKE und ne Runde für alle die mir neue Verbesserunsvorschläge geliefert haben

@ MrFox :
Ich benutz ein ganz normales TStringGrid, über das ich mit Canvas dicke schwarze Linien zeichne. Da ich aber plane von vorne anzufangen, werde ich das ganze komplett mit Canvas machen.
Backtracking fand ich doof, da ich unbedingt die Übersicht über die Schritte haben wollte.

@ Born-to-Frag :
Mit "-=NOT SOLVED=-" wollte ich nur ausdrücken, dass die einzige Lösung (ich gehe stets davon aus, dass es nur eine Lösung gibt) nicht gefunden wurde. Ganz im Gegensatz zu "-=Solved=-"
Das mit den Tasten gefällt mir ganz gut wie es ist, aber eine Taste zum zurückspringen wäre wirklich ganz nett.

@ Knuddel :
Es gibt sooooo viele Techniken um Sudokus zu lösen
Ich hab mir zwar die, die im Programm sind, alle selber überlegt (hab im Urlaub ein Sudoku Buch geschenkt bekommen und immer fleissig geübt),
musste dann aber feststellen, dass das lediglich die einfachsten Techniken waren.
Ich werd irgendwann nen X-Wing und Swordfish Detektor einbauen, versprochen

Bin übrigens auch grade zu blöd um dein Sudoku zu lösen.

Mein Prog schaffts bis da hin:


Wer sieht die Lösung ?

mfg Jetstream

ich sehe eine:

865 219 437
719 346 285
324 875 196

597 681 324
631 724 859
248 953 671

176 532 948
453 198 762
982 467 513

Die Lösung an sich ist nicht das Problem.
Dafür muss ich nur Try-n-Error machen.

Ich will wissen welcher Schritt im Bild der nächste ist !

Mit Begründung bitte

//Edit:
Hab nen X-Wing gefunden.
Weiß nur net, ob der unbedingt weiterhilft.

Da in den Zeilen 2 und 4 die Zahl 8 nur in den Spalten 5 und 8 steht, kann sie in diesen beiden Spalten nirgends anders stehen.
Also streichen wir die Zahl 8 in den Feldern (5,3) und (8,3).

Was nu ?