Als der Sudoku-Virus zuschlug; Erlebnisse, Notizen, Spielereien im Umfeld der Theorie der koordinierten endlichen Mengen

Inhalt/ Content

1. Sudoku Virus
   
2. Sudoku Regeln
   
3. Sudoku Loesungsbedingung
   
4. Beispiel Nr.1
   
5. Einschub: ein paar Gedanken zur 3Band Theorie
   
6. Beispiel Nr.3 (Kamikaze)
   
7. Sudoku-Algorithmus II
   
8. Backtracking
   
9. Abhaengigkeitsgraph/ Dependency Graph
   
10. Neuer Loesungsalgorithmus III
    
11. Reference-Solutions by Thomas R.Davis
    
12. References and Links
    

Sudoku Infektion

Sudoku Regeln

1. Die Spielfäche ist ein Quadrat mit 9 Zeilen und 9 Spalten. Dieses Hauptquadrat ist wiederum in Unterquadrate so aufgeteilt, dass jedes Unterquadrat 3 Zeilen und 3 Spalten hat. Man bekommt auf diese Weise 9 Unterquadrate. 
2. In jeder Zeile dürfen die Ziffern 1, ..., 9 jeweils nur einmal vorkommen
3. In jeder Spalte dürfen die Ziffern 1, ..., 9 jeweils nur einmal vorkommen
4. In jedem Unterquadrat dürfen die Ziffern 1, ..., 9 jeweils nur einmal vorkommen
5. Ein Sudoku-Problem besteht aus einer Sudoku-Spielfläche und einer endlichen Zahl (0, ...,80) von Ziffern, die schon vorgegeben sind (nicht 81, da es dann nichts mehr zu tun gäbe...)
6. Ein Sudoku Spiel ist nun die Aktivität, bei der man, ausgehend von der Vorgabe möglicher Ziffern, versucht, nach möglichst kurzer Zeit eine Lösung zu finden, bei der kein Feld mehr frei ist und die Regeln (R1)-(R4) einhehalten wurden.

Sudoku Loesungsbedingung

Bild: Sudoku Rahmen

Notwendige Lösungsbedingung

Back tracking

Schwierigkeitsgrad

Beispiel Nr.1

Beispiel Nr.1 (Bonsai) (Teil 1+2)

Einschub: ein paar Gedanken zur 3Band-Theorie...

Beispiel Nr.3 ('Kamikaze')

Sudoku-Algorithmus, II

1. Eingabe einer 9x9 Matrix mit vorgegebenen Ziffern; Verteilung entsprechend Sudoku-Regeln.

2. Zeilenweise: Berechnung der Komplementmengen für die Zeilen (Z^-), für die Spalten (S^-), sowie wie für 3er-Quadranten (Q^-).

3. 3Bandweise: Anordnung der 3Bänder B1 - B3 entsprechend der 'Zifferndichte': Man beginnt mit dem 3Band mit der höchsten Zifferndichte. Falls alle gleich, dann 'von oben nach unten'. 

4. Zeilenweise innerhalb eines 3Bandes: Berechne für jedes Element der Zeile die Schnittmenge entsprechend Z_i^- geschnitten S_i^- geschnitten Q_i^-. Hinweis: Jede Zeile benötigt mindestens so viele verschiedene Ziffern ('angebotene Werte'), wie verschiedene Felder ('Lösungskandidaten') vorkommen! Ist diese Bedingung nicht erfüllt, kann es keine Lösung geben.

5. Falls Minimalbedingung für alle Zeilen des aktuellen 3Bandes erfüllt sind: Konstruiere für alle Zeilen des aktuellen 3Bandes eine Lösungsmenge indem (i) die  Schnittmengen jedes Elementes nach Mächtigkeit geordnet werden:  kleinste Mächtigkeit vor grösserer Mächtigkeit; (ii) eindeutige Werte erzwingen Auswahl und Setzung /*Erzwungen*/. (iii) Falls keine Lösungsmengen mit nur  1 Element  übrig bleibt, ist der Freiheitsgrad grösser als 1. In diesem Fall muss in Rechnung gestellt werden, dass eine aktuelle Auswahl zu einem späteren Zeitpunkt ('backtracking') revidiert werden muss.  Man wählt dann das Element mit dem kleinsten Koordinierungsgrad (KG)  im aktuellen 3Band aus (es kann auch hier die Möglichkeit geben, dass eine Eindeutigkeit dadurch gegeben ist, dass die Anzahl der Schnittmengen gleich ist der Anzahl der möglichen Werte, und zwar im Bereich Q oder S oder Z!). (iv) Jede Auswahl kann    zu Löschungen in anderen Schnittmengen führen (koordiniert über Unterquadrat Q, Zeile Z oder Spalte S).(v) Wiederhole 5.i - 5.iv bis entweder eine vollständige Lösung vorliegt oder aber die minimale Lösungsbedingung verletzt worden ist.

6. Wenn keine Lösung  möglich ist,dann Abbruch mit Fehlermeldung 'NO SOLUTION'.

7. Falls Lösung möglich ist und noch ein 3Band frei ist, dann gehe zum nächsten 3Band und mache weiter mit (5)

8. Falls Lösung möglich ist und kein 3Band mehr frei ist, dann Meldung 'SUCCESS'

 Fortsetzung Lösung Nr.3

Zifferndichte

1. 3Band B1 (Z1 - Z3): 8
2. 3Band B2 (Z4 - Z6): 11
3. 3Band B3 (Z7 - Z9): 8

Aufspannen des potentiellen Lösungsraumes

Resultierende Lösungsanforderungen:

Konstruktion einer Lösung

Aufspannen des potentiellen Lösungsraumes

Resultierende Lösungsanforderungen:

Konstruktion einer Lösung

--------------------------

Backtracking

Die generelle Idee ist die, dass man einen Startzustand  hat und mögliche Zielzustände (= SUCCESS) . Die Verbindung zwischen Startzustand und Zielzustände ist dadurch gegeben, dass man auf einen aktuellen Zustand bestimmte Operationen anwenden kann, die dann zum aktuellen Zustand Nachfolger (= children) erzeugen. Einer dieser Nachfolger ist dann entweder ein Zielzustand oder aber nicht. Wenn alle möglichen Nachfolger ausprobiert worden sind und kein Zielzustand gefunden wurde, dann gibt es keine Lösung (= FAILURE).

Die Verbindung von Tiefensuche und Backtracking wirkt sich dahingehend aus, dass der Algorithmus für jeden Knoten erst einmal Nachfolger sucht, unter diesen den ersten von links nach rechts auswählt, für diesen wieder Nachfolger sucht, solange, bis es keine Nachfolger mehr gibt oder zwischendurch ein Zielzustand auftrat. Findet sich kein Nachfolger mehr, dann werden zunächst die aktuellen Nachbarn  (= neighbours) aufgesucht. Für jeden Nachbarn wird dann die gleiche Strategie ausprobiert: erst alle möglichen Nachfolger bis man die nächsten Nachbarn aufsucht. Sind die aktuellen  Nachbarn verbraucht, dann versucht der Algorithmus eine Stufe (level) zurückzugehen, um über die unbesuchten Nachbarn dieser Stufe wieder seine Strategie von Nachfolgern zuerst und dann Nachbarn anzuwenden. Falls sich zwischendurch kein Zielzustand findet, wird dieser Algorithmus nach endlich vielen Schritten alle möglichen Knoten besucht haben. Dann stoppt er mit Misserfolg (= failure).

Ein Knoten im Lösungsgraphen (= solution graph) besteht in unserem Fall aus einem 9x9-Feld mit den bis zu diesem Zeitpunkt gesetzten Werten. Zusätzlich haben wir die drei Bänder geordnet nach ihrer Dichte mit einem Marker, der anzeigt, welches Band gerade in Bearbeitung ist. Schliesslich gibt es für alle noch nicht besetzten Felder des aktuellen Bandes die Menge der potentiellen Werte {X_i.j, .... } unter Berücksichtigung der Koordinierungen.

Eine mögliche Operationen ergibt sich aus einer  simultanen Auswahl plus Löschung von Elementen in den potentiellen Werten der Lösungskandidaten{X _i.j, .... }. Wenn für einen bestimmten Kandidaten X_i.j ein Wert w ausgewählt wird, dann muss dieser Wert  w zugleich in den potentiellen Lösungsmengen aller Kandidaten der gleichen Zeile, der gleichen Spalte sowie des gleichen Unterquadrates gelöscht werden. Ferner folgt aus der Auswahl, dass dieser Wert an der zugehörigen Stelle im 9x9-Feld neu gesetzt wird.

Führt die Anwendung einer Operation zu einem 9x9-Feld, in dem alle Felder korrekt besetzt sind, dann liegt eine Lösung vor, d.h. dieses Feld repräsentiert einen Zielzustand. 

Wenn wir dieses Konzept jetzt auf unser Beispiel an.

Lösungsversuch mit Tiefensuche und  Backtracking

X4.1 aus Z₄^- geschnitten mit  S₁^- geschnitten mit Q4^- =  {2,6,7,8}
X_4.2 aus Z₄^- geschnitten mit  S₂^- geschnitten mit Q4^- =  {2,7,8}
X_4.3 aus Z₄^- geschnitten mit  S3^- geschnitten mit Q4^- =  {2,5,6,7,8}
X_4.5 aus Z₄^- geschnitten mit  S₅^- geschnitten mit Q5^- =  {4,6,9}
X_4.7 aus Z₄^- geschnitten mit  S₇^- geschnitten mit Q6^- =  {4,5,6,8,9}
X_4.8 aus Z₄^- geschnitten mit  S₈^- geschnitten mit Q6^- =  {5,6,8,9}
X_4.9 aus Z₄^- geschnitten mit  S₉^- geschnitten mit Q6^- =  {8,9}
-------------------------------------------------------------------
X_5.4 aus Z₅^- geschnitten mit  S₄^- geschnitten mit Q5^- =  {5,6}
X_5.6 aus Z₅^- geschnitten mit  S₆^- geschnitten mit Q5^- =  {5,6}
-------------------------------------------------------------------
X6.1 aus Z₆^- geschnitten mit  S₁^- geschnitten mit Q4^- =  {6,8}
X_6.2 aus Z₆^- geschnitten mit  S₂^- geschnitten mit Q4^- =  {1,8}
X_6.3 aus Z₆^- geschnitten mit  S₃^- geschnitten mit Q4^- =  {1,5,6,8}
X_6.5 aus Z₆^- geschnitten mit  S₅^- geschnitten mit Q5^- =  {4,6,9}
X_6.7 aus Z₆^- geschnitten mit  S₇^- geschnitten mit Q6^- =  {3,4,5,6,8,9}
X_6.8 aus Z₆^- geschnitten mit  S₈^- geschnitten mit Q6^- =  {5,6,8,9}
X_6.9 aus Z₆^- geschnitten mit  S₉^- geschnitten mit Q6^- =  {3,8,9}

Abhaengigkeitsgraph/ Dependency Graph

Bild: Anordnung der Elemente aus den Mächtigkeiten als Abhängigkeitsgraph (dependency Graph)

Dies ist so zu lesen: wenn man 1 Lösungsmenge hat mit 9 Elementen, dann hat man 9 Varianten. Bei 2 Lösungsmengen mit jeweils 9 Elementen hat man 9x9=81 Möglichkeiten, usw. Bei 65 Lösungsmengen (= 65 Felder, die besezt werden sollten) mit jeweils 9 Möglichkeiten (was aufhrund von Koordinierung kaum geht) hätte man dann die astronomische Zahl 106.111.661.199.647 * 10⁴⁸. 

Natürlich wäre ein Algorithmus, der soviele Möglichkeiten ausprobieren sollte, nicht sehr schnell.... 

1. MMAX ist max.65
2. Nicht alle  Lösungskandidaten haben die Mächtigkeiten   9. 
3. Die Lösungskandidaten sind untereinander koordiniert.

Neuer Loesungsalgorithmus III: Abhängigkeitsgraph der Lösungskandidaten mit Koordination

Dazu müsste man jetzt die Menge der Lösungskandidaten auf alle Zeilen ausdehnen.

Problem:

Ordnen nach Mächtigkeit

Operationsmenge

 *2* X5:Z2,S5,Q2  =    {  3.    9.} m= 2
*1*X9 : Z4,S9,Q6 =   {  8.    9. } m= 2
 X4 : Z5,S4,Q5 =   {  5.    6. } m= 2
X6 : Z5,S6,Q5 = {  5.    6.} m=   2
 x1 : Z6,S1,Q4 =    { 6.    8. } m= 2
 X2 : Z6,S2,Q4 =  {  1.    8.} m=  2
 X9 : Z7,S9,Q9 = {  8.    9. } m=   2
 X5 : Z8,S5,Q8 =  {{   6.    9.} m=   2

 X6: Z1,S6,Q2 =   { 4.    7.    8. } m= 3
 X7: Z1,S7,Q3 =    {2.    3.    8.} m= 3
X8: Z1,S8,Q3 =    {2.    7.    8} m= 3
X6: Z2,S6,Q2 =    {  7.    8.    9.} m= 3
x1 : Z3,S1,Q1 =   {   2.    7.    8.} m=  3
 X2 : Z4,S2,Q4 = {  2.    7.    8.} m=   3
 X5 : Z4,S5,Q5 =   {  4.    6.    9.} m=  3
 X5 : Z6,S5,Q5 = {  4.    6.    9. } m=    3
X1 : Z7,S1,Q7 =   {  2.    6.    8.} m= 3
X4 : Z8,S4,Q8 =   {6.    8.    9.} m=  3
X6 : Z8,S6,Q8 =   { 6.    8.    9. } m= 3
 X9 : Z6,S9,Q6 = {  3.    8.    9. } m=   3

 X4: Z1,S4,Q2: =    { 2.    4.    8.} m= 4
 X3: Z2,S3,Q1 =    { 2.      7.    8.} m= 4
 X4: Z2,S4,Q2 =   {  2.     8.    9.} m=  4
X7 : Z2,S7,Q3 =    {   2.    3.    8.    9.} m= 4
X2 : Z3,S2,Q1 =    {  2.    4.    7.    8.} m= 4
 x9 : Z3,S9,Q3  = { 3.    7.    8.    9. } m= 4
 X1 : Z4,S1,Q4 =  { 2.    6.    7.    8. } m=  4
X3 : Z4,S3,Q4 =    { 2.    5.    6.    7.    8.} m= 4
X8 : Z4,S8,Q6 =  { 5.    6.    8.    9.} m=  4 
X3 : Z6,S3,Q4 =   {  1.    5.    6.    8.} m=  4
 X8 : Z6,S8,Q6 =  {  5.    6.    8.    9.} m=   4
X2 : Z7,S2,Q7 =    {   2.    4.    8.    9.} m= 4
 X3 : Z7,S3,Q7 =   {  2.    4.    6.    8. } m= 4
 X8 : Z7,S8,Q9 =   {  2.    6.    8.    9. } m= 4
 X3 : Z8,S3,Q7 =    {  2.    6.    7.    8.} m=  4
X7 : Z8,S7,Q9 =  {  2.    6.    8.    9. } m=   4
X2 : Z9,S2,Q7 = { 4.    7.    8.    9. } m=   4
 X3 : Z9,S3,Q7 =   {   4.    6.    7.    8.} m=  4
   X4 : Z9,S4,Q8 =  {   4.    6.    8.    9.} m=  4 
 X7 : Z9,S7,Q9 =   {  1.    6.    8.    9.} m=  4
 X8 : Z9,S8,Q9 =   {  6.    7.    8.    9. } m= 4

 X2: Z1,S2,Q1 =    {1.    2.    4.    7.    8.} m=  5
X3 : Z3,S3,Q1 =   {  2.    3.    4.    7.    8.} m=  5
 X6 : Z3,S6,Q2 =  {  4.    6.    7.    8.    9. } m=   5
X7 : Z3,S7,Q3 =  {  2.    3.    5.    8.    9. } m=  5
 X8 : Z3,S8,Q3 =   {  2.    5.    7.    8.    9.} m= 5
 X7 : Z4,S7,Q6 =   [ 4.    5.    6.    8.    9. } m= 5
 X7 : Z6,S7,Q6 =  {   3.    4.    5.    6.    8.    9} m=  5
X7 : Z7,S7,Q9 =  {  1.    2.    6.    8.    9.} m=   5
 X6 : Z9,S6,Q8 =   { 1.    4.    6.    8.    9.} m=  5

 X3: Z1,S3,Q1 =     { 1.    2.    3.    4.    7.    8.} m= 6
 X4 : Z3,S4,Q2 =    {  2.    4.    6.    8.    9. } m= 6
X4 : Z7,S4,Q8 =    {  3.    4.    5.    6.    8.    9.} m= 6
X6 : Z7,S6,Q8 = {   1.    4.    5.    6.    8.    9.} m=   6

-------------------------------------------------------------------------------------------

Ansatz zu Lösungsgraphen

Reference-Solutions by Thomas R.Davis algorithm:

Initial puzzle (kamikaze_1_tdformat.txt):

+---+---+---+
|9  | 5 |  6|
|56 |   | 41|
|   | 1 |   |
+---+---+---+
|   |1 3|   |
|439| 8 |712|
|   |7 2|   |
+---+---+---+
|   | 7 |   |
|15 |   | 34|
|3  | 2 |  5|
+---+---+---

........................

no other possibility: row: 9 column: 7 value: 8
Solved!
+---+---+---+
|971|254|386|
|562|837|941|
|843|619|527|
+---+---+---+
|725|143|698|
|439|586|712|
|618|792|453|
+---+---+---+
|284|375|169|
|157|968|234|
|396|421|875|
+---+---+---+
single possibility: 50
one in row/column/block: 24
coloring: 1
push[0] = 1

no other possibility: row: 9 column: 9 value: 5
Solved!
+---+---+---+
|637|254|189|
|459|186|327|
|128|937|546|
+---+---+---+
|596|721|834|
|371|548|962|
|284|693|751|
+---+---+---+
|942|375|618|
|865|419|273|
|713|862|495|
+---+---+---+
single possibility: 48
one in row/column/block: 4
locked candidates: 7

Initial puzzle (samurai_1_tdformat.txt):

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

.................

no other possibility: row: 9 column: 8 value: 9
Solved!
+---+---+---+
|456|721|389|
|173|498|265|
|928|365|741|
+---+---+---+
|215|679|834|
|894|532|176|
|367|814|952|
+---+---+---+
|589|247|613|
|641|983|527|
|732|156|498|
+---+---+---+
single possibility: 50

References and Links

1. Simon Armstrong. :This site points to some nice descriptions of solution techniques, most of which are also discussed in the paper of Davis. http://www.sadmansoftware.com/sudoku/index.html
2. Thomas R.Davis  (2006). The Mathematics of Sudoku. Email: tomrdavis@earthlink.net. URL: http://www.geometer.org/mathcircles. Paper: http://www.geometer.org/mathcircles/sudoku.pdf
3. Thomas R. Davis (2006). Programm zum Lösen von Sudokus: http://www.geometer.org/puzzles
4. Philip Dwinger. (1971) Introduction to Boolean Algebras. Physica-Verlag 
5. Bertram Felgenhauer, Frazer Jarvis (2005) Enumerating possible Sudoku grids. Department of Computer Science, TU Dresden, 01069 Dresden, Germany, bf3@mail.inf.tu-dresden.de  &  Department of Pure Mathematics, University of Sheffield, Sheffield S3 7RH, U.K. a.f.jarvis@shef.ac.uk 
6. Gideon Greenspan and Rachel Lee. This page by  generates sudoku games of varying degrees of difficulty and allows you to solve the problem online. http://www.websudoku.com/
7. Angus Johnson.  Page, where  you can download a program   that runs under Windows that will help you construct and solve sudoku problems. In addition, the page points to a step-by-step guide for solving sudoku, similar to what appears in the paper of Davis: http://angusj.com/sudoku/
8. Eytan Suchard, Raviv Yatom, and Eitan Shapir (2005). Sudoku & Graph Theory. Understanding graph theory is central to building your own Sudoku solver. Dr. Dobb's Journal. URL:http://www.ddj.com/184406436
9. Robin Wilson. (2005) How to solve sudoku: A step-by-step guide.  Oxford: The Infinite Ideas Company Limited
10. Wikipedia. Zur Mathematik der Sudokus: http://en.wikipedia.org/wiki/Mathematics_of_Sudoku
    
11. Robert Woodhead .  A downloadable program called Sudoku Susser for the Mac, Windows and Linux that will solve almost
    any puzzle using logic alone. The distribution comes with great documentation as well, that describes many of the techniques presented in the paper of Davis  and others besides. http://www.madoverlord.com/projects/sudoku.t: 
12. Takayuki YATO,Takahiro SETA ().Complexity and Completeness of Finding Another Solution and Its Application to Puzzles. Department of Information Science Graduate School of Science, The University of Tokyo, yato@is.s.u-tokyo.ac.jp & Department of Computer Science, Graduate School of Information Science and Technology, The University of Tokyo, seta@is.s.u-tokyo.ac.jp
13. http://www.setbb.com/phpbb/index.php: This page is a forum for people who want to solve and construct sudoku puzzles as well as for people who want to write computer programs
    to solve sudoku automatically.
14. Sudoku Forum:  http://www.sudoku.com/forums
15. Sudoku Probleme zum testen: http://www.websudoku.com/
16. Weitere Links:  http://www.sudocue.net/guide.php 
17.  http://www.paulspages.co.uk/sudoku/howtosolve/index.htm 
18.  http://www.sadmansoftware.com/sudoku/techniques.htm 
19.  http://www.scanraid.com/BasicStrategies.htm 
20.  http://www.stolaf.edu/people/hansonr/sudoku/explain.htm 
21.  http://homepages.cwi.nl/~aeb/games/sudoku/ 
22.  Some good Sudoku puzzle solvers can be found at
      ----- http://www.angusj.com/sudoku/
      ----- http://magictour.free.fr/sudoku.htm 
23.  Several of the many good sites to find Sudoku puzzles include:
      ----- http://www.sudoku.com.au/
      ----- http://www.sudoku.org.uk
      ----- http://www.websudoku.com
      ----- http://www.sudocue.net/daily.php 
24. The Basics (Sudoku without candidates)
          http://palmsudoku.com/pages/techniques-overview.php
          http://www.puzzle.jp/keys/sudoku_mid02-e.html
          http://www.conceptispuzzles.com/products/sudoku/solution_examples.htm