Im Urlaub habe ich (wiedermal) Sudoku für mich entdeckt. Da ich beim Lösen recht systematisch vorgegangen bin, habe ich mich gefragt, ob man diese langweilige Aufgabe nicht einem Computer überlassen könnte. Heute habe ich meine Ideen mal in Code gefasst und die Regeln, die mir im Urlaub geholfen haben implementiert.
Leider musste ich feststellen, dass mein Solver von Zeit zu Zeit in eine Sackgasse rennt und nicht weiterkommt. Prinzipiell könnte man solche festgefahrenen Situationen zwar mit ausprobieren und Backtracking lösen, jedoch wollte ich lieber versuchen die Lösung allein durch anwenden verschiedener Regeln zu produzieren. An dieser Stelle hänge ich im Moment - vielleicht gibt es ja draußen jemanden, der noch eine elementare Regel findet und mir (und dem Solver) auf die Sprünge helfen kann.
Cornelius responded on 16 Nov 2008 at 14:27 #
Hej Johannes,
nach einem kurzen durchblick durch deinen Solver ist mir folgendes aufgefallen:
Du scheinst nach Eindeutigen Kandiaten (nur eine Möglichkeit für das Feld) und nach nur einfach vorkommenden Kanditen (kann nirgendwo anders stehen) zu suchen.
Prinizipiell gibt es aber noch Gruppen, die du berücksichtigen kannst. Ich gebe da einfach mal ein Beispiel (gilt für Zeilen, Spalten oder (9er) Kästchen):
Angenommen es sind noch es gibt in einer Zeile/Spalte/Kästchen zwei Felder mit den Möglichketen A und B. Und ein drittes Feld hat die Moglichkeit A, B und C. In dem Fall muss das dritte Feld C enthalten, da A und B sich auf die ersten Beiden Felder verteilen und somit nicht im dritten Feld vorkommen können.
Das Ganze gilt auch für größere und komplexere Gruppen.
(A,B), (A,C), (B,C), ((A,B,C, _D_))
die ersten 3 Felder müssen A,B und C enthalten. Also können alle anderen Felder der selben Zeile/Spalte/Kasten diese nicht enthalten und damit in diesen Feldern von den “possible Candiates” ausgeschlossen werden.
Viel Spass beim implementieren
SmilingJ responded on 16 Nov 2008 at 14:36 #
Ja, die Methode kenn’ ich auch und wenn ich die Sudokus manuell (per Hand) löse, mach ich das manchmal auch so.
Ich habe aber festgestellt, dass sich diese Probleme darauf reduzieren lassen, dass man woanders was einsetzt.
Ich hab ja 2 Boards mit “// not explicit solvable?” drinne, bei denen ich nicht weiter weiß. Ich hatte das auch schon “ausgedruckt” und versucht per Hand zu lösen. Unter anderem auch mit der von dir vorgeschlagenen Lösung - diese hilft hierbei jedoch auch nicht weiter. Daher habe ich den Verdacht, dass die vorgeschlagene Regel redundant ist. (Bewiesen habe ich das noch nicht
Oder kommst du mit “deiner” Regel bei den problematischen Boards weiter und ich hab mich nur verguckt?!
Cornelius responded on 16 Nov 2008 at 18:39 #
Ja stimmt, ich hatte das auch mal versucht und hab mich da eben auch an deine “//not explicit solvable”s per hand gemacht und konnte die Lösen (zumindest einen Schritt weiter von dem was rauskommt wenn man die implemntierten Lösungsstrategien angewand hat).
Dann hab ich mir genau überlegt wie ich darauf gekommen bin, und hab das mal implementiert. Allerdings bin ich GUI-Faul
Das Ergebniss: Vergiss meinen vorherigen Kommentar… ist viel zu kompliziert und wie du schon sagtest hilft das nicht unbedingt.
Aber mit Methode 2 (später) hab ich das rausbekommen (ist dein zweiter Testfall):
4 9 6 3 2 8 1 5 7
2 8 3 1 5 7 6 9 4
5 7 1 9 6 4 8 2 3
3 1 9 5 7 2 4 8 6
8 6 5 4 9 3 7 1 2
7 2 4 8 1 6 5 3 9
6 5 7 2 8 9 3 4 1
1 4 2 6 3 5 9 7 8
9 3 8 7 4 1 2 6 5
Und die Methode funktioniert so:
_ _ _ _ _ 8 1 _ 7
2 8 3 1 5 7 6 9 4
_ 7 1 _ 6 4 _ _ 3
_ 1 9 5 7 2 _ _ 6
_ _ _ 4 9 _ 7 1 2
7 2 _ 8 1 _ _ _ _
6 _ 7 _ _ 9 _ 4 1
1 4 2 6 _ 5 _ 7 X
_ _ _ 7 4 1 2 6 _
Das ist was mit der konventioniellen Strategie rauskommt. Das Feld X ist aber bestimmt (8)!
Legende:
- 8 in der gleichen Zeile
| 8 in der gleichen Spalte
? möglich Positionen für 8
Nicht relevante Felder hab ich weggelassen:
_ | _ _ _ _ _ _ 7
_ 8 _ _ _ _ _ _ 4
_ | _ _ _ _ _ _ 3
_ | _ _ _ _ _ _ 6
_ | _ _ _ _ _ _ 2
- | - 8 - - - - -
6 | 7 _ _ _ _ 4 1
1 4 2 _ _ _ _ 7 X
? | ? - - - 2 6 -
Also bleibt in der rechten Spalte nur die Position X für die 8 übrig.
Der Punkt ist, dass ich die unterste Reihe ausschließen konnte, da in der linken unteren Box nur zwei Positionen für die 8 auf der letzen Reihe frei waren.
Und wenn man so “possible Candidates” reduziert kann man danach mit den vorherigen Methoden weiterarbeiten.
Cornelius responded on 16 Nov 2008 at 18:40 #
Ohje, das sieht ohne Kurier-Schrift und Leerzeichen aber nicht so gut aus ^^
SmilingJ responded on 16 Nov 2008 at 19:09 #
Na dann lass mal seh’n … den Code.. ich find Code besser zu lesen, als ein Beispiel
Zumindest, wenn er so geschrieben ist, wie man Code schreiben sollte - übersichtlich