ubuntuusers.de

Ich interessiere mich aktuell wieder für Lösungsalgorithmen weshalb ich mit einem Sudokusolver angefangen habe.

Das Ganze, so wie es aktuell implementiert ist, funktioniert ganz gut, nur schwere Sudokus kann das Teil nicht lösen. Dafür nutze ich aktuell das Backtracking-Verfahren, welches aber (und das ist mir eben erst aufgefallen) bei Sudokus natürlich verdammt langsam ist. Tja, blöd gelaufen.

Ich hab aktuell 3 Funktionen eingebaut:

• Es wird aufgrund der Regel, dass jede Zahl nur einmal vorkommen darf (pro 3x3 Feld und horizontale als auch vertikale Zahlenreihe) das Sudoku gelöst

• Sollte es mit der ersten Funktion nicht gelöst werden, kommt das Ausschlussverfahren zum Einsatz: Sollte in einem 3x3 Feld mehr als ein Feld frei sein, so wird versucht via Ausschlussverfahren eine eindeutige Zahl zu finden (ich erstelle eine Liste mit allen möglichen Zahlen und streiche alles weg, was nicht drin stehen darf. Bleibt exakt eine Zahl übrig: Glückwunsch)

• Ist das Sudoku dann immer noch nicht gelöst, so kommt Backtracking zum Einsatz. Um das Verfahren zu beschleunigen, nutzt Backtracking in den Zwischenschritten auch immer die ersten beiden Funktionen.

Leider ist Backtracking bei geschätzten 6,7 Trilliarden Kombinationsmöglichkeiten nicht unbedingt das Schnellste, welche Verfahren könnte man noch implementieren? Vielleicht ist auch meine Implementierung langsam (ist ja Python 😉 )

Hier mal ein Beispielsudoku, von dem ich nicht die Lösung besitze und welches eigentlich gelöst werden sollte:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

Sudoku:

 _ 3 4 | _ _ _ | _ _ 2
 6 7 2 | 1 9 5 | _ _ 8
 1 9 8 | _ _ _ | _ 6 7
-------+-------+-------
 _ 5 _ | 7 6 _ | 4 _ 3
 4 _ _ | _ _ 3 | _ _ 1
 _ _ _ | _ 2 _ | _ _ 6
-------+-------+-------
 _ 6 _ | _ _ _ | 2 8 4
 _ _ _ | 4 1 9 | _ _ 5
 _ _ _ | _ _ _ | _ 7 9

Press ENTER to continue with logical approach
Step: 0 	Leftover: 46
Step: 1 	Leftover: 38
Step: 2 	Leftover: 35

 5 3 4 | _ _ _ | 9 1 2
 6 7 2 | 1 9 5 | 3 4 8
 1 9 8 | _ _ _ | 5 6 7
-------+-------+-------
 _ 5 _ | 7 6 _ | 4 _ 3
 4 _ _ | _ _ 3 | _ _ 1
 _ _ _ | _ 2 _ | _ _ 6
-------+-------+-------
 _ 6 _ | _ _ 7 | 2 8 4
 _ _ 7 | 4 1 9 | 6 3 5
 _ _ _ | _ _ _ | 1 7 9

Press ENTER to continue with out procedure
Step: 3 	Leftover: 35

 5 3 4 | _ _ _ | 9 1 2
 6 7 2 | 1 9 5 | 3 4 8
 1 9 8 | _ _ _ | 5 6 7
-------+-------+-------
 _ 5 _ | 7 6 _ | 4 _ 3
 4 _ _ | _ _ 3 | _ _ 1
 _ _ _ | _ 2 _ | _ _ 6
-------+-------+-------
 _ 6 _ | _ _ 7 | 2 8 4
 _ _ 7 | 4 1 9 | 6 3 5
 _ _ _ | _ _ _ | 1 7 9

Press ENTER to continue with backtracking

Hat da jemand ne Idee? Das Sudoku wird intern übrigens so gehandhabt:

1
2
3
4
5
6
7
8
9

sudoku = [[0, 3, 4, 0, 0, 0, 0, 0, 2],
          [6, 7, 2, 1, 9, 5, 0, 0, 8],
          [1, 9, 8, 0, 0, 0, 0, 6, 7],
          [0, 5, 0, 7, 6, 0, 4, 0, 3],
          [4, 0, 0, 0, 0, 3, 0, 0, 1],
          [0, 0, 0, 0, 2, 0, 0, 0, 6],
          [0, 6, 0, 0, 0, 0, 2, 8, 4],
          [0, 0, 0, 4, 1, 9, 0, 0, 5],
          [0, 0, 0, 0, 0, 0, 0, 7, 9]]

Danke schonmal ☺

Hallo,

was heißt denn "langsam"? Minuten? Sekunden?

Selbst mit Prolog - welches ja für Sudokusolver prädestiniert ist 😉 - dauern schwere Sudokus ca. 10 - 15 s auf meinem Core2. Das war nur minimal schneller als ein Python Sudokusolver, denn ich damals im Internet gefunden hat. Frag' jetzt aber nicht, wie der hießt und wo ich den runtergeladen hatte... weiß ich nicht mehr. ☺

Gruß, noisefloor

noisefloor schrieb:

Hallo,

was heißt denn "langsam"? Minuten? Sekunden?

Vieeel länger. Sagen wirs so: Nach 15 Minuten hatte ich keine Lust mehr zu warten. Allerdings wurde das Ganze durch die Konsolenausgabe verlangsamt, gerade mal 460000 Mutationen des Ausgangssudokus (oder sagt man Rekrusionen? Naja, jedenfalls wurden 460000 Kombinationen durchprobiert)

Die Backtracking-Lösung ist ja im Prinzip BruteForce, das dauert vom Konzept her schon zu lange

Gruß, noisefloor

mfg ☺

Hallo,

habe mal "Backtracking python" bei Google eingegeben - da bekommt man bei den 1. Treffern auch ein Sudoku-Beispiel. Keine Ahnung, ob das gut ist. Kannst aber den Code ja mal mit deinem Vergleichen 😉

Gruß, noisefloor

noisefloor schrieb:

Hallo,

habe mal "Backtracking python" bei Google eingegeben - da bekommt man bei den 1. Treffern auch ein Sudoku-Beispiel. Keine Ahnung, ob das gut ist. Kannst aber den Code ja mal mit deinem Vergleichen 😉

Ich hoffe du meinst nicht das hier: http://www.linux-magazin.de/Heft-Abo/Ausgaben/2006/06/Mit-Methode-raetseln/(offset)/2 ?

Auf der ersten Seite wird ein 3x3-Sudoku gezeigt, das ist nicht unbedingt das, was ich will. Hab auch keinen interessanten Code entdecken können.

Werd ihn aber trotzdem mal probieren, sofern das lauffähig ist.

mfg

Ich habe mal ein Hilfsprogramm geschrieben, dass das, was ich im Kopf mache, programmatisch macht.

Es füllt alle Zellen, die nicht gelöst sind, mit allen Ziffern.

Dann streicht es die Ziffern, die horizontal, vertikal oder im Block schon auftauchen, weg. Bleibt nur noch eine Ziffer über, so ist die Zelle gelöst.

Es kann aber auch vorkommen, dass für die Zellen einer Zeile mehrere Mengen überbleien (3,4)(3,4)(3,4,5)(5,7,8)(5,7,8). Jetzt ist es so, dass in der ersten Zelle 3 oder 4 sein muss, woraus folgt, dass in der Zelle zwei 4 oder 3 sein muss, so dass in Zelle drei nicht 3,4,5 sein können, sondern nur noch 5. Analog kann man auch aus (3,4,5)(3,4,5)(3,4,5,6)(3,4,5) (4,5,6,7) feststellen, dass 3 Felder (3,4,5) determinieren, und Feld 3 daher nicht (3,4 oder 5) sein kann, sondern 6 sein muss.

Außerdem kann man sich auf die Suche nach Einzelkandidaten machen: Wenn in einer Zeile, Spalte oder einem Block eine Ziffer nur einmal als Kandidat auftaucht (letztes Beispiel: 7), dann muss die Zahl in dieser Zelle sein.

Nach jeder erfolgreichen Vereinfachung mit einer Methode kann man wieder die anderen ausprobieren.

Da ich nicht Python nutzte wird Dir der Code womöglich wenig bringen: http://home.arcor.de/hirnstrom/minis/index.html#sudoku

• Auf PyPI gibt es ein paar in Python geschriebene Sudoku-Löser, die du dir mal anschauen kannst.

• Ich würde ein intelligentes Backtracking mit den Lösungsstrategien kombinieren: Immer, wenn deine Strategien nicht weiterkommen, machst du als nächsten Backtracking-Schritt eine Annahmen über ein geschickt gewähltes Feld, z.B. eines, das in einer Zeile, Spalte o.ä. mit zwei Unbekannten liegt.

• Wenn du Mathematik magst: Möglicherweise findest du weiter Lösungs-Strategien, wenn du aus dem Sudoku ein Lineares Gleichungssystem (die Summe in jeder Zeile/Spalte usw. ist 45) ableitest, und dir dafür Lösungsalgorithmen suchst.

• Du kannst mal allgemein nach Lösungsstrategien für Constraint-Satisfaction-Problems suchen.

Danke für die Antworten.

Ich hab mir alles angesehen, ein paar hab ich aber nicht zum Laufen bekommen. Letztlich läuft es aber im Moment auf folgendes hinaus: Ich hab zu wenig Funktionen, die ein Sudoku logisch lösen. Dadurch wird bei mir Backtracking zu früh verwendet und naja, das dauert. Ich werd mal ein paar Sachen implementieren, mal sehen wie weit man damit kommt ☺

mfg