Da es ein Unentschieden nur geben kann, wenn alle Felder belegt sind, kann man das auf recht brutale Weise herausfinden.
Man rechnet alle Varianten durch, bei denen
a) alle Felder belegt sind,
b) je 21 Steine jeder Farbe benutzt wurden
und überprüft, ob
c) es nur Reihen aus höchstens 3 gleichen Steinen gibt.
Die Darstellung des Feldes würde ich aus programmiertechnischen Gründen von einem Boole'schen Array mit 42 Stellen übernehmen lassen. Dann werden alle Möglichkeiten durchgerechnet und gezählt.
Ich kann da ja zum Spaß mal kurz etwas schreiben und rechnen lassen.
---
20:40 Uhr:
Nach ersten Schätzungen dauert auch eine Optimierung noch deutlich zu lange (rund anderthalb Jahre), um schnell ein zufrieden stellendes Ergebnis zu liefern.
---
20:51 Uhr:
Genial einfach, einfach genial: Starke Optimierung bringt enormen Geschwindigkeitszuwachs, es dauert nur noch rund 3 Tage.
---
21:17 Uhr:
Zugegeben, nicht alle die auf diese Weise berechneten Lösungen sind zwangsläufig möglich, da durch die Gravitation bedingt nicht alle durch abwechselndes Werfen erreicht werden können. Wenn man allerdings das auch noch berücksichtigt, braucht man bedeutend länger, da das Ganze rekursiv berechnet werden muss, jeweils mit 7 Wurfmöglichkeiten. Dabei werden aber gleiche Endlösungen mehrmals durchgekaut, da ja nicht die Wurfreihenfolge, sondern die Lage der Spielsteine bei einem Unentschieden wichtig ist.
---
21:55 Uhr:
Für Verbesserungsvorschläge im Code bin ich dankbar...
(Programmiert mit C#, der erste Ausschnitt steht im Rumpf einer von System.Windows.Forms.Form erbenden Klassen, der zweite im Konstruktor)
1:
2: | private long[] zweiHoch = new long[43];
private const long startwert = 2203814451; |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111: | Show(); // Fenster anzeigen
bool[] feld = new bool[42];
int zaehler = 0;
int feldzaehler = 0;
int vierzaehler = 0;
int prozentler = 0;
// Zweierpotenzen berechnen
zweiHoch[0] = 1;
for (int i = 1; i < 43; i++)
zweiHoch[i] = (long) zweiHoch[i-1] * 2;
// %startwert in bool-Array umsetzen und ausgeben
for (int j = 0; j < 42; j++)
{
feld[j] = ((startwert / zweiHoch[j]) % 2 == 1);
Console.Write(feld[j] ? 1 : 0);
}
Console.WriteLine(string.Empty);
for (long i = startwert; i < 4398046511104; i++)
{
if (prozentler == 65536)
{
prozentler = 0;
Text = i.ToString() + " = " + ((float) (100f * ((float) i + 1f) / 4398046511104f)).ToString("0.0000") + "% ~ " + zaehler;
Application.DoEvents();
}
else
prozentler++;
// Felder setzen
for (int j = 0; j < 42; j++)
{
feld[j] = ! feld[j];
if (feld[j]) break;
}
// genau 21 Felder true
feldzaehler = 0;
for (int j = 0; j < 42; j++)
if (feld[j]) feldzaehler++;
if (feldzaehler != 21) continue;
// auszählen
// waagerecht (w-o)
for (int j = 0; j < 42 && vierzaehler < 3; j += 7)
for (int k = 0; k < 4 && vierzaehler < 3; k++)
{
vierzaehler = 0;
for (int l = 0; l < 3; l++)
{
if (feld[j + k + l] == feld[j + k + l + 1])
vierzaehler++;
else
break;
}
}
if (vierzaehler == 3) continue;
// senkrecht (n-s)
for (int j = 0; j < 21 && vierzaehler < 3; j += 7)
for (int k = 0; k < 7 && vierzaehler < 3; k++)
{
vierzaehler = 0;
for (int l = 0; l < 21; l += 7)
{
if (feld[j + k + l] == feld[j + k + l + 1])
vierzaehler++;
else
break;
}
}
if (vierzaehler == 3) continue;
// diagonal 1 (no-sw)
for (int j = 0; j < 21 && vierzaehler < 3; j += 7)
for (int k = 0; k < 4 && vierzaehler < 3; k++)
{
vierzaehler = 0;
for (int l = 0; l < 24; l += 8)
{
if (feld[j + k + l] == feld[j + k + l + 8])
vierzaehler++;
else
break;
}
}
if (vierzaehler == 3) continue;
// diagonal 1 (no-sw)
for (int j = 0; j < 21 && vierzaehler < 3; j += 7)
for (int k = 0; k < 4 && vierzaehler < 3; k++)
{
vierzaehler = 0;
for (int l = 0; l < 24; l += 8)
{
if (feld[j + k + l] == feld[j + k + l + 8])
vierzaehler++;
else
break;
}
}
if (vierzaehler < 3)
{
zaehler++;
Console.WriteLine(i.ToString());
}
}
Text = "fertig ~ " + zaehler; |
