Sudoku algorithmus

Hi Alexej,
mich würde der Code interessieren. Wäre Dir für posten dankbar, bzw. um anderen nicht den Spaß zu nehmen, gerne an uw(ät)dipbach.de - ist schone korrekt ohne e.

Gruß,
Uwe

Entenwickler

Schwere Sudokus sind so aufgebaut, dass du verausdenken musst:
„Wenn ich hier eine 5 mache, muss ich dort eine 3 machen, dann muss die 3 dort hin, und das geht nicht -> keine 5 einsetzen, sondern die andere Möglichkeit“

Genau das kannst du am PC nur doch probieren simulieren. Ich würde es so versuchen, dass der sichere Algrithmus solange arbeiten darf, bis er nicht mehr weiter weiß, dann wird probiert (Backtracing).

Phoemuex

glinux schrieb:

Übrigens funktionieren die meisten Online Löser auf diese weise. Bei eindeutigen Lösungen ist die Peformance im millisikunden bereich. Bei Matrizen mit meheren Lösungen und ungünstiger belegung kann der Code schon mal 30 Sekunden arbeiten.

Entschuldige, aber das hört sich nicht nach einer optimalen Lösung an... Ich habe einen Sudoku-Solver in Python (interpretiert) geschrieben und der löst auf meinem Athlon 3000+ JEDES Feld, das ich bisher probiert habe in unter 3 Sekunden. Und ich habe auch ein KOMPLETT leeres Feld probiert ^^ ne ungünstigere Belegung geht ja wohl nicht mehr.

Vorgegangen wird nach dem logischen Ausschlussprinzip und wenn man damit nicht mehr weiter kommt, wird Backtracking hinzugenommen.

Bei Interesse kann ich den Code mal posten, ich hab das Ganze auch in C++, da allerdings ohne GUI

An dem Generator für Sudokus arbeite ich gerade noch, der ist allerdings etwas langsamer, d.h. es kann bis zu 10 Sekunden dauern

Felix

Hallo zusammen,

das Grundprinzip zum Lösen ist recht einfach.
Du speicherst dir für jede Zelle, die möglichen Zahlen.
Du initialiesierst jede Zell mit allen Zahlen.
Jetzt fängst du an die vorgegebenen Zahlen einzutragen.
Wenn du eine Zahl einträgst, löschst du diese Zahl in deinem Quadrat,
Zeile und Spalte für die übrigen Felder, zudem marikierst du dir dieses
Feld als gelöst. Wenn du jetzt alle vorgegebenen Zahlen eingetragen hast.
Läufst du das Spielfeld durch und sucht, ob in einer Zelle (die nicht als
gelöst markiert ist) nur noch ein Wert möglich ist oder diese Zahl in allen
anderen Zellen der Zeile / Spalte / Quadrat ausgeschlossen ist. Irgendwas wirst
du in der Regel finden. Die kannst du dann wie am Anfang eintragen.
Irgendwann wirst du möglicherweise den Fall haben, dass du irgendwann mit
diesen Mitteln nicht weiterkommst. Wenn du so weit bist, kannst du dann ja
mal wieder schreiben.

Dann mußt du etwa so etwas weiter eingrenzen:
Bsp.: (2,3,4,5) , (2,3,4,5), (1,4,5), (4,5) , (1,5)
Das kannst du auf (2,3) (2,3), (1,4,5), (4,5), (1,5) reduzieren

Da mußt du für alle Teilmengen von Zahlen, alle Felder suchen, in denen sie
vorhanden sind. Falls die Anzahl der gefundenen Felder gleich der Größe der Menge ist, kannst du die restlichen Zahlen in den Feldern löschen.
(Natürlich wieder für alle Zeilen Spalten, Quadrate)
Im Prinzip ist das ne Veralgemeinerung der oberen Verfahren.

Ob du damit alle eindeutigen SuDokus lösen kannst, weiß ich nicht, aber
ziemlich viele.

Gruß,
SuDokuSolver

PS: Ich hoffe ich, ich hab nix vergessen

Warum sollte man einen schlauen Algo schreiben, wenn man es mit probieren in wenigen ms hin bekommt?

Bei einfachen

groovemaster

Toniiii schrieb:

Warum sollte man einen schlauen Algo schreiben, wenn man es mit probieren in wenigen ms hin bekommt?

So ein Algorithmus muss sich ja nicht immer auf das typische 9x9 Sudoku beziehen. Du kannst das Spielfeld fast beliebig vergrössern. Dann werden aus Millisekunden mal ganz schnell Sekunden oder Minuten.