Post on 06-Mar-2018
transcript
Sudoku vs. GraphenfärbungWenn alles verschieden sein muss
Timo BertholdZuse Institut Berlin
DFG-Forschungszentrum MATHEONMathematik für Schlüsseltechnologien
Berlin, 14.06.2008
Geschichtliches
Verschiedene Zahlenquadrate
. Magische Quadrate: Summe derZeilen-, Spalten-, Diagonal-einträge konstant
. Lateinische Quadrate: Jede Zahlnur einmal pro Spalte und Zeile
. Sudoku: Größe 9x9,Unterquadrate
Sudoku vs. Graphenfärbung 2 / 16
Geschichtliches
Verschiedene Zahlenquadrate
. Magische Quadrate: Summe derZeilen-, Spalten-, Diagonal-einträge konstant
. Lateinische Quadrate: Jede Zahlnur einmal pro Spalte und Zeile
. Sudoku: Größe 9x9,Unterquadrate
Sudoku vs. Graphenfärbung 2 / 16
Geschichtliches
Verschiedene Zahlenquadrate
. Magische Quadrate: Summe derZeilen-, Spalten-, Diagonal-einträge konstant
. Lateinische Quadrate: Jede Zahlnur einmal pro Spalte und Zeile
. Sudoku: Größe 9x9,Unterquadrate
Sudoku vs. Graphenfärbung 2 / 16
Geschichtliches
Verschiedene Zahlenquadrate
. Magische Quadrate: Summe derZeilen-, Spalten-, Diagonal-einträge konstant
. Lateinische Quadrate: Jede Zahlnur einmal pro Spalte und Zeile
. Sudoku: Größe 9x9,Unterquadrate
Sudoku vs. Graphenfärbung 2 / 16
Sudoku
Die Regeln
. pro Feld: Genau eine Zahl
. pro Zeile: Jede Zahl genau einmal
. pro Spalte: Jede Zahl genau einmal
. pro Block: Jede Zahl genau einmal
. am Anfang:Zahlen vorgegeben
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
2
Sudoku vs. Graphenfärbung 3 / 16
Sudoku
Die Regeln
. pro Feld: Genau eine Zahl
. pro Zeile: Jede Zahl genau einmal
. pro Spalte: Jede Zahl genau einmal
. pro Block: Jede Zahl genau einmal
. am Anfang:Zahlen vorgegeben
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
2
Sudoku vs. Graphenfärbung 3 / 16
Sudoku
Die Regeln
. pro Feld: Genau eine Zahl
. pro Zeile: Jede Zahl genau einmal
. pro Spalte: Jede Zahl genau einmal
. pro Block: Jede Zahl genau einmal
. am Anfang:Zahlen vorgegeben
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
2
Sudoku vs. Graphenfärbung 3 / 16
Sudoku
Die Regeln
. pro Feld: Genau eine Zahl
. pro Zeile: Jede Zahl genau einmal
. pro Spalte: Jede Zahl genau einmal
. pro Block: Jede Zahl genau einmal
. am Anfang:Zahlen vorgegeben
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
2
Sudoku vs. Graphenfärbung 3 / 16
Sudoku
Die Regeln
. pro Feld: Genau eine Zahl
. pro Zeile: Jede Zahl genau einmal
. pro Spalte: Jede Zahl genau einmal
. pro Block: Jede Zahl genau einmal
. am Anfang:Zahlen vorgegeben
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
3
2
Sudoku vs. Graphenfärbung 3 / 16
Sudoku
Die Regeln
. pro Feld: Genau eine Zahl
. pro Zeile: Jede Zahl genau einmal
. pro Spalte: Jede Zahl genau einmal
. pro Block: Jede Zahl genau einmal
. am Anfang:Zahlen vorgegeben
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
2
Sudoku vs. Graphenfärbung 3 / 16
Sudoku
Die Regeln
. pro Feld: Genau eine Zahl
. pro Zeile: Jede Zahl genau einmal
. pro Spalte: Jede Zahl genau einmal
. pro Block: Jede Zahl genau einmal
. am Anfang:Zahlen vorgegeben
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
2
Sudoku vs. Graphenfärbung 3 / 16
Sudoku
Die Regeln
. pro Feld: Genau eine Zahl
. pro Zeile: Jede Zahl genau einmal
. pro Spalte: Jede Zahl genau einmal
. pro Block: Jede Zahl genau einmal
. am Anfang:Zahlen vorgegeben
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
2
Sudoku vs. Graphenfärbung 3 / 16
Sudoku
Die Regeln
. pro Feld: Genau eine Zahl
. pro Zeile: Jede Zahl genau einmal
. pro Spalte: Jede Zahl genau einmal
. pro Block: Jede Zahl genau einmal
. am Anfang:Zahlen vorgegeben
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
2
Sudoku vs. Graphenfärbung 3 / 16
Sudoku
Die Regeln
. pro Feld: Genau eine Zahl
. pro Zeile: Jede Zahl genau einmal
. pro Spalte: Jede Zahl genau einmal
. pro Block: Jede Zahl genau einmal
. am Anfang:Zahlen vorgegeben
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
2
Sudoku vs. Graphenfärbung 3 / 16
Sudoku
Die Regeln
. pro Feld: Genau eine Zahl
. pro Zeile: Jede Zahl genau einmal
. pro Spalte: Jede Zahl genau einmal
. pro Block: Jede Zahl genau einmal
. am Anfang:Zahlen vorgegeben
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
28
Sudoku vs. Graphenfärbung 3 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2, x1,1,3, x1,1,4, . . . ,x1,1,9
. pro Feld:
. pro Zeile:
. pro Spalte:
. pro Block:
. Fixieren:
729 Variablen, Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2 34 5 67 8 9
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1,
x1,1,2, x1,1,3, x1,1,4, . . . ,x1,1,9
. pro Feld:
. pro Zeile:
. pro Spalte:
. pro Block:
. Fixieren:
729 Variablen, Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1
2 34 5 67 8 9
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2,
x1,1,3, x1,1,4, . . . ,x1,1,9
. pro Feld:
. pro Zeile:
. pro Spalte:
. pro Block:
. Fixieren:
729 Variablen, Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2
34 5 67 8 9
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2, x1,1,3,
x1,1,4, . . . ,x1,1,9
. pro Feld:
. pro Zeile:
. pro Spalte:
. pro Block:
. Fixieren:
729 Variablen, Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2 3
4 5 67 8 9
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2, x1,1,3, x1,1,4,
. . . ,x1,1,9
. pro Feld:
. pro Zeile:
. pro Spalte:
. pro Block:
. Fixieren:
729 Variablen, Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2 34
5 67 8 9
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2, x1,1,3, x1,1,4, . . . ,x1,1,9
. pro Feld:
. pro Zeile:
. pro Spalte:
. pro Block:
. Fixieren:
729 Variablen,
Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2 34 5 67 8 9
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2, x1,1,3, x1,1,4, . . . ,x1,1,9
. pro Feld: Genau eine Zahl
. pro Zeile:
. pro Spalte:
. pro Block:
. Fixieren:
729 Variablen,
Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2 34 5 67 8 9
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2, x1,1,3, x1,1,4, . . . ,x1,1,9
. pro Feld: x1,1,1+. . .+x1,1,9 = 1
. pro Zeile:
. pro Spalte:
. pro Block:
. Fixieren:
729 Variablen,
Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2 34 5 67 8 9
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2, x1,1,3, x1,1,4, . . . ,x1,1,9
. pro Feld: x1,1,1+. . .+x1,1,9 = 1
. pro Zeile: Jede Zahl genau einmal
. pro Spalte:
. pro Block:
. Fixieren:
729 Variablen, Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2 34 5 67 8 9
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2, x1,1,3, x1,1,4, . . . ,x1,1,9
. pro Feld: x1,1,1+. . .+x1,1,9 = 1
. pro Zeile: x1,1,3+. . .+x1,9,3 = 1
. pro Spalte:
. pro Block:
. Fixieren:
729 Variablen, 81 Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2 34 5 67 8 9
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2, x1,1,3, x1,1,4, . . . ,x1,1,9
. pro Feld: x1,1,1+. . .+x1,1,9 = 1
. pro Zeile: x1,1,3+. . .+x1,9,3 = 1
. pro Spalte: Jede Zahl genau einmal
. pro Block:
. Fixieren:
729 Variablen, 81 Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2 34 5 67 8 9
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2, x1,1,3, x1,1,4, . . . ,x1,1,9
. pro Feld: x1,1,1+. . .+x1,1,9 = 1
. pro Zeile: x1,1,3+. . .+x1,9,3 = 1
. pro Spalte: x1,1,3+. . .+x9,1,3 = 1
. pro Block:
. Fixieren:
729 Variablen, 162 Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2 34 5 67 8 9
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2, x1,1,3, x1,1,4, . . . ,x1,1,9
. pro Feld: x1,1,1+. . .+x1,1,9 = 1
. pro Zeile: x1,1,3+. . .+x1,9,3 = 1
. pro Spalte: x1,1,3+. . .+x9,1,3 = 1
. pro Block: Jede Zahl genau einmal
. Fixieren:
729 Variablen, 162 Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2 34 5 67 8 9
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2, x1,1,3, x1,1,4, . . . ,x1,1,9
. pro Feld: x1,1,1+. . .+x1,1,9 = 1
. pro Zeile: x1,1,3+. . .+x1,9,3 = 1
. pro Spalte: x1,1,3+. . .+x9,1,3 = 1
. pro Block: x1,1,3+. . .+x3,3,3 = 1
. Fixieren:
729 Variablen, 243 Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2 34 5 67 8 9
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2, x1,1,3, x1,1,4, . . . ,x1,1,9
. pro Feld: x1,1,1+. . .+x1,1,9 = 1
. pro Zeile: x1,1,3+. . .+x1,9,3 = 1
. pro Spalte: x1,1,3+. . .+x9,1,3 = 1
. pro Block: x1,1,3+. . .+x3,3,3 = 1
. Fixieren: Vorgegebene Zahlen
729 Variablen, 243 Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2 34 5 67 8 9
3
Sudoku vs. Graphenfärbung 4 / 16
Modellierungsansatz
Modell mit Gleichungen
. Neun 0-1-Variablen pro Feld:x1,1,1, x1,1,2, x1,1,3, x1,1,4, . . . ,x1,1,9
. pro Feld: x1,1,1+. . .+x1,1,9 = 1
. pro Zeile: x1,1,3+. . .+x1,9,3 = 1
. pro Spalte: x1,1,3+. . .+x9,1,3 = 1
. pro Block: x1,1,3+. . .+x3,3,3 = 1
. Fixieren: x2,2,3 = 1,. . .
729 Variablen, 324 Gleichungen
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
1 2 34 5 67 8 9
3
Sudoku vs. Graphenfärbung 4 / 16
Varianten
Andere Zahlenrätsel
. X-Sudoku
. 16x16-Sudoku
. 3D-Sudoku
. Kakuro
. Killer-Sudoku
. Ensaimada
. Vergleichs-Sudoku
Sudoku vs. Graphenfärbung 5 / 16
Varianten
Andere Zahlenrätsel
. X-Sudoku
. 16x16-Sudoku
. 3D-Sudoku
. Kakuro
. Killer-Sudoku
. Ensaimada
. Vergleichs-Sudoku
Sudoku vs. Graphenfärbung 5 / 16
Varianten
Andere Zahlenrätsel
. X-Sudoku
. 16x16-Sudoku
. 3D-Sudoku
. Kakuro
. Killer-Sudoku
. Ensaimada
. Vergleichs-Sudoku
Sudoku vs. Graphenfärbung 5 / 16
Varianten
Andere Zahlenrätsel
. X-Sudoku
. 16x16-Sudoku
. 3D-Sudoku
. Kakuro
. Killer-Sudoku
. Ensaimada
. Vergleichs-Sudoku
Sudoku vs. Graphenfärbung 5 / 16
Varianten
Andere Zahlenrätsel
. X-Sudoku
. 16x16-Sudoku
. 3D-Sudoku
. Kakuro
. Killer-Sudoku
. Ensaimada
. Vergleichs-Sudoku
Sudoku vs. Graphenfärbung 5 / 16
Varianten
Andere Zahlenrätsel
. X-Sudoku
. 16x16-Sudoku
. 3D-Sudoku
. Kakuro
. Killer-Sudoku
. Ensaimada
. Vergleichs-Sudoku
Sudoku vs. Graphenfärbung 5 / 16
Varianten
Andere Zahlenrätsel
. X-Sudoku
. 16x16-Sudoku
. 3D-Sudoku
. Kakuro
. Killer-Sudoku
. Ensaimada
. Vergleichs-Sudoku
Sudoku vs. Graphenfärbung 5 / 16
Graphenfärbung
Graphen und Färbung
. Graph:
Knoten, Kanten. Färbung:
I Jeder Knoten eine FarbeI Kante ⇒ verschiedene Farben
I Färbungszahl
Sudoku vs. Graphenfärbung 6 / 16
Graphenfärbung
Graphen und Färbung
. Graph: Knoten,
Kanten. Färbung:
I Jeder Knoten eine FarbeI Kante ⇒ verschiedene Farben
I Färbungszahl
Sudoku vs. Graphenfärbung 6 / 16
Graphenfärbung
Graphen und Färbung
. Graph: Knoten, Kanten
. Färbung:I Jeder Knoten eine FarbeI Kante ⇒ verschiedene Farben
I Färbungszahl
Sudoku vs. Graphenfärbung 6 / 16
Graphenfärbung
Graphen und Färbung
. Graph: Knoten, Kanten
. Färbung:I Jeder Knoten eine FarbeI Kante ⇒ verschiedene Farben
I Färbungszahl
Sudoku vs. Graphenfärbung 6 / 16
Graphenfärbung
Graphen und Färbung
. Graph: Knoten, Kanten
. Färbung:I Jeder Knoten eine FarbeI Kante ⇒ verschiedene FarbenI Färbungszahl
Sudoku vs. Graphenfärbung 6 / 16
Ein typisches Färbungsproblem
Kartenfärbung
. Ziel: Länder mit gemeinsamerGrenze verschieden einfärben
. Idee: Nachbarschaftsgraph
. Resultat: 4-Farben-Satz
Sudoku vs. Graphenfärbung 7 / 16
Ein typisches Färbungsproblem
Kartenfärbung
. Ziel: Länder mit gemeinsamerGrenze verschieden einfärben
. Idee: Nachbarschaftsgraph
. Resultat: 4-Farben-Satz
Sudoku vs. Graphenfärbung 8 / 16
Ein typisches Färbungsproblem
Kartenfärbung
. Ziel: Länder mit gemeinsamerGrenze verschieden einfärben
. Idee: Nachbarschaftsgraph
. Resultat: 4-Farben-Satz
Sudoku vs. Graphenfärbung 8 / 16
Ein typisches Färbungsproblem
Kartenfärbung
. Ziel: Länder mit gemeinsamerGrenze verschieden einfärben
. Idee: Nachbarschaftsgraph
. Resultat: 4-Farben-Satz
Sudoku vs. Graphenfärbung 8 / 16
Ein typisches Färbungsproblem
Kartenfärbung
. Ziel: Länder mit gemeinsamerGrenze verschieden einfärben
. Idee: Nachbarschaftsgraph
. Resultat: 4-Farben-Satz
Sudoku vs. Graphenfärbung 9 / 16
Optimierung in der Telekommunikation
Frequenzzuweisung
. GSM-Funknetze:Farben =̂ Frequenzen
. MATHEON B-4: Planning theUMTS radio interface
. Ziel: Funknetz optimalkonfigurieren
Sudoku vs. Graphenfärbung 10 / 16
Optimierung in der Telekommunikation
Frequenzzuweisung
. GSM-Funknetze:Farben =̂ Frequenzen
. MATHEON B-4: Planning theUMTS radio interface
. Ziel: Funknetz optimalkonfigurieren
Sudoku vs. Graphenfärbung 10 / 16
Optimierung in der Telekommunikation
Frequenzzuweisung
. GSM-Funknetze:Farben =̂ Frequenzen
. MATHEON B-4: Planning theUMTS radio interface
. Ziel: Funknetz optimalkonfigurieren
Sudoku vs. Graphenfärbung 10 / 16
Optimierung in der Telekommunikation
Frequenzzuweisung
. GSM-Funknetze:Farben =̂ Frequenzen
. MATHEON B-4: Planning theUMTS radio interface
. Ziel: Funknetz optimalkonfigurieren
Sudoku vs. Graphenfärbung 10 / 16
Sudoku ⇔ Graphenfärbung
Der Sudokugraph
. Zahlen ⇔ Farben
. Felder ⇔ Knoten
. Konflikte ⇔ Kanten
. Lösung ⇔ 9-Färbung
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
465873192 4
35621879
786549321
824916735
617435298
359782146
178264953
962153487
543897612
Sudoku vs. Graphenfärbung 11 / 16
Sudoku ⇔ Graphenfärbung
Der Sudokugraph
. Zahlen ⇔ Farben
. Felder ⇔ Knoten
. Konflikte ⇔ Kanten
. Lösung ⇔ 9-Färbung
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
465873192 4
35621879
786549321
824916735
617435298
359782146
178264953
962153487
543897612
Sudoku vs. Graphenfärbung 11 / 16
Sudoku ⇔ Graphenfärbung
Der Sudokugraph
. Zahlen ⇔ Farben
. Felder ⇔ Knoten
. Konflikte ⇔ Kanten
. Lösung ⇔ 9-Färbung
465873192 4
35621879
786549321
824916735
617435298
359782146
178264953
962153487
543897612
Sudoku vs. Graphenfärbung 11 / 16
Sudoku ⇔ Graphenfärbung
Der Sudokugraph
. Zahlen ⇔ Farben
. Felder ⇔ Knoten
. Konflikte ⇔ Kanten
. Lösung ⇔ 9-Färbung
465873192 4
35621879
786549321
824916735
617435298
359782146
178264953
962153487
543897612
Sudoku vs. Graphenfärbung 11 / 16
Sudoku ⇔ Graphenfärbung
Der Sudokugraph
. Zahlen ⇔ Farben
. Felder ⇔ Knoten
. Konflikte ⇔ Kanten
. Lösung ⇔ 9-Färbung
465873192 4
35621879
786549321
824916735
617435298
359782146
178264953
962153487
543897612
Sudoku vs. Graphenfärbung 11 / 16
Sudoku ⇔ Graphenfärbung
Der Sudokugraph
. Zahlen ⇔ Farben
. Felder ⇔ Knoten
. Konflikte ⇔ Kanten
. Lösung ⇔ 9-Färbung
465873192 4
35621879
786549321
824916735
617435298
359782146
178264953
962153487
543897612
Sudoku vs. Graphenfärbung 11 / 16
Sudoku ⇔ Graphenfärbung
Der Sudokugraph
. Zahlen ⇔ Farben
. Felder ⇔ Knoten
. Konflikte ⇔ Kanten
. Lösung ⇔ 9-Färbung
465873192 4
35621879
786549321
824916735
617435298
359782146
178264953
962153487
543897612
Sudoku vs. Graphenfärbung 11 / 16
Sudoku ⇔ Graphenfärbung
Der Sudokugraph
. Zahlen ⇔ Farben
. Felder ⇔ Knoten
. Konflikte ⇔ Kanten
. Lösung ⇔ 9-Färbung
465873192 4
35621879
786549321
824916735
617435298
359782146
178264953
962153487
543897612
Sudoku vs. Graphenfärbung 11 / 16
Sudoku ⇔ Graphenfärbung
Der Sudokugraph
. Zahlen ⇔ Farben
. Felder ⇔ Knoten
. Konflikte ⇔ Kanten
. Lösung ⇔ 9-Färbung
465873192 4
35621879
786549321
824916735
617435298
359782146
178264953
962153487
543897612
Sudoku vs. Graphenfärbung 11 / 16
Software
Sudoku-Löser
. Verfügbar unter:http://www.matheon.de/specialities/sudoku.asp
. Löst ein GanzzahligesProgramm
. Benutzt die Software SCIP
Sudoku vs. Graphenfärbung 12 / 16
Symmetrie
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
7→ 9, 9→ 2, . . .
Anzahl möglicher Sudokus:≈ 6,67 · 1021 = 6,67 Trilliarden
3 87
429 8 2
9
73 6
5384
2
71
5 8 3
86 316
7→ 9, 9→ 2, . . .
Anzahl nichtsymm. Sudokus:≈ 5,47 · 1010 = 54,7 Milliarden
Sudoku vs. Graphenfärbung 13 / 16
Symmetrie
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
7→ 9, 9→ 2, . . .
Anzahl möglicher Sudokus:≈ 6,67 · 1021 = 6,67 Trilliarden
5 19
64
2 1 4
2
95 8
75 1
6
4
93
7 1 5
1 8 538
7→ 9, 9→ 2, . . .
Anzahl nichtsymm. Sudokus:≈ 5,47 · 1010 = 54,7 Milliarden
Sudoku vs. Graphenfärbung 13 / 16
Symmetrie
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
7→ 9, 9→ 2, . . .
Anzahl möglicher Sudokus:≈ 6,67 · 1021 = 6,67 Trilliarden
5 19
64
2 1 4
2
95 8
75 1
6
4
93
7 1 5
1 8 538
7→ 9, 9→ 2, . . .
Anzahl nichtsymm. Sudokus:≈ 5,47 · 1010 = 54,7 Milliarden
Sudoku vs. Graphenfärbung 13 / 16
Symmetrie
3 87
42
9 8 2
9
73 6
53 8
4
2
71
5 8 3
8 6 316
7→ 9, 9→ 2, . . .
Anzahl möglicher Sudokus:≈ 6,67 · 1021 = 6,67 Trilliarden
5 19
64
2 1 4
2
95 8
75 1
6
4
93
7 1 5
1 8 538
7→ 9, 9→ 2, . . .
Anzahl nichtsymm. Sudokus:≈ 5,47 · 1010 = 54,7 Milliarden
Sudoku vs. Graphenfärbung 13 / 16
Aktuelle Forschung
Umgang mit Symmetrien
. Ursache: Äquivalente Lösungen
. Problem: Langsamer,schlechtere Abschätzungen
. Idee: Sortierung
Ganzzahlige Programmierung
. Lösen “riesiger” Gleichungssysteme
. Anwendungen:I FrequenzzuweisungI FahrplanerstellungI Chip-Design, . . .
Sudoku vs. Graphenfärbung 14 / 16
Aktuelle Forschung
Umgang mit Symmetrien
. Ursache: Äquivalente Lösungen
. Problem: Langsamer,schlechtere Abschätzungen
. Idee: Sortierung
Ganzzahlige Programmierung
. Lösen “riesiger” Gleichungssysteme
. Anwendungen:I FrequenzzuweisungI FahrplanerstellungI Chip-Design, . . .
Sudoku vs. Graphenfärbung 14 / 16
Aktuelle Forschung
Umgang mit Symmetrien
. Ursache: Äquivalente Lösungen
. Problem: Langsamer,schlechtere Abschätzungen
. Idee: Sortierung
Ganzzahlige Programmierung
. Lösen “riesiger” Gleichungssysteme
. Anwendungen:I FrequenzzuweisungI FahrplanerstellungI Chip-Design, . . .
Sudoku vs. Graphenfärbung 14 / 16
Aktuelle Forschung
Umgang mit Symmetrien
. Ursache: Äquivalente Lösungen
. Problem: Langsamer,schlechtere Abschätzungen
. Idee: Sortierung
Ganzzahlige Programmierung
. Lösen “riesiger” Gleichungssysteme
. Anwendungen:I FrequenzzuweisungI FahrplanerstellungI Chip-Design, . . .
Sudoku vs. Graphenfärbung 14 / 16
P = NP? P 6= NP?
Ausgangslage
. Seien ein beliebiger Graph und eine beliebige Zahl k ∈ N gegeben
. Suchverfahren: Findet Färbung mit k Farben oder stellt fest, dass derGraph nicht k-färbbar ist
. Prüfverfahren: Überprüft für vorgegebene k-Färbung, ob sie korrekt ist
Ein Millennium-Problem
. Frage: Gibt es ein Suchverfahren, das “vergleichbar” schnell ist wie eineffizientes Prüfverfahren?
. Antwort: Ungeklärt . . .
. Belohnung: 1 Million Dollar
Sudoku vs. Graphenfärbung 15 / 16
P = NP? P 6= NP?
Ausgangslage
. Seien ein beliebiger Graph und eine beliebige Zahl k ∈ N gegeben
. Suchverfahren: Findet Färbung mit k Farben oder stellt fest, dass derGraph nicht k-färbbar ist
. Prüfverfahren: Überprüft für vorgegebene k-Färbung, ob sie korrekt ist
Ein Millennium-Problem
. Frage: Gibt es ein Suchverfahren, das “vergleichbar” schnell ist wie eineffizientes Prüfverfahren?
. Antwort: Ungeklärt . . .
. Belohnung: 1 Million Dollar
Sudoku vs. Graphenfärbung 15 / 16
P = NP? P 6= NP?
Ausgangslage
. Seien ein beliebiger Graph und eine beliebige Zahl k ∈ N gegeben
. Suchverfahren: Findet Färbung mit k Farben oder stellt fest, dass derGraph nicht k-färbbar ist
. Prüfverfahren: Überprüft für vorgegebene k-Färbung, ob sie korrekt ist
Ein Millennium-Problem
. Frage: Gibt es ein Suchverfahren, das “vergleichbar” schnell ist wie eineffizientes Prüfverfahren?
. Antwort: Ungeklärt . . .
. Belohnung: 1 Million Dollar
Sudoku vs. Graphenfärbung 15 / 16
P = NP? P 6= NP?
Ausgangslage
. Seien ein beliebiger Graph und eine beliebige Zahl k ∈ N gegeben
. Suchverfahren: Findet Färbung mit k Farben oder stellt fest, dass derGraph nicht k-färbbar ist
. Prüfverfahren: Überprüft für vorgegebene k-Färbung, ob sie korrekt ist
Ein Millennium-Problem
. Frage: Gibt es ein Suchverfahren, das “vergleichbar” schnell ist wie eineffizientes Prüfverfahren?
. Antwort: Ungeklärt . . .
. Belohnung: 1 Million Dollar
Sudoku vs. Graphenfärbung 15 / 16
Sudoku vs. GraphenfärbungWenn alles verschieden sein muss
Timo BertholdZuse Institut Berlin
DFG-Forschungszentrum MATHEONMathematik für Schlüsseltechnologien
Berlin, 14.06.2008