Math Board Game Puzzle?

Question

I am trying to find a solution to this board game problem this is how it goes.

Mike and Bob are playing a board game on an m by n board. The board has at least 3 rows and 3 columns. The bottom row is row 0 and the top row is row m − 1; the left-most column is column 0 and the right-most column is column n − 1.

Mike moves first, then Bob, then Mike, then Bob, etc. until the game is over. The game is over when one of two things happens: Bob wins or Mike wins.

• Bob wins if he lands on the same square as Mike before Mike reaches the top row. Note that this winning condition is checked only after Bob moves; Bob can never win right after Mike moves, even if Mike lands on the same square as Bob
• Mike wins if Mike reaches the top row before Bob wins, i.e., Mike reaches the top row without Bob ever landing on the same square as Mike. As soon as Mike reaches the top row, Mike wins (Bob cannot move anymore).

Mike’s move on each turn is fixed according to the following rule: he goes 1 square up and then, if not already at the right edge, goes 1 square to the right as well.

Bob, by contrast, has eight choices of move to make on his turn:

1. 1 up, 2 right
2. 1 up, 2 left
3. 1 down, 2 right
4. 1 down, 2 left
5. 2 up, 1 right
6. 2 up, 1 left
7. 2 down, 1 right
8. 2 down, 1 left

Note that some moves may be unavailable depending on Bob’s location; for example, if Bob is already in column n − 1, then any move that tries to go to the right is not allowed.

Given the starting locations of Mike and Bod, come up with a solution that determines the result of the game, as follows:

• If it is possible for Bob to win, then report that Bob can win and give the minimum number of Bob moves required for him to win.
• Otherwise, Mike wins; report the number of Bob moves that occur before Mike wins

we can assume that

• Mike’s starting location is never in the top row
• Bob’s starting location is never the same as Mike’s

we can use any type of methods we like, the only real restriction to solving this problem are mentioned above. How would we approach a question like this.

Answer 1

Notation

First note that Mike has a fixed, predefined movement strategy.

Let us denote by M₀, M₁, .., M_k the cells that Mike would go through in his path towards the top row. Here M₀ is the starting cell of Mike, and M_k is the cell on the top row that Mike would reach if Bob would not intervene.

Additionally, let us denote by B₀ the cell where Bob starts from. According to the statement it is guaranteed that B₀ is different from M₀.

Reformulation

The question is whether there is sequence of i moves for Bob, B₀ -> B₁ -> .. -> B_i such that B_i = M_i, for an i between 1 and k - 1.

Approach

One possible approach is to generate the list of all possible cells that can be reached in exactly i moves, for any i.

For i = 0, there is a single cell that can be reached by Bob, the starting position B₀.

Afterwards, for i = 1, 2, .. k - 1, we should consider every cell that can be reached in i - 1 steps (we already know this set of cells), and perform each legal move for Bob. The resulting list of positions would be the set of cells reachable in i steps.

Now that we found the cells that can be reached in i steps by Bob, we should simply check whether M_i is in that set. If this happens for at least one i between 1 and k - 1, then Bob wins.

Implementation

For efficiency, it is important to make sure that if the same cell is reached from different sources in the same number of steps, i, then the duplicates are stored only once.

This removal of duplicates is essential, because otherwise the size of the list of reachable cells would grow exponentially with i.

One approach would be to maintain an m by n matrix of booleans for each i, specifying whether the respective cell can be reached in i steps. Improvements in terms of memory are possible, such that only the matrix of booleans for the current i is maintained (along with a temporary matrix to help advancing towards the next set), but a little bit more care would be needed in that case.

Answer 2

Old topic, but I feel like puzzling for a moment: Start by general observations On a 3 by 3 board Mike wins in exactly 4 starting positions, namey those where Bob has to move to (1, 2) (order of coordinates here m before n, i.e. not common to chess notations) und Mike can move there. If Bob moves onto Mike's square, Mike can win the very next move or never at all, because he generally needs two moves from Bob's square to Bob's next square. So as long as Bob moves diagonally it is just a matter of distance and speed (Mike is 50% faster, just calculate distance to Bob's diagonal). On the right border Mike is 100% faster. He still has to catch up before the top. Plus Mike has no way of winning if both players end up on different colors on one and those each move.