All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 3x3 Nim (Posted on 2009-06-25)
A 3x3 array of counters is laid out. Players take turns removing counters. The rule for removing counters is to pick a row or column and take any 1,2 or 3 from it. Whoever removes the last counter wins.

Does the first or second player have a winning strategy?
What is this strategy?

 See The Solution Submitted by Jer Rating: 4.0000 (7 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 nim value equivalents | Comment 24 of 26 |

The game board is not modified by rotating or reflecting it, obviously.  It is also not affected by permuting the rows or colums.  The two boards below are equivalent, differing only in the permutation of rows and columns:

`X..  XX.XX.  XXXXXX  X..`

This can be applied to all game boards to reduce the number of cases to a core of 26.  Each board is labeled with an ID, the nim value of the board, and a list of boards which are results of legal moves.  The nim value is calculated by looking at the nim values of the possible results of legal moves and finding the smallest number not in that list.

`...  ...  ...  ...  ...  ...   ...   X.....  ...  ...  X..  ...  X..   X..   .X....  X..  XX.  .X.  XXX  .XX   XX.   ..X`
`Z    A    B1   B2   C1   C2    C3    C40    1    2    0    3    3     3     1     Z    Z,A  A    Z,A  A,B1  A,B1  B2                    B1   B2    B2`
`...    ...    ...    X..    ..X    ...    X..    XX.    ..X    X..X..    XX.    XX.    X..    XX.    XX.    X..    .XX    XX.    XX.XXX    XX.    .XX    .XX    .X.    XXX    XXX    .X.    XX.    .XX`
`D1     D2     D3     D4     D5     E1     E2     E3     E4     E54      0      1      0      2      5      1      5      1      4A,B1   B1,C3  B1,B2  B1,C2  B2,C2  B1,C1  B1,C1  B2,C2  C2,D2  C3,D3B2,C1         C2,C3         C3,C4  C2,C3  C2,D1  C3,C4  D5     D4,D5C2,C3                              D1,D2  D4     D1,D3                                   D3            D5`
`...    X..    X..    .XX    X..    XX.    XX.    XXXXXX    XX.    XXX    X.X    XXX    X.X    XXX    XXXXXX    XXX    .XX    XX.    XXX    XXX    XXX    XXX`
`F1     F2     F3     F4     G1     G2     H      I1      0      6      0      2      2      3      0C1,D1  C3,D1  C2,D1  D3,E5  D1,D2  D3,E1  E1,F1  F1,G1D2,E1  D3,D5  D2,D3         E1,E2  E3,E5  F2,F3  H       E1,E2  D4,D5         E3,E4  F2,F3  G1,G2       E3,E5  E1,E3         F1,F2  F4              E4,E5         F3`

The zero nim values I calculated are the full board (I), the empty board (Z), and boards B2, D2, D4, F2, and F4.

 Posted by Brian Smith on 2009-06-29 01:15:18

 Search: Search body:
Forums (0)