The program below makes all possible sequences of moves, recursively seeking all possible states of the system. The first time through a given set of numbers of red, white and blue balls it continues with all possibilities from there; the second time it reaches the same set, it does not continue, as the possibilities starting from there have already been exhausted.
DefDbl A-Z
Dim crlf$, hadstate(12, 12, 12), red, white, blue, h(50), lvl
Private Sub Form_Load()
Form1.Visible = True
Text1.Text = ""
crlf = Chr$(13) + Chr$(10)
red = 3: white = 4: blue = 5
hadstate(red, white, blue) = 1
makeMove
Text1.Text = Text1.Text & crlf & crlf
For red = 0 To 12
For white = 0 To 12
For blue = 0 To 12
If hadstate(red, white, blue) Then
Text1.Text = Text1.Text & red & Str(white) & Str(blue) & crlf
DoEvents
End If
Next
Next
Next
Text1.Text = Text1.Text & crlf & " done"
End Sub
Sub makeMove()
For a = 1 To 2
For b = a + 1 To 3
c = 6 - a - b
Select Case c
Case 1
red = red + 2
white = white - 1
blue = blue - 1
Case 2
white = white + 2
red = red - 1
blue = blue - 1
Case 3
blue = blue + 2
white = white - 1
red = red - 1
End Select
If red >= 0 And red <= 12 Then
If white >= 0 And white <= 12 Then
If blue >= 0 And blue <= 12 Then
If hadstate(red, white, blue) = 0 Then
hadstate(red, white, blue) = 1
lvl = lvl + 1
h(lvl) = c
Text1.Text = Text1.Text & red & Str(white) & Str(blue) & " "
For mno = 1 To lvl
Text1.Text = Text1.Text & Mid("rwb", h(mno), 1)
Next mno
Text1.Text = Text1.Text & crlf
makeMove
lvl = lvl - 1
End If
End If
End If
End If
Select Case c
Case 1
red = red - 2
white = white + 1
blue = blue + 1
Case 2
white = white - 2
red = red + 1
blue = blue + 1
Case 3
blue = blue - 2
white = white + 1
red = red + 1
End Select
Next
Next
End Sub
The only reachable states are shown below with the sequence of moves needed to get there. Each step of the sequence is indicated by the starting letter of the color that gained two balls in the process of that step:
R W B
2 3 7 b
1 2 9 bb
0 1 11 bbb
2 0 10 bbbr
0 4 8 bbw
3 1 8 bbr
5 0 7 bbrr
4 2 6 bbrrw
6 1 5 bbrrwr
5 3 4 bbrrwrw
4 5 3 bbrrwrww
3 7 2 bbrrwrwww
2 6 4 bbrrwrwwwb
1 5 6 bbrrwrwwwbb
0 7 5 bbrrwrwwwbbw
1 8 3 bbrrwrwwwbw
0 10 2 bbrrwrwwwbww
2 9 1 bbrrwrwwwbwwr
1 11 0 bbrrwrwwwbwwrw
4 8 0 bbrrwrwwwbwwrr
5 6 1 bbrrwrwwwr
7 5 0 bbrrwrwwwrr
6 4 2 bbrrwrwwwrrb
8 3 1 bbrrwrwwwrrbr
7 2 3 bbrrwrwwwrrbrb
9 1 2 bbrrwrwwwrrbrbr
8 0 4 bbrrwrwwwrrbrbrb
11 0 1 bbrrwrwwwrrbrbrr
10 2 0 bbrrwrwwwrrbrbrrw
All the possible states in a sorted sequence, including the initial state:
0 1 11
0 4 8
0 7 5
0 10 2
1 2 9
1 5 6
1 8 3
1 11 0
2 0 10
2 3 7
2 6 4
2 9 1
3 1 8
3 4 5
3 7 2
4 2 6
4 5 3
4 8 0
5 0 7
5 3 4
5 6 1
6 1 5
6 4 2
7 2 3
7 5 0
8 0 4
8 3 1
9 1 2
10 2 0
11 0 1
Of course, for example, bbrrwrwwwb is the hard way to get to (2,6,4), where merely w would get there right away. It's just that the algorithm explores all sequences starting with b first. (Why b? It actually chooses which to decrease, and starts with r and w.)
None of these states have 12 of one color and zero of each of the other two.
|
|
Posted by Charlie
on 2015-07-29 14:35:28 |
computer proof
