[quote=docsnyder,21.03.2007, 14:15]Na, ja, so ganz einfach ist bruteforce auch nicht: bis 9 Schleifen mit einem Laufindex von jeweils 362880 (wenn man das mit Permutationen von 123456789 macht) abgearbeitet sind, werden wir alt sein. Man muss sich schon überlegen, wie man die Geschichte sinnvoll abkürzt.[/quote]
Ich hab jetzt eine Brute-Force Lösung, die für das schwierigste SuDoKu, was ich finden konnte, 83 Sekunden braucht. Wobei der Algorithmus nicht stoppt, wenn eine Lösung gefunden wurde, um damit auch SuDoKus auf Lösbarkeit testen zu können. Allerdings habe ich auch mit Hilfe von Devel::DProf so weit optimiert wie es nur ging.

Ich werde nachher noch mal einen Ansatz mit RegEx testen. Mal schauen, ob ich das noch schneller bekomme...

@Taumarill

Kannst Du bitte die Anfangsbelegung Deines schwierigen Sudokus posten?

Würde es gerne mal durch mein Script jagen.

Gruss, Doc

5......169....7.......38....79........3.2.9........54....97.......3....768......1

Wenn jemand was mit weniger Vorgaben findet, kann er ja gerne mal posten. Ich bin übrigens überzeugt davon, dass es intelligentere Methoden, als meine gibt. Ich wollte nur gerne eine möglichst performante Brute-Force Lösung haben, um damit SuDoKus auf ihre Lösbarkeit hin zu testen. Die Idee ist halt, dass ein SuDoKu nicht lösbar ist, wenn mein Programm keine Lösung findet. Ferner sind SuDoKus nicht vollständig logisch lösbar, wenn es mehrere gültige Lösungen gibt.

@Taumarill

Gratuliere, mein Script braucht ganze 21 Minuten.

Muss da wohl noch optimieren ;o)

Gruss, Doc

Dann streng dich mal an, ich hab mich auf 65 Sekunden verbessert. Allerdings ist das natürlich auch Prozessorabhängig. Ich glaub das hier ist ein AMD 64 3700+ auf dem ich arbeite.

Mein halbfertiges braucht dafür eine Minute. (1GHz mit 512Mb RAM)\n\n

<!--EDIT|topeg|1174665581-->

Dann hast du dir wohl was schlaueres als Brute-Force einfallen lassen, oder? :)

Btw. bin jetzt bei 60 Sekunden...

So, meine Lösung ist raus und ich bin recht zufrieden. Die meisten Sudokus schafft es in unter einer Sekunde (auch das o.a.). Das einzige Sudoku, was noch länger braucht (c.a. 10 Sekunden) ist folgendes
........1.....2.3...4..5..........5......46...17.8........1...7.2.9.....5.....4..

Bin nochmal in mich gegangen und habe eine optimierte Lösung gebastelt und eingereicht.

@Taumarill

Ich liege bei der Eingabe von


bei 11 Sekunden auf einer Sun Ultra-250 (zugegeben, ein älteres Modell) und 3 Sekunden auf einer Sun-Fire-V240. Die Performance auf einem PC habe ich noch nicht getestet, aber das Ergebnis wird irgendwo dazwischen liegen.

Alle übrigen Eingaben, die ich getestet habe, liegen (wie bei Deiner Lösung) deutlich unter einer Sekunde.

Allerdings ist der Code auch deutlich länger geworden als der meiner ersten Lösung (die hatte nur 88 Zeilen inkl. Leerzeilen).

Ich wünsche ein schönes Wochenende!

Gruss, Doc

Also, hab's nochmal gebenchmarked:

Bei der Eingabe von


benötigt meine optimierte Lösung auf einem Celeron, 1,3 GHz, 512 MB nur 3 Sekunden. Alles andere von mir getestete unter 1 Sekunde.

Gruss, Doc