Buchstabensalat - Mathematisches
Auf dieser Seite fasse ich einige Überlegungen zur Denksportaufgabe Buchstabensalat zusammen. Ziel soll es sein in Erfahrung zu bringen, wie viele (eindeutig) lösbare Aufgaben und Spiele es gibt.
Für die Anzahl der Aufgabenstellungen kann man recht schnell eine erste obere Schranke angeben. Das Spielfeld besteht aus einem Quadrat der Seitenlänge n, und an jeder Stelle steht entweder eines von m Symbolen oder keine Angabe. Dies führt uns zu (m+1)^(4*n) Aufgabenstellungen.
Wenn wir von einer Nennung aller Informationen ausgehen verringert sich die Anzahl der Aufgabenstellungen auf m^(4*n) Spiele. Da an den sich gegenüberliegenden Seiten einer Spalte oder Zeile nicht zweimal der gleiche Buchstabe stehen kann, können wir weiter auf (m*(m-1))^(2*n) vereinfachen.
| m=2 | m=3 | m=4 | m=5 | m=6 | |
|---|---|---|---|---|---|
| n=3 | 531.441 4.096 64 |
16.777.216 531.441 46.656 |
|||
| n=4 | 43.046.721 65.536 256 |
> 4*10^9 43.046.721 419.904 |
> 152*10^9 > 4*10^9 429.981.696 |
||
| n=5 | > 3*10^9 1.048.576 1.024 |
> 1*10^12 > 3*10^9 3.779.136 |
> 95*10^12 > 1*10^12 > 6*10^9 |
> 3*10^15 > 95*10^12 > 10*10^12 |
|
| n=6 | > 282*10^9 16.777.216 4.096 |
> 281*10^12 > 282*10^9 34.012.224 |
> 59*10^15 > 281*10^12 > 110*10^9 |
> 4*10^18 > 59*10^15 > 256*10^12 |
> 191*10^18 > 4*10^18 > 531*10^15 |
Die Anzahl der Aufgabenstellungen wächst also recht flott in Größenordnungen, in denen eine Überprüfung aller Spiele auf ihre Lösbarkeit nicht mehr denkbar ist. Drehen wir also den Spieß um, und werfen wir einen Blick auf das Erstellen der zu erratenden Spielfelder.
Mit den oberflächlich geschätzten m^(n^2) Möglickeiten die Buchstaben auf das Spielfeld zu verteilen brauchen wir uns glücklickerweise nicht zufrieden geben.
Jeder Buchstabe kommt in jeder Zeile genau einmal vor. Da es n!/(n-m)! Möglichkeiten gibt die m Buchstaben auf eine Zeile von n Spalten zu verteilen, gibt es maximal (n!/(n-m)!)^n gültige Spielfelder. Da jeder Buchstabe auch nur einmal pro Spalte vorkommt, gibt es n! Möglichkeiten je Buchstabe, also n!^m Möglichkeiten insgesamt.
| m=2 | m=3 | m=4 | m=5 | m=6 | |
|---|---|---|---|---|---|
| n=3 | 216 36 |
216 216 |
|||
| n=4 | 20.736 576 |
331.776 13.824 |
331.776 331.776 |
||
| n=5 | 3.200.000 14.400 |
777.600.000 1.728.000 |
> 24*10^9 207.360.000 |
> 24*10^9 > 24*10^9 |
|
| n=6 | 729.000.000 518.400 |
> 2*10^12 373.248.000 |
> 2*10^15 > 268*10^9 |
> 139*10^15 > 193*10^12 |
> 139*10^15 > 139*10^15 |
Erstellbare Spiele
Unter Berücksichtigung aller Spiegelungen, Rotationen und Permutationen:
| m=1 | m=2 | m=3 | m=4 | m=5 | m=6 | |
|---|---|---|---|---|---|---|
| n=3 | 2 | 2 | 1 | |||
| n=4 | 7 | 27 | 24 | 12 | ||
| n=5 | 23 | 367 | 1.460 | 900 | 192 | |
| n=6 | 115 | 12.428 | 321.888 | 1.483.013 | 852.592 | 145.164 |
| n=7 | 694 | 586.695 | 112.787.754 | |||
| n=8 | 5.282 | 37.418.814 |
Aufgabenstellungen
Die Anzahl der aus den Spielfeldern generierbaren Aufgabenstellungen. Ebenfalls wieder nach Berücksichtigung aller Permutationen, Drehungen und Spiegelungen.
| m=2 | m=3 | m=4 | m=5 | m=6 | m=7 | m=8 | |
|---|---|---|---|---|---|---|---|
| n=3 | 2 | 1 | |||||
| n=4 | 12 | 16 | 10 | ||||
| n=5 | 37 | 737 | 648 | 131 | |||
| n=6 | 214 | 73.594 | 438.618 | 249.732 | 10.704 | ||
| n=7 | 782 | 8.340.797 | 5.000.535 | ||||
| n=8 | 3.841 |
Eindeutig lösbare Spiele
Oberer Wert: Mit Prädikatenlogik lösbar. (Unterer Wert: zusätzlich mit Backtracking lösbar.)
| m=2 | m=3 | m=4 | m=5 | m=6 | m=7 | m=8 | |
|---|---|---|---|---|---|---|---|
| n=3 | 2 0 |
1 0 |
|||||
| n=4 | 4 0 |
11 0 |
8 0 |
||||
| n=5 | 8 0 |
331 +2 |
463 0 |
70 0 |
|||
| n=6 | 12 0 |
15.927 +1.841 |
149.942 +5.684 |
90.880 +2.066 |
0 0 |
||
| n=7 | 16 +1 |
497.156 |
0 |
||||
| n=8 | 17 +4 |