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