Sudoku - page.mi.fu-berlin.depage.mi.fu-berlin.de/rote/Papers/slides/Sudoku-Berlin-2006.pdf · Sudoku-R¨atsel Einige Felder sind vorgegeben. Finde die ¨ubrigen Felder! Ein richtiges

Prof. Gunter Rote, Institut fur Informatik. SUDOKU, Studentenkolloquium, 6. 7. 2006

SUDOKU

423981756

758463219

916257348

584319627

692875134

137624985

375146892

841792563

269538471


SUDOKU

423981756

758463219

916257348

584319627

692875134

137624985

375146892

841792563

269538471 • Jede Zeile und

• jede Spalte

enthalt jeder Ziffer genaueinmal.


SUDOKU

423981756

758463219

916257348

584319627

692875134

137624985

375146892

841792563

269538471 • Jede Zeile und

• jede Spalte


• Jeder 3× 3-Block


Sudoku-Ratsel

Einige Felder sindvorgegeben.

Finde die ubrigen Felder!

Ein richtigesSudoku-Ratsel hat eineeindeutige Losung.

9 5 8123

17

846

1

5

48

43

2

9

87

149

5

7

68

2

17

2

6

3

71


Sudoku-Ratsel




Wo kann die 1 in diesem Block stehen?

9 5 8123

17

846

1

5

48

43

2

9

87

149

5

7

68

2

17

2

6

3

71


Sudoku-Ratsel





9 5 8123

17

846

1

5

48

43

2

9

87

149

5

7

68

2

17

2

6

3

71


Sudoku-Ratsel





9 5 8123

17

846

1

5

48

43

2

9

87

149

5

7

68

2

17

2

6

3

71

1


Sudoku-Ratsel




9 5 8123

17

846

1

5

48

43

2

9

87

149

5

7

68

2

17

2

6

3

71

1


Sudoku-Ratsel




9 5 8123

17

846

1

5

48

43

2

9

87

149

5

7

68

2

17

2

6

3

71

1

Welche Ziffer kann in diesem Feld stehen?

1 2 3 4 5 6 7 8 9


Sudoku-Ratsel




9 5 8123

17

846

1

5

48

43

2

9

87

149

5

7

68

2

17

2

6

3

71

1


1 2 3 4 5 6 7 8 9


Sudoku-Ratsel




9 5 8123

17

846

1

5

48

43

2

9

87

149

5

7

68

2

17

2

6

3

71

1


1 2 3 4 5 6 7 8 9


Sudoku-Ratsel




9 5 8123

17

846

1

5

48

43

2

9

87

149

5

7

68

2

17

2

6

3

71

1


1 2 3 4 5 6 7 8 9


Sudoku-Ratsel




9 5 8123

17

846

1

5

48

43

2

9

87

149

5

7

68

2

17

2

6

3

71

1


1 2 3 4 5 6 7 8 9

5


Keine Mathematik!


Keine Mathematik!


• Was ist Sudoku?

• ein bisschen Geschichte

• lateinische Quadrate und Stundenplane

• Losung als lineares Ungleichungssystem

• Losung durch logisches Schließen

• Losung durch Probieren

• Wieviele Sudoku-Gitter gibt es?

Uberblick


Geschichte

– Mai 1979: In Dell Pencil Puzzles & Word Gameserschienen die beiden ersten Sudoku-Ratsel unter demTitel Number Place.– Erfinder: Howard Garns, ein 74-jahriger ehemaligerArchitekt, gestorben 1989


Geschichte


– April 1984: Der japanische Ratsel-Verlag Nikoliverbreitet das Ratsel unter dem Namen suji wa dokushinni kagiru: Die Ziffern mussen einzeln stehen.


Geschichte


– April 1984: Der japanische Ratsel-Verlag Nikoliverbreitet das Ratsel unter dem Namen suji wa dokushinni kagiru: Die Ziffern mussen einzeln stehen.

Der abgekurzte Name Sudoku ist in Japan eingeschutztes Markenzeichen von Nikoli.

In japanischen Zeitschriften wird Sudoku daher oft mitdem englischen Namen Number Place bezeichnet.→ nan-ba-pu-re-su → abgekurzt nanpureProf. Gunter Rote, Institut fur Informatik. SUDOKU, Studentenkolloquium, 6. 7. 2006

Geschichte

– Der Neuseelander Wayne Gould (ein pensionierterRichter aus Hongkong) entwickelt in mehrjahrigerArbeit ein Computerprogramm zur Erstellung vonSudoku-Ratseln.

– Ende 2004 erscheinen die ersten Sudokus vonWayne Gould in der Londoner Times. Wenig spaterzieht der Guardian mit Sudokus von Nikoli nach.

– Marz 2006: erste Soduko-Weltmeisterschaft inLucca


Lateinische Quadrate

• Jede Zeile und

• jede Spalte


42

381756

75

863219

91

657348

58

419627

69

275134

13

724985

37

546892

84

192563

9 42 3 8 6 1 7

26

938471

53× 3-Blocke spielen keineRolle

erstmals 1783 vomMathematiker LeonhardEuler untersucht.


5

42

381756

7

863219

91

657348

58

419627

69

275134

13

724985

37

546892

84

192563

9

4

2 3 8 6 1 726

938471

5

123456789

9× 9× 9 Gitterwurfel

• Jede horizontale Zeile,

• jede horizontale Spalte, und

enthalt genau einen Knoten.

• jede senkrechte Saule

Lateinische Quadrate im Raum


123456789


Mo8

Mo9

Di 8Di 9

Mi 8

Mi 9

Do8

Do9

Fr8

• Jedes Fach in jeder Klassewird einmal unterrichtet.

• Zu jeder Stunde hat jedeKlasse Unterricht.

• Jedes Fach wird zu jederStunde in irgendeinerKlasse unterrichet.Deutsch

ErdkundeMathematik

EnglischMusikKunstPhysikSportBiologie

Stundenplane

Klasse:


123456789


Mo8

Mo9

Di 8Di 9

Mi 8

Mi 9

Do8

Do9

Fr8

• Jedes Fach in jeder Klassewird einmal unterrichtet.

• Zu jeder Stunde hat jedeKlasse Unterricht.

• Jedes Fach wird zu jederStunde in irgendeinerKlasse unterrichet.Deutsch

ErdkundeMathematik

EnglischMusikKunstPhysikSportBiologie

Stundenplane

Klasse:

• Varianten

• weitereNebenbedingungen


5

42

381756

7

863219

91

657348

58

419627

69

275134

13

724985

37

546892

84

192563

9

4

2 3 8 6 1 726

938471

5

123456789






Sudokus


5

42

381756

7

863219

91

657348

58

419627

69

275134

13

724985

37

546892

84

192563

9

4

2 3 8 6 1 726

938471

5

123456789







• Auch jede waagrechte3×3-Scheibe

Sudokus


Losung mit Variablen

xijk = 1, wenn Ziffer k in Zeile i, Spalte j stehtxijk = 0, sonst.

(i = 1, . . . , 9; j = 1, . . . , 9; k = 1, . . . , 9)



xijk = 1, wenn Ziffer k in Zeile i, Spalte j stehtxijk = 0, sonst.

(i = 1, . . . , 9; j = 1, . . . , 9; k = 1, . . . , 9)

In jeder Zelle steht eine Ziffer:

9∑k=1

xijk = 1, fur alle i, j (1)




9∑k=1


In jeder Zeile i kommt jede Ziffer k einmal vor:9∑

j=1

xijk = 1, fur alle i, k (2)

In jeder Spalte j kommt jede Ziffer k einmal vor:9∑

i=1

xijk = 1, fur alle j, k (3)



Im ersten 3× 3-Block kommt jede Ziffer k einmalvor:

3∑i=1

3∑j=1

xijk = 1, fur alle k, (4.1)

und analog in allen anderen 3× 3-Blocken.



9∑k=1


9∑j=1

xijk = 1, fur alle i, k (2)

fur a, b = 0, 1, 2; k = 0, . . . , 9

9∑i=1

xijk = 1, fur alle j, k (3)

3∑i=1

3∑j=1

x3a+i,3b+j,k = 1 (4)



9× 9× 9 = 729 Variablen xijk

4× (9× 9) = 324 Gleichungen



xijk ∈ {0, 1}

ersetzen durch0 ≤ xijk ≤ 1

→ System von linearen Gleichungen undUngleichungen (lineares Optimierungsproblem)

9× 9× 9 = 729 Variablen xijk

4× (9× 9) = 324 Gleichungen

52

1

6

38

1

8

3

6

673

81

41

823

7

8

7

1

7

296

81

2613

854

9

768

213

38

12679



52

1

6

38

1

8

3

6

673

81

41

823

7

8

7

1

7

296

81

2613

854

9

768

213

38

12679

9

6

4

7

4

4

9

5

4

7

9

2

5

9

6

9

6

5

4

2

5

3

4

3

7

9

5

4

4

5



xijk = 1/2

4

9

7

9

9

7

2 4

5 2

5

2

5

5

9

3

9

4

3

6

2

5

5

4

9

7

4

5

5

4

52

1

6

38

1

8

3

6

673

81

41

823

7

8

7

1

7

296

81

2613

854

9

768

213

38

12679

9

6

4

7

4

4

9

5

4

7

9

2

5

9

6

9

6

5

4

2

5

3

4

3

7

9

5

4

4

5



xijk = 1/2

4

9

7

9

9

7

2 4

5 2

5

2

5

5

9

3

9

4

3

6

2

5

5

4

9

7

4

5

5

4

Losen durch”logisches Schließen“

Ein gutes Sudoku soll durch durch direktes logischesSchließen, ohne Versuch und Irrtum, losbar sein.


Das Programm stammt hauptsachlich von David Eppstein(University of California at Irvine).

Losen durch Probieren

Systematisches Durchsuchen des Losungsbaumes,backtracking, Verzweigen





Ausgangsproblem

Ausfullen von Felderndurch Anwendung vonRegeln

An dieser Stelle kommt mandurch Regeln nicht weiter.Nehmen wir an, fur die Zellelinks oben gibt es zweimogliche Ziffern: 3 und 6




3 6




3 6

Ausfullen von Felderndurch weitere Anwendungvon Regeln




3 6

Ausfullen von Felderndurch weitere Anwendungvon Regeln

Sackgasse:An dieser Stelle geht esnicht mehr weiter.




3 6

2 3




3 6

2 3

Losung

Die Anzahl der Sudokus

Die Anzahl der verschiedenen Sudoku-Gitter ist

6670903752021072936960 ≈ 6,671× 1021

(6,671 Trilliarden).

(berechnet im Jahr 2005 von Bertram Felgenhauer(Dresden), Frazer Jarvis (Sheffield) und Ed Russell)

Diese Zahl ist 9!× 722 × 27 × 27 704 267 971.



Die Anzahl der verschiedenen Sudoku-Gitter ist

6670903752021072936960 ≈ 6,671× 1021

(6,671 Trilliarden).

(berechnet im Jahr 2005 von Bertram Felgenhauer(Dresden), Frazer Jarvis (Sheffield) und Ed Russell)

Zum Vergleich:Die Anzahl der 9×9 lateinischen Quadrate ist

5524751496156892842531225600 ≈ 5,525× 1027.

Diese Zahl ist 9!× 722 × 27 × 27 704 267 971.


Symmetrien

Umbenennung

1234...

↔ A↔ B↔ C↔ D

↔...

423981756

758463219

916257348

584319627

692875134

137624985

375146892

841792563

269538471


Symmetrien

Umbenennung

1234...

↔ ♥↔ ♣↔ ◦↔ �↔

...

↔ A↔ B↔ C↔ D

↔...

423981756

758463219

916257348

584319627

692875134

137624985

375146892

841792563

269538471


Symmetrien

Umbenennung

1234...

↔ ♥↔ ♣↔ ◦↔ �↔

...

↔↔↔↔↔

...

↔ A↔ B↔ C↔ D

↔...

423981756

758463219

916257348

584319627

692875134

137624985

375146892

841792563

269538471


Symmetrien

Umbenennung

1234...

↔ ♥↔ ♣↔ ◦↔ �↔

...

↔↔↔↔↔

...

↔ A↔ B↔ C↔ D

↔...

↔ 5↔ 8↔ 9↔ 6

↔...

423981756

758463219

916257348

584319627

692875134

137624985

375146892

841792563

269538471


Symmetrien

Umbenennung

1234...

↔ ♥↔ ♣↔ ◦↔ �↔

...

↔↔↔↔↔

...

↔ A↔ B↔ C↔ D

↔...

↔ 5↔ 8↔ 9↔ 6

↔...

Durch Umbenennung kann man das ersteKastchen in sortierte Reihenfolge bringen.

423981756

758463219

916257348

584319627

692875134

137624985

375146892

841792563

269538471

7

14 5

2

869

3

Ersparnisfaktor:9×8×7×6×5×4×3×2×1 = 9! = 362 880


Symmetrien

423981756

758463219

916257348

584319627

692875134

137624985

375146892

841792563

269538471 Vertauschung von Zeilen

oder Spalten innerhalbeines Dreierblockes


Symmetrien

423981756

758463219

916257348

584319627

692875134

137624985

375146892

841792563



Vertauschung von ganzenDreierblocken von Zeilenoder Spalten


Symmetrien

423981756

758463219

916257348

584319627

692875134

137624985

375146892

841792563



Vertauschung von ganzenDreierblocken von Zeilenoder Spalten

(Beliebige Zeilen oderSpalten durfen nichtvertauscht werden!)


Symmetrien

7

14 5

2

869

3 7 45 8 6 9

Durch Vertauschen vonSpalten erreicht man, dassdie beiden Dreiergruppenin der ersten Zeile sortiertsind.


Symmetrien

7

14 5

2

869

3 7 45 8 6 9

Durch Vertauschen vonSpalten erreicht man, dassdie beiden Dreiergruppenin der ersten Zeile sortiertsind.

7

14 5

2

869

3 4 6 9 75 8Durch Vertauschen vonDreierblocken (falls notig)bringt man dann diekleinste Ziffer (4) ganznach links.


Symmetrien

7

14 5

2

869

3 7 45 8 6 9456 789457 689458 679459 678467 589468 579469 578478 569479 568489 567

Es gibt nur mehr 10 Moglichkeitenfur die erste Zeile.

Reduktion von6× 5× 4× 3× 2× 1 = 720auf 10 Moglichkeiten.Ersparnisfaktor 72


7

14 5

2

8

Es gibt 36.288Moglichkeiten, die erstendrei Reihen zu fullen.46

912

375

8213

4 6 9 75 869

3



7

14 5

2

8


912

375

8213

4 6 9 75 869

3

7

14 5

2

8

Viele von diesenMoglichkeiten konnen aufgenau die gleiche Artvervollstandigt werden.

4691

2375

8 21

34 6 9 75 8

69

3



7

14 5

2

8


912

375

8213

4 6 9 75 869

3

7

14 5

2

8

Viele von diesenMoglichkeiten konnen aufgenau die gleiche Artvervollstandigt werden.

4691

2375

8 21

34 6 9 75 8

69

3

Die 32.666 Moglichkeiten lassen sich zu nur71 Klassen zusammenfassen. (eigentlich 44)



7

14 5

2

8 469

12

375

8213

4 6 9 75 869

3 einer von 71 Fallen


7

14 5

2

8 469

12

375

8213

4 6 9 75 869


Fur diese 6 Felder braucht manebenfalls nur 10 Moglichkeiten zubetrachten.

235 689236 589238 579239 568256 389258 369259 378268 359269 358289 356


7

14 5

2

8 469

12

375

8213

4 6 9 75 869


6

9

35

2

8

einer von 10 Fallen

Diesen Bereich kannman mit Probierenabzahlen.


7

14 5

2

8 469

12

375

8213

4 6 9 75 869


6

9

35

2

8

einer von 10 Fallen

Diesen Bereich kannman mit Probierenabzahlen.

Insgesamt werden∼7 000 000 000 Losungenabgegrast (mit∼130 000 000 000Sackgassen)

Laufzeit: einige StundenProf. Gunter Rote, Institut fur Informatik. SUDOKU, Studentenkolloquium, 6. 7. 2006

Es gibt neuere Methoden, die die Anzahl der Sudoku-Gitter in Bruchteilen einer Sekunde berechnen.


Es gibt neuere Methoden, die die Anzahl der Sudoku-Gitter in Bruchteilen einer Sekunde berechnen.

Unter Berucksichtigung von allen Symmetrien gibt es5.472.730.538 verschiedene Sudoku-Gitter.


Documents

Sudoku - page.mi.fu-berlin.depage.mi.fu-berlin.de/rote/Papers/slides/Sudoku-Berlin-2006.pdf · Sudoku-R¨atsel Einige Felder sind vorgegeben. Finde die ¨ubrigen Felder! Ein richtiges