Sudoku-Rätsel und Rainbow-Looms Burkhard.Wald@Uni-DuE.de ... · Sudoku-Rätsel möglich sind, dann...

1

Burkhard Wald

Sudoku-Rätsel und Rainbow-Looms

Burkhard.Wald@Uni-DuE.de

November 2015

2

Burkhard Wald

Nachträglich eingefügte Seite

• Seiten mit dem Titel „Nachträglich eingefügte Seite“ wurden von mir nachträglich eingefügt um den Gebrauchswert der Folien zu erhöhen. Manches würde sonst etwas unverständlich und zusammenhanglos wirken, wenn das gesprochene Wort des Vortrages.

Burkhard Waldburkhard.wald@uni-due.dehttps://www.uni-due.de/zim/burkhard.wald

3

Burkhard Wald

Nachträglich eingefügte Seite

• Abstract: Rätsel sind das populärwissenschaftliche Bindeglied zwischen den Problemen des Alltags (oder auch des Berufslebens) und der Mathematik.

Sudokus sind hier ein Beispiel. Zuerst hat man eine scheinbar unübersichtliche Menge von Möglichkeiten, doch nach und nach kann man Möglichkeiten ausschließen und manche Möglichkeiten werden zu Gewissheiten. Wie läuft das ab und wie schwierig können Sudokus sein? Wir nutzen die gefärbten Gummibänder um dem "Markt der Möglichkeiten" Struktur zu geben.

Sorry, wir werden keine Armbänder knüpfen.

4

Burkhard Wald

Nachträglich eingefügte Seite

• Als Entschädigung dafür, dass wir nicht wirklich über Rainbow-Looms reden wollen hier zwei Links

– https://www.youtube.com/watch?v=DqknSI67lkY

– https://anjasschnipselkiste.wordpress.com/2014/07/17/anleitung-fur-ein-rainbow-loom-luftmaschenarmand-oder-single-chain-bracelet-auf-einer-gabel/

• Im mathematischen Sinne (Topologie) sind die Rainbow-Looms nicht wirklich verknüpft; wie z.B. die Borromäischen Ringe

– https://de.wikipedia.org/wiki/Borrom%C3%A4ische_Ringe

5

Burkhard Wald

Soduko-Vorlage für Cut&Paste

6

Burkhard Wald

Das ausgeteilte Beispiel

4 5 7

8 2 3

9 1 6

6 3 2

1 9 7

5

1 9 8

5 6 4

2 7 3

5 6

7 1

3 4 2

7 3

2 4

5 1 6

4 2 1

6 3 5

7 8 9

6 3 5

2

1 7

7 8 1

6 5

3 2

9 4 2

3 1 7

8 5 6

7

Burkhard Wald

Sudokus

• In einem Schema von 9x9 Einzelfeldern die zusätzlich in 9 3x3-Blöcke eingeteilt sind, müssen die Zahlen von 1 bis 9 so eingetragen werden, dass am Ende in jeder Zeile, jeder Spalte und jedem Block jede Zahl genau einmal vorkommt.

• Bei einem Sudoku-Rätsel sind mache Felder vorbelegt, sodass es nun eine einzig richtig Ergänzung aller anderen Felder gibt. Diese gilt es zu finden.

• Drei Fragen:

– Wie schwierig können Sudokurätsel sein?

– Wie verschieden können Sudokurätsel sein?

– Wie verschieden sind die möglichen voll ausgefüllten Schemen?

8

Burkhard Wald

Die Menge der Möglichkeiten

• Man hat 9*9*9 = 729 Variablen x_nij die die Werte „true“ und „false“ (1 und 0) annehmen können.

• x_nij besagt „in Zeile i, Spalte j steht die Ziffer n.

• Der Raum der Variablen ist durchspannt durch eine Menge von Teilmengen:

– Alle Möglichkeiten eine Ziffer n in einer Zeile i

– Alle Möglichkeiten einer Ziffer n in eine Spalte j

– Alle Möglichkeiten einer Ziffer n in einem Block

– Alle möglichen Ziffern in einen Einzelfeld

• Diese 4*9*9 = 324 Mengen der Mächtigkeit 9 nennen wir Looms

9

Burkhard Wald

Looms

• Die Bedingung für Sudokus besteht darin, dass in jedem Loom eine Variable den Wert 1 hat und alle anderen den Wert 0.

• Arithmetisch bedeute das, dass die Summe der Werte der Variable 1 ergeben muss.

• Irgendwie ist Sudoku auch ein „Damenproblem“

• Spielverlauf:

– Kann eine Variable zu 0 entschieden werden, kann sie aus dem Spiel entfernt werden.

– Kann eine Variable zu 1 entschieden werden, entscheiden sich alle anderen Variablen der beteiligten Variablen zu 0. Alle beteiligte Looms können samt Inhalt entfernt werden.

10

Burkhard Wald

Nachträglich eingefügte Seite

• „Damenproblem“ bezieht sich auf die Problemstellung auf einem Schachbrett acht Damen so zu platzieren, dass Sie sich nicht gegenseitig schlagen können.

• „Spielverlauf“ meint das schrittweise Lösen eines Sudokus. Dabei entscheiden sich die boolschen Variable nach und nach als wahr oder falsch. Dann können sie aus dem „Spiel“ „entfernt“ werden.

11

Burkhard Wald

436

836

493

996

484

496

434984

483

993

983982

834944

844

956

856

943883882

843

952

852

12

Burkhard Wald

13

Burkhard Wald

Nachträglich eingefügte Seite

• Dieses Bild (1969) hängt im Folkwang-Museum und ist von dem Maler Peter Brüning

– https://de.wikipedia.org/wiki/Peter_Br%C3%BCning

14

Burkhard Wald

Lösungswege

• Ein „Single“ ist ein Loom mit nur einem Element

• Wir nennen ein Sudokurätsel „trivial“ wenn es durch Auflösen von Singles lösbar ist.

• Subset-Regel• Doppelpaar-Regel• Ketten von Paaren

15

Burkhard Wald

Beispiel Subset-Regel

7

7 4 9

8

8

7

1

1

7

5 3

1

6 2

5 9

7 1 4

9

1

2

4

3 5 1

3

Betrachte die Möglichkeiten für die Ziffer 2.Die Graue Felder können ausgeschlossen werden.

Hier sind zwei Looms im Spiel: L1 besteht aus den Möglichkeiten der 2 in der zweiten Spalte (die grünen und grauen Felder). L2 sind die Möglichkeiten der 2 im vierten Block. (die grünen Felder). L2 ist eine Teilmenge von L1. Die Differenzmenge der beide Looms (grauen Felder) kann ausgeschlossen werden.

L1: x212 + x222 + x232 + x252 + x262 = 1L2: x252 + x262 = 1L1-L2: x212 + x222 + x232 = 0Also: x212 = 0, x222 = 0, x232 = 0

16

Burkhard Wald

Beispiel für Doppelpaar-Regel

5 3

1

2

6 5

3

6

3 1

7 5

8

3

1

3 7

4

2

6

3 6

2 8

4

7

5 3

2

8

7

In den blauen Felder sind nur die Ziffern 8 und 9 möglich.In den grauen Feldern kann 8 und 9 ausgeschlossen werden.

Wir betrachten die folgende Looms:L1 seien die Möglichkeiten der 8 in Spalte 4.L2 seien die Möglichkeiten der 9 in Spalte 4.Diese Loom sind verbunden durch die Paare P1 (alle Möglichkeiten für Feld [2,4]) und P2 (alle Möglichkeiten für Feld [3,4])

L1: x814 + x824 + x834 + x844 = 1L2: x914 + x924 + x934 + x944 = 1P1: x824 + x924 = 1P2: x834 + x934 = 1L1+L1-P1-P2: x814 + x844 + x914 + x944 = 0Also: x814 = 0, x844 = 0, x914 = 0, x944 = 0

17

Burkhard Wald

2. Beispiel für Doppelpaar-Regel

9

5

3

6 2

3

5

7

6

7

8 2

3

9

4 5 9

3

4

1

5 1 2 8

5

Für Ziffer 1 gibt es zwei parallele Paare.

In den grauen Feldern kann die 1 ausgeschlossen werden.

L1 (die 1 in Zeile 2)L2 (die 1 in Zeile 5)P1 (die 1 in Spalte 1)P2 (die 1 in Spalte 5)

L1: x121 + x124 + x125 + x127 + x129 = 1L2: x151 + x153 + x154 + x155 + x157 + x159 = 1P1: x121 + x151 = 1P2: x125 + x155 = 1L1+L1-P1-P2: x124 + x127 + x129 + x153 + x154 + x157 + x159 = 0Also: x124 = 0, x127 = 0, x129 = 0, x153 = 0, x154 = 0, x157 = 0, x159 = 0

18

Burkhard Wald

Gefärbte Loom-Strukturen• Für das Lösen eines Sudokus ist es völlig uninteressant, ob ein Loom

die Möglichkeiten einer Zahl in einer Zeile, einer Spalte oder einem Block sind oder ob es die möglichen Zahlen in einem Feld sind.

• Stellt man aber die Frage welche Loom-Strukturen überhaupt als Sudoku-Rätsel möglich sind, dann ist es sehr wohl interessant, die Art der Looms zu unterscheiden.

• Jeder Loom ist einer von 4 Farben zugeordnet: Blau (Zeilen), Rot(Spalten), Gelb(Blöcke) und Schwarz(Felder)

• Die Looms einer Farbe bilden eine disjunkte Überdeckung der Grundmenge. (Jeder Punkt ist in genau einem Loom jeder Farbe)

• Zwei Looms unterschiedlicher Farbe schneiden sich in höchsten einem Punk; allerdings mit zwei Ausnahmen: ein blaues und ein gelbes Loom, sowie ein rotes und ein gelbes Loom können mehrere gemeinsames Elemente besitzen.

• 4. Von jeder Farbe gibt es gleich viele Looms

19

Burkhard Wald

Lemma

• Jedes eindeutig lösbare Sudoku-Rätsel, das keine Looms hat, die größer als 2 sind ist trivial lösbar.

• Wenn bei einem Sudoku ohne Single für eine Farbe die Looms nur aus Paaren bestehen, dann gilt das auch für alle anderen Farben. (Es kann dann nicht eindeutig sein)

• Wenn ein Sudoku ohne Singles nur Looms der Länge 2 und 3 hat, so haben alle Farben gleich viele Paare und gleich viele Dreier-Looms.

20

Burkhard Wald

Theorem

• Es gibt ein nicht-triviales Sudoku mit 11 offenen Felder und alle mit dieser Eigenschaft (mit 11 offenen Feldern) sind nach dem gleichen Schema aufgebaut.

• Alle eindeutig lösbaren Sudokus mit weniger als 11 offenen Feldern sind trivial.

• Zwei Fragen:– wie habe ich das gefunden?– wie beweist man das?

• Alle 4x4-Sudoku-Rätsel sind trivial.

21

Burkhard Wald

Nachträglich eingefügte Seite

• Ausgangspunkt war diese Liste mit 49151 Sudokushttp://staffhome.ecm.uwa.edu.au/~00013890/sudoku17die von

• Diese wurden mit einem einfachen Sudoku-Solver, der nur triviale Sudokus lösen kann, analysiert.

• Der Solver wurde mit Perl programmiert und konnte in der Uni-Kommandozeile benutzt werden.

• Der Beweis, dass kleinere Sudokus trivial oder nicht eindeutig sind, ist ein aufwendige Durchchecken verschiedener Fälle.

• Dadurch kommt man schließlich zu der Aussage, dass mindestens 5 Blöcke beteiligt sein müssen.

• Aus vorherigen Überlegungen ergibt sich, dass jeder Block mindestens 2 freie Felder haben muss, und einer sogar 3. Daraus ergibt sich eine Zahl größer gleich 11.

22

Burkhard Wald

Anzahl der vollständig ausgefüllten Sudokus

• Bertram Felgenhauer, Frazer Jarvis, Ed Russell

• 6.670.903.752.021.072.936.960 (ca. 6,7 Trilliarden oder 6,7 * 10^21)

• 9! = 362880 Möglichkeiten für eine(n) Block, Zeile Spalte

• 18.383.222.420.692.992 Möglichkeiten wenn ein Block fest ist(18 Billarden oder 1,8 * 10^16)

• 5.472.730.538 die im Wesen verschieden sind (5,5 Milliarden oder 5,5 * 10^9)

23

Burkhard Wald

Gruppe

Eine Gruppe ist eine Menge auf der ein interne Verknüpfung definiert ist. Ist G die Menge und * die Verknüpfung, so muss gelten

• f*(g*h) = (f*g)*h für alle f,g,h aus G• Es gibt ein Element e in G mit

g*e = g und e*g = g für alle g aus G (Einselement)• Zu jedem g aus G gibt es ein h aus G mit

g*h = e und h*g = e (inverses Element)• (Einselement und inverses Element zu g sind zwingend

eindeutig)

24

Burkhard Wald

Gruppe G operiert auf Menge X

Zu jedem x aus X und jedem g aus G ist ein Element x^g definiert. Es müssen folgende Bedingung gelten

• x^e = x• (x^g)^h = x^(g*h)

25

Burkhard Wald

Symentriegruppe von Sudokus

• Vertauschungen der Ziffern 1 … 9

• Vertauschungen von Zeilen in einem Dreierblock von Zeilen

• Vertauschungen der Dreierblöcke von Zeilen

• Vertauschungen von Spalten in einem Dreierblock von Spalten

• Vertauschungen der Dreierblöcke von Spalten

• Drehungen um 90, 180 und 270 Grad

• Diagonale Spiegelungen

• Kombinationen aus all dem

• Das sind 9! * (3!)^8 * 2 = 362880 * 3359232 = 1218998108160 viele Elemente (ca 1,2 Billionen oder 1,2 * 10^12)

• Diese Gruppe operiert auf den Sudokus (Rätsel oder voll ausgefüllt)

26

Burkhard Wald

Orbits

• Wenn eine Gruppe auf einer Menge operiert, zerfällt die Menge in disjunkte Teilmengen, den Orbits.

• In den Orbits sind alle Elemente untereinander „erreichbar“ (x erreicht y, wenn x^g = y)

• Elemente verschiedener Orbits können sich gegenseitig nicht erreichen

• Grundsätzliche Frage: Wie viele Orbit gibt es?

27

Burkhard Wald

Beispiel

Gruppe mit 8 Elementen

Drehung um 0 Grad (16 bleiben fix)Drehung um 90 Grad (2 bleiben fix)Drehung um 180 Grad (4 bleiben fix)Drehung um 270 Grad (2 bleiben fix)Spiegelung N/S (4 bleiben fix)Spiegelung O/W (4 bleiben fix)Spiegelung NW/SO (8 bleiben fix)Spiegelung NO/SW (8 bleiben fix)

Operiert auf der Menge der obigen 16 Quadrate

6 Orbit:

28

Burkhard Wald

Lemma von Burnside

• Zu einem x gibt es die Untergruppe G_x derjenigen Gruppenelement, die x fix lassen.

• Zwei Elemente im selben Orbit haben gleich große Fixgruppen.

• Die Orbitgröße ist die Größe der Gruppe geteilt durch Größe der Fixgruppen dieses Orbits

• Die Menge der Paare (x,g) mit x^g = x, wobei x einen Orbit durchläuft und g ein beliebiges Gruppenelement ist, hat die gleiche Mächtigkeit wie G.

• Zu einem Gruppenelement gibt des die Menge fix(g) der Fixpunkte der Operation von g auf die Menge.

• Die Anzahl der Orbits ist die mittlere Größe der Fixmengen fix(g).

29

Burkhard Wald

Lemma von Burnside

30

Burkhard Wald

Nachträglich eingefügte Seite• Das Bild zeigt die Operation der Gruppe auf der Menge.

• Jede Zeile steht für ein Gruppenelement. Wie wird das Quadrat in der oberste Zeile durch Gruppenelement transferiert.

• Die obere Zeile steht auch für die Operation des Einselemtes der Gruppe

• Die rot markierten Quadrate zeigen Situation wo x^g=x

• Die Anzahl der roten Quadrate im ganzen Bild kann man auf zwei Weisen zählen: zeilenweise oder spaltenweise.

• Ein Spalte stellt die Wirkung der Gruppe auf ein einzelnes Element (das oberste) dar.

• Dabei wir der ganze Orbit durchschritten. Ist k die Anzahl der Fixpunkte in der Zeile, so haben immer k viele Gruppenelemente die gleiche Wirkung.

• Die Orbitgröße mal k ergibt die Gruppengröße.

• Bei der Abzählung der roten Quadrate im Bild ergibt sich pro Orbit die Gruppegröße.

• Somit gibt es insgesamt Orbitanzahl mal Gruppengröße viele rote Quadrate.

• Summiert man sie zeilenweise hat die gleiche Zahl. Um die mitlerer Zahl pro Zeile zu bekommen, Teilt man das durch die Gruppengröße.

• Das ist das die Orbitanzahl

• Das erläutert das Lemma von Bernsite

31

Burkhard Wald

Konjugationsklassen

• Verschieden Elemente der Gruppe können ein ähnliches Verhalten zeigen

• z.B wenn sie konjugiert zueinander sind:f und h sind konjugiert, wenn f = g*h*g^-1

• Die Konjugation h → g*h*g^-1 ist eine Gruppenoperation von G auf der Menge G

• Die Orbits sind die Konjugationsklassen

• Im Beispiel haben wir 5 Konjugationsklassen, 2 einelementige und 3 zweielementige.

• Für die Elemente einer Konjugationsklasse ist die Menge fix(g) gleich groß.

• Die Sudoku-Gruppe (ohne das Vertauschen) der Ziffern hat 275 Konjugationsklassen

32

Burkhard Wald

Nachträglich eingefügte Seite

• Um die Anzahl der Orbit zu bestimmen, muss ich die Größe der Fixmengen jedes Gruppenelementes bestimmen und aufsummieren. Die Größe der Fixmenge eines Gruppenelementes kann ich repräsentativ für ein einzelnes Gruppenelement jeder Konjugationklasse durchführen. Das multipliziert man mit der Größe der Konjugationsklasse.

•

• Im Folgenden fragen wir nach der Anzahl der Orbit bei ausgefüllten 4x4-Sudokus.

• Es sind 2.

• Als Erstes notieren wir alle Sudokus mit einem festen ersten Block

• Das sind 12. Im Bild sehen wir 4 Ansätze die sich vervollständigen lassen.

33

Burkhard Wald

12 4x4-Sudokus mit einen festen Block

1 243

3 421

4 132

2 314

1 243

3 412

1 243

4 321

1 243

4 312

1 423

1 243

3 421

2 314

4 132

1 243

3 412

1 243

4 321

1 243

4 312

3 241

1 243

3 421

4 312

2 134

1 243

3 412

4 321

1 243

4 321

3 412

1 243

4 312

3 421

1 243

3 421

2 134

4 312

1 243

3 412

1 234

1 243

4 321

2 143

1 243

4 312

1 243

2 314

2 314

2 314

4 132

4 132

4 132

2 134

2 134

2 134

4 312

4 312

4 312

34

Burkhard Wald

… ergibt nur 2 Orbits

• Die blauen, grünen und roten Sudokus sind gleichwertig

• Spiegelt man ein blaues Sudoku, entsteht ein grünes.

• Die roten sind anders. Dort gibt es nur zwei Paare, die in den Blöcken als Diagonale vorkommen. Das gilt für blau und grün nicht.

35

Burkhard Wald

Andere Abzählungsfragen

4 5 7

8 2 3

9 1 6

6 3 2

1 9 7

8 5 4

1 9 8

5 6 4

2 7 3

5 6 8

7 9 1

3 4 2

9 7 3

2 4 8

5 1 6

4 2 1

6 3 5

7 8 9

6 3 5

2 8 9

1 7 4

7 8 1

4 6 5

3 2 9

9 4 2

3 1 7

8 5 6 949 Orbits bei 50952 Möglichkeiten(82 Orbits bei 3600 Möglichkeiten für 2 Ziffern)

a b c

fed

Schema: aed bee dcd

36

Burkhard Wald

Nachträglich eingefügte Seite• Wir fragen nach der Anzahl der Möglichkeiten, wie 3 (oder 2) Ziffern in einem

ausgefüllten Sudoku verteilt sein können. (nat. unter Berücksichtigung der Symmetrien)

• Für eine einzelne Ziffer ist das die Anzahl 1 (dh. alle Möglichkeiten sind gleichwertig)

• Es gibt 6 Möglichkeiten 3 Ziffern in einem Block anzuordnen (a,b,c,d,e,f)

• Jeder der 9 Blöcke hat eines dieser 6 Schemen.

• Daraus ergeben sich 6^9 = 10077696 Möglichkeiten.

• Davon sind aber nur 50952 wirklich möglich.

• Jede Möglichkeit 3 Ziffern in einem ausgefüllten Sudoku anzuordnen lässt sich durch Vertauschen der 3 Zeilen einer Blockzeile oder der 3 Spalten einer Blockspalte auf eine der 50952 Möglichkeiten bringen.

• Wir betrachten die Symetriegruppe auf diese 3x3 Schemen und berücksichtige, das bei einer Drehung um 90 Grad und einer Spiegelung an der Diagonalen a und f sowie b und e vertauscht werden.

• Dann hat man 949 Orbit

37

Burkhard Wald

Verweise

• Ein passables Sududoku-Programm ist „Simple Sudoku“– http://www.angusj.com/sudoku/

•

•• Die Berechnungen mit den Symmetriegruppen wurde mit

„GAP“ gemacht– https://de.wikipedia.org/wiki/GAP_(Software)