Board Game |
A surprisingly complex game can be played between two players on a simple one-dimensional board with up to 60 holes; each player has counters of one colour (indicated here by letters like W or R) which go into the holes. A player may move a counter anywhere on the board, as long as it does not land on or jump over any other counter. The object of the game is to block the other player so he or she has no allowable moves. In a game with one counter each, the first player can force a win on the first move by moving their counter next to the other counter. Whenever the second player tries to move away, the first player moves next to them. Eventually the second player will have no moves left. If the first player does not take this first move, then the second player can force a win. Convince yourself that these statements are true in this example:
W | R |
With two counters each, the game is more complex. For example, in the following situation, if W moves first they can force a win by moving the leftmost counter one square to the right, or the rightmost counter one square to the left. Any other move (for example, moving one of the W counters next to an R counter) will mean than R can force a win. Try it and convince yourself this is true.
W | R | W | R |
Even more complex situations arise with more counters; for example, draws can occur (ie neither player can force a win) as in the following case:
W | W | R | W | R | R |
It is embarrassing that it is difficult to see how to win such a simple game. Please write a program so that I can play this safely by always knowing the winning first move, or, when there is no winning first move, whether the game is lost or can be drawn. Assume that a player will always win the game if it is in their power, and will always try to avoid defeat.
000200100000 000100200102 000010201002 000010200102 001020020001100002000 010122010122 0
1 7 5 1 4 5 1 5 4 2 1 13 15 1 2 1