Die Generierungs-Routinen sind fertig. Schaut doch mal hier nach!

Horst_H hat folgendes geschrieben:

Meine Loesung sucht wie Jaenicke's Loesung einfach alle schon eindeutigen Belegungen von Feldern. Also fuer ein Feld fehlen in der Spalte[3,5,6] in der Zeile[1,3,6,8] und im Carree[2,5,6,8] dann ist die Schnittmenge daraus einelementig und enthaelt nur [6]. ALso kann nur [6] an diese Position. Durch eintragen dieser 6 , werden in der betroffenen Spalte,Zeile,Carree die Moeglichkeiten der anderen Spielfelder eingeschraenkter. Also wird das komplette Spielfeld solange nach eindeutigen Spielfeldern untersucht, bis keine mehr gefunden werden. Dies fuehrt schon oft zu einer Loesung. und wie mir auffaellt koennt man das auch mittels Backtracking alle Loenungen finden lassen.

Ich habe diese Idee durch eine weitere Heuristik erweitert, so dass ausnahmslos alle eindeutig lösbaren Sudokus auch gelöst werden können: Zusätzlich überprüfe ich nämlich ob eine Zahl die in einem Feld stehen kann, NUR in diesem Feld der entsprechenden Zeile/Spalte oder des Blockes stehen kann. Zusammen mit diesem Verfahren löst mein Algorithmus ein eindeutig lösbares Sudoku in weniger als einer Millisekunde bei ca. 2-5 kompletten (9x9-) Feld-Betrachtungen. Source ist allerdings weder kurz noch trivial, deswegen nur auf Anfrage.

Hallo!

Also jetzt funktioniert das Programm besser und generiert jetzt auch Sudokus. Ich habe jedenfalls kein Sudoku mehr gefunden, das das Programm nicht innerhalb von 5 Sekunden lösen konnte.

Homepage:
www.buchmanager-berl...ts/sudoku/index.html

Direkte Download-Links im ersten Posting.

Hmmm ich bastel auch grade an nem Solver

Der arbeitet nicht mit Bruteforce oder Random-Walk, sondern nur mit Logik.
Das Ganze ist recht schnell (Bruchteil einer Sekunde für jedes Rätsel),
nur mit nem halben MB etwas größer (Quelltext artet etwas aus).

Prinzipiell ist er eher gedacht um beim Rätseln zu assistieren, da er in ein Label alle seine
Schritte nacheinander begründet reinschreibt.

Und die etwas komplexeren Moves lassen sich per Checkbox abschalten, damit man nicht so durcheinanderkommt.
(Es sind noch nicht alle komplexen Moves enthalten die ich umzusetzen gedenke, aber das kommt noch)

www.fabiman.de.vu/SudokuSolv.exe

mfg Jetstream

@Jetstream:
Tja, aber anders als mein Solver löst er eben nicht jedes Rätsel, sondern trägt nur ein, was wo möglich ist. Und nur bei den einfachen Rätslen reicht das schon zum Lösen.
Das ist also ähnlich zu meiner alten Version.

Meine neue Version kann jetzt die meisten Rätsel lösen. Ich hab 4 ausprobiert, die hat dein Programm alle nicht gelöst, und bei mir gehen die in wenigen Millisekunden...

jaenicke hat folgendes geschrieben:

@Jetstream: Tja, aber anders als mein Solver löst er eben nicht jedes Rätsel, sondern trägt nur ein, was wo möglich ist. Und nur bei den einfachen Rätslen reicht das schon zum Lösen. Das ist also ähnlich zu meiner alten Version. Meine neue Version kann jetzt die meisten Rätsel lösen. Ich hab 4 ausprobiert, die hat dein Programm alle nicht gelöst, und bei mir gehen die in wenigen Millisekunden...

man kann sehr wohl alle eindeutig lösbaren sudokus nur mit logik lösen. das macht mein programm auch, und zwar in < 1 ms. wenn es eine eindeutige lösung gibt, wird diese auch gefunden. nicht eindeutig lösbare sudokus (also mit mehreren lösungen) spielen praktisch auch keine rolle, da niemand freiwillig sowas von hand löst.

nochmal explizit: ich will eigentlich nur sagen dass nicht nur EINFACHE sudokus mit purer logik lösbar sind, sondern alle die exakt eine lösung besitzen.

für mein programm guckst du mal hier:
www.delphi-forum.de/....php?p=322573#322573

jaenicke hat folgendes geschrieben:

Jetzt sollten fast alle Sudokus innerhalb von höchstens 5 Sekunden lösbar sein. Da würde mich aber mal interessieren, wie schnell das zweite mitgelieferte Beispiel bei den anderen hier im DF vorgestellten Löseprogrammen funktioniert (bei mir 2 Sekunden, AMD 3800er).

dein programm braucht dafür bei mir mehr als 8 sekunden (athlon XP 2600+). ausserdem ist dieses sudoku eben nicht eindeutig lösbar. die zeit die ein brute force algo braucht sollte maßgeblich von der zahl der unbestimmten felder abhängen bzw. von der anzahl der möglichen lösungen.

Also meiner Meinung nach IST dieses Sudoku eindeutig lösbar! Ich konnte keine Möglichkeit finden, eine weitere Lösung zu erzeugen (weder per PC noch per Hand)!

Luzzifus hat folgendes geschrieben:

man kann sehr wohl alle eindeutig lösbaren sudokus nur mit logik lösen. das macht mein programm auch, und zwar in < 1 ms. wenn es eine eindeutige lösung gibt, wird diese auch gefunden. nicht eindeutig lösbare sudokus (also mit mehreren lösungen) spielen praktisch auch keine rolle, da niemand freiwillig sowas von hand löst.

Bitte??? Dein Programm kann keines (der von mir getesteten jedenfalls) der schweren Sudokus der Zeit (zeit.de/sudoku) oder von anderen Internetseiten lösen!
Die haben aber doch nicht alle mehrere Lösungen. Die Anforderung an ein Sudoku geht ja auch dahin, dass es eine eindeutige Lösung haben muss. Und egal wo ich im Internet nachgesehen habe, überall gibt es Sudokus, die dein Programm nicht löst.

jaenicke hat folgendes geschrieben:

Bitte??? Dein Programm kann keines (der von mir getesteten jedenfalls) der schweren Sudokus der Zeit (zeit.de/sudoku) oder von anderen Internetseiten lösen! Die haben aber doch nicht alle mehrere Lösungen. Die Anforderung an ein Sudoku geht ja auch dahin, dass es eine eindeutige Lösung haben muss. Und egal wo ich im Internet nachgesehen habe, überall gibt es Sudokus, die dein Programm nicht löst.

hm ich habe lange zeit sudokus aus zeitschriften und sudoku büchern getestet und bisher konnte mein programm alle lösen. da ich nun aber kein zeit-leser bin werde ich mir das wohl doch nochmal genauer anschauen müssen. ^^ empirie reicht eben doch nicht immer

@ jaenicke
hast du bei meinem prog das 'advanced' häkchen angemacht ? damit schaffts n paar mehr.

da werden nochn paar zusätzliche routinen eingebunden.
wenn du aufs feld unten rechts klickst kannste dir das genau ansehen.

Oh, Ok, das hab ich übersehen. Sorry. Damit klappts wohl wirklich meistens. Hmm, da werd ich mal noch ein paar mehr testen.

So, die routinen sind eingebunden

das ganze zu bestaunen gibts hier: www.delphi-forum.de/...ku+Solver_54322.html

Hallo,

das Programm sollte anzeigen was es bisher herausbekommen hat.
Von diesem Beispiel mit eindeutiger Loesung
www.softgames.de/for....php?p=670521#670521
zeigt er nur >ungueltiges Spielfeld eingegeben<
wenn man bei Beispiel4 in Zeile 7 Spalte 6 die 9 loescht kommt die gleiche Anzeige.
>Kann ich nicht loesen< waere angebrachter.

Gruss Horst

bei meinem programm ?
schonmal auf solve gedrückt ?

Hallo,

uups, ich dachte ich haette die alte Version ueberschrieben.
Trotzdem ist die Ausgabe mehrere Loesungen gefunden falsch, denn es gibt nur eine.
Gruss Horst

dann hast du die advanced checkboxes nicht angemacht.
die beispiele schafft das programm alle.

Hallo,

mein Beispiel nicht.
Und wie gesagt, wenn man bei Beispiel diese 9 entfernt kommt die Meldung > keine < Loesung , statt mehrere???
Gruss Horst

Hallo,
da mich das Thema interessiert und auch gerade einen Solver am Schreiben bin, hab ich mir das ein oder andere Programm mal angeschaut.

Spontan habe ich bei dem Cocktail Programm (v1.5) zwei Sudokus gefunden, bei dem das Programm abschmiert (nur Unsinn ausgibt).
Erstes Sudoku: alle Felder sind leer
Zweites S.:

200000030
070000020
080000000
000000060
306000809
000000000
700000000
820000010
010000040

Das Sudoku hat keine Lösung.

Mein Programm ist zwar noch nicht das schnellste (braucht für das File im Anhang mit 100 solchen Sudokus) noch 5,5 Sekunden, aber es basiert noch ausschließlich auf dem Backtrack-Prinzip (mit mehreren Heuristiken).

Wenn ich demnächst das Setzen eindeutiger Felder über das Schnittmengenproblem einbaue und erst wenn nichts mehr geht auf Backtrack umsteige, sollte das Ganze nochmals deutlich schneller sein.
Halte euch auf dem Laufenden.

PS: Mich würde mal interessieren, wessen Programm das 100er File lösen kann und wie lange gebraucht wird (Tipp: 4 Sudokus davon haben keine Lösung)


Gruß

JackF

Hmm, also wenn es ein leeres Sudoku ist, dann sollte da eigentlich die Meldung kommen, dass sehr wenige Werte eingegeben wurden! Ich hielt es nicht für nötig da weitere Prüfungen einzubauen, denn wer trotz der Warnung fortsetzt muss wissen, was er da tut.

Das andere Sudoku werde ich mir mal ansehen!

Ich glaube so eine Meldung ist gekommen. Aber wieso? Das ist ein Computerprogramm, wieso sollte es solche Sudokus nicht lösen können? Dafür ist ein Solver ja da. Dein Programm kann irgendwie die selbst erzeugten Sudokus nicht lösen? Ist das noch ein Bug oder ist das nur bei mir so (Schwierigkeit war egal)?

In dem 100er File sind noch einige weitere Sudokus drin, die von den verschiedenen Programmen hier nicht gelöst werden können.
Das liegt daran, dass eure Algorithmen (allen Anschein nach) ausschließlich auf der Schnittmengen-Heuristik beruhen.
Damit kann man zwar die meisten Sudokus komplett lösen, andere aber nur teilweise oder gar nicht.


Edit: So habe mein Programm nun noch verbessert und u.a. die Schnittmengen-Heuristik hinzugefügt. Dadurch kann ich nun das
100er-File in stolzen 406 ms lösen

Die Meldung sollte nur bei sehr wenigen Eingabewerten kommen. (Ich meinte das in Bezug auf ein leeres Sudoku)

Und mein Programm versucht durchaus auch auszuprobieren (mittels Backtracking). Dass ein selbst erzeugtes Sudoku ncith lösbar ist, kann eigentlich gar nicht sein, denn der generator erkennt an der Lösbarkeit durch den eigenen Algorithmus die Gültigkeit (ich versuche schon serit Monaten ein besseres mathematisches Verfahren zu finden, aber bis jetzt haben mich meine Überlegungen nicht sehr weit gebracht, nur mit Hilfe von Permutationen scheint sich eine Lösung abzuzeichnen...)

Aber ich seh mir das nochmal an...