Domino
Domino - Beispiel
Ein Dominostein besteht aus zwei Hälften, auf denen jeweils eine Zahl von 0 bis 6 steht. Jeden Dominostein gibt es genau einmal: 0-0, 0-1, usw. bis 6-6; wobei es auf die Reihenfolge der Beschriftung nicht ankommt: 1-2 und 2-1 sind identisch. Es gibt also insgesamt 28 verschiedene Dominosteine.
Im gegebenen Diagramm sind alle 28 Dominosteine in einem 7x8 Rechteck zusammengelegt; jedes Kästchen präsentiert einen halben Dominostein.
Die Aufgabe besteht nun darin, eine Konfiguration von Dominosteinen herauszufinden, die das gegebene Muster ergibt. Die Lösung ist eindeutig.
Wir wollen nun die folgende Aufgabe gemeinsam lösen:
| 2 | 1 | 0 | 3 | 0 | 4 | 5 | 5 |
| 6 | 2 | 0 | 6 | 3 | 1 | 4 | 0 |
| 3 | 2 | 3 | 6 | 2 | 5 | 4 | 3 |
| 5 | 4 | 5 | 1 | 1 | 2 | 1 | 2 |
| 0 | 0 | 1 | 5 | 0 | 5 | 4 | 4 |
| 4 | 6 | 2 | 1 | 3 | 6 | 6 | 1 |
| 4 | 2 | 0 | 6 | 5 | 3 | 3 | 6 |
Versuchen wir zunächst einmal, Steine zu finden, die sich eindeutig identifizieren lassen. Der Stein 2-1 ist beispielsweise nicht eindeutig:
| 2 | 1 | 0 | 3 | 0 | 4 | 5 | 5 |
| 6 | 2 | 0 | 6 | 3 | 1 | 4 | 0 |
| 3 | 2 | 3 | 6 | 2 | 5 | 4 | 3 |
| 5 | 4 | 5 | 1 | 1 | 2 | 1 | 2 |
| 0 | 0 | 1 | 5 | 0 | 5 | 4 | 4 |
| 4 | 6 | 2 | 1 | 3 | 6 | 6 | 1 |
| 4 | 2 | 0 | 6 | 5 | 3 | 3 | 6 |
Andere Steine sind hingegen eindeutig; in dieser Aufgabe sind dies 1-1, 2-2, 3-3, 3-4 und 5-5:
| 2 | 1 | 0 | 3 | 0 | 4 | 5 | 5 |
| 6 | 2 | 0 | 6 | 3 | 1 | 4 | 0 |
| 3 | 2 | 3 | 6 | 2 | 5 | 4 | 3 |
| 5 | 4 | 5 | 1 | 1 | 2 | 1 | 2 |
| 0 | 0 | 1 | 5 | 0 | 5 | 4 | 4 |
| 4 | 6 | 2 | 1 | 3 | 6 | 6 | 1 |
| 4 | 2 | 0 | 6 | 5 | 3 | 3 | 6 |
Jeder identifizierte Stein reduziert die Möglichkeiten für die noch fehlenden Steine. Dadurch können jetzt zwei weitere Steine identifiziert werden, nämlich 4-0 und 1-6:
| 2 | 1 | 0 | 3 | 0 | 4 | 5 | 5 |
| 6 | 2 | 0 | 6 | 3 | 1 | 4 | 0 |
| 3 | 2 | 3 | 6 | 2 | 5 | 4 | 3 |
| 5 | 4 | 5 | 1 | 1 | 2 | 1 | 2 |
| 0 | 0 | 1 | 5 | 0 | 5 | 4 | 4 |
| 4 | 6 | 2 | 1 | 3 | 6 | 6 | 1 |
| 4 | 2 | 0 | 6 | 5 | 3 | 3 | 6 |
Jetzt kann ein weiterer Stein identifiziert werden: 2-0
| 2 | 1 | 0 | 3 | 0 | 4 | 5 | 5 |
| 6 | 2 | 0 | 6 | 3 | 1 | 4 | 0 |
| 3 | 2 | 3 | 6 | 2 | 5 | 4 | 3 |
| 5 | 4 | 5 | 1 | 1 | 2 | 1 | 2 |
| 0 | 0 | 1 | 5 | 0 | 5 | 4 | 4 |
| 4 | 6 | 2 | 1 | 3 | 6 | 6 | 1 |
| 4 | 2 | 0 | 6 | 5 | 3 | 3 | 6 |
So geht es jetzt aber leider nicht weiter, es können keine Steine mehr eindeutig identifiziert werden. Wir müssen zu Versuch und Irrtum greifen:
Nehmen wir einmal an, dass links unten 4-4 liegt. Dann liegt 6-2 daneben. Rechts kann nicht mehr 4-4 liegen, also liegt dort 2-4. 6-0 ist jetzt eindeutig, damit auch 6-6 und 0-0. Und nun ist auch 5-0 eindeutig.
| 2 | 1 | 0 | 3 | 0 | 4 | 5 | 5 |
| 6 | 2 | 0 | 6 | 3 | 1 | 4 | 0 |
| 3 | 2 | 3 | 6 | 2 | 5 | 4 | 3 |
| 5 | 4 | 5 | 1 | 1 | 2 | 1 | 2 |
| 0 | 0 | 1 | 5 | 0 | 5 | 4 | 4 |
| 4 | 6 | 2 | 1 | 3 | 6 | 6 | 1 |
| 4 | 2 | 0 | 6 | 5 | 3 | 3 | 6 |
Jetzt ergeben sich weiter: 5-1, 3-6, 4-5, 3-6 ... HALT! 3-6 darf nicht doppelt vorkommen! Die Annahme war also falsch, links unten liegt nicht 4-4, also liegt links unten 4-2. Damit muss rechts 4-4 liegen, damit auch 1-2 und 6-6. Da jetzt 1-2 verbraucht ist, muss links oben 2-6 liegen, womit sich 1-0 und 3-5 automatisch ergeben:
| 2 | 1 | 0 | 3 | 0 | 4 | 5 | 5 |
| 6 | 2 | 0 | 6 | 3 | 1 | 4 | 0 |
| 3 | 2 | 3 | 6 | 2 | 5 | 4 | 3 |
| 5 | 4 | 5 | 1 | 1 | 2 | 1 | 2 |
| 0 | 0 | 1 | 5 | 0 | 5 | 4 | 4 |
| 4 | 6 | 2 | 1 | 3 | 6 | 6 | 1 |
| 4 | 2 | 0 | 6 | 5 | 3 | 3 | 6 |
Jetzt ist 0-0 eindeutig, und danach sind es dann auch 4-6, 4-5 und 1-5:
| 2 | 1 | 0 | 3 | 0 | 4 | 5 | 5 |
| 6 | 2 | 0 | 6 | 3 | 1 | 4 | 0 |
| 3 | 2 | 3 | 6 | 2 | 5 | 4 | 3 |
| 5 | 4 | 5 | 1 | 1 | 2 | 1 | 2 |
| 0 | 0 | 1 | 5 | 0 | 5 | 4 | 4 |
| 4 | 6 | 2 | 1 | 3 | 6 | 6 | 1 |
| 4 | 2 | 0 | 6 | 5 | 3 | 3 | 6 |
Der Rest ergibt sich jetzt fast von selbst:
| 2 | 1 | 0 | 3 | 0 | 4 | 5 | 5 |
| 6 | 2 | 0 | 6 | 3 | 1 | 4 | 0 |
| 3 | 2 | 3 | 6 | 2 | 5 | 4 | 3 |
| 5 | 4 | 5 | 1 | 1 | 2 | 1 | 2 |
| 0 | 0 | 1 | 5 | 0 | 5 | 4 | 4 |
| 4 | 6 | 2 | 1 | 3 | 6 | 6 | 1 |
| 4 | 2 | 0 | 6 | 5 | 3 | 3 | 6 |