14
$\begingroup$

This question is inspired by this puzzle.

You have an $m \times n$ chessboard with $m \le n$. Alice and Bob alternately move the rook (horizontally or vertically, through any number of squares). As the rook moves, it leaves a trail of painted squares: every square through which the rook passes or at which the rook stops is painted red. The rook is not allowed to pass through a red square nor can it stop on a red square. The first player who cannot move loses the game.

As seen in the original version of this puzzle, if the rook starts in a corner, the first player (Alice) can always force a win. But what if the rook does not start in the corner?

Are there any sized boards and starting positions in which the second player (Bob) can force a win?

Example:

Here is an example of the $n=m=3$ board where the rook starts in the middle. Alice can force a win by always moving 1 square until she can take all the remaining squares.

enter image description here

It is easy to see that the other starting squares are also winnable by Alice, thus, all squares in the $n=m=3$ board are winnable by Alice.

Note: I don't know the answer to this one. I've ruled out some initial sized boards, but a general proof for Alice being able to win all, or a counter example where Bob can win has thus far eluded me. I thought I had a simple solution, but then found a counter example for my strategy. I will have to think on it some more.

Note 2: I figured it out. Wasn't that difficult in the end after all. I will post it as an answer in a week or two if someone hasn't answered by then.

$\endgroup$
5
$\begingroup$

The solution seems rather simple. (Everything below is a spoiler)


The $m×n$ board is the same as an $n×m$ board. So WLOG we will assume that $m≤n$ , i.e. length of rows is $\le$ than length of columns.

We can analyze all possible scenarios if Alice uses the method from the previous puzzles answer.


$$1. \text{ Starting in a corner}$$

As seen in the previous puzzles answer, Alice can always force a win if she moves in columns when she starts in a corner. She chooses to move in columns rather than rows to prevent the possibility of a spiral case, which is also shortly and simply covered in the previous puzzles answer. (Note that Rows and Columns are reversed in this answer relative to the previous puzzles answer, since I decided to reference the previous puzzles answer instead of explaining the already explained.)

$$2. \text{ Starting on a border}$$

The case is the same if she starts anywhere on the shorter border of the board. She simply takes a column, after which the game reduces to the previous case where Alice is starting in a corner. This is because the board gets split in $2$ boards, and Bobs move simply enters from a corner on either boards using a row, allowing Alice to continue taking columns as if it were the first case, already solved in her favor. The longer border is realted to the third case, since the first column can't be fully taken.

$$3. \text{ Starting on inner spots of the board}$$

There's one extra thing to look out for when Alice isn't starting on a shorter border or corners. In this case, it happens that the first column she takes isn't fully taken. Bob can attempt to exploit this.
When she is about to take a column, and the Bobs next move can end up in finishing the column that isn't fully taken, she instead of taking the full column, should leave one spot empty.
This is because if Bob were to finish her column now, she would end up taking a row and the Bob would overtake her winning position.
Thus she leaves one spot empty so she can finish her other column afterwards (since there are $2$ unfinished columns now), canceling out the Bobs column take and keeping her advantage.

If Bob were to not finish her new unfinished column, and continue moving in rows, Alice would either end up taking the winning column, or if there is more than $1$ consecutive columns in the direction that Bob moved, she can again make another unfinished column to prevent Bob from ending up being the one to finish them. This guarantees her to eventually win or force Bob to be the first one to take an unfinished column, after which she can row out all finishable unfinished columns, keeping her advantage.

There is a second possible scenario, where Bob rows into the unfinished column, but does not finish it. Alice can simply finish the column herself and the game continues in her favor, possibly leaving another unfinished column afterwards, which again can be resolved as explained before.


Alice can always force a win.

$\endgroup$
  • $\begingroup$ I think this is the right answer, but perhaps a bit more rigour is needed to really prove that this is correct. How do we know that Bob can't somehow get into a situation where he is in control of the initiative again? In the 3x3 scenario, Alice has 2 situations where she must be careful not to let Bob trap her. Are we positive that there can be no other times Bob can force her, maybe even 2 or three moves ahead of the obvious "gotcha"? $\endgroup$ – Trenin Mar 9 '17 at 19:13
  • $\begingroup$ Also, you mention that columns are longer than rows, but I don't see how this fact becomes critical in your proof. It is very important, but it is not obvious why it is so. $\endgroup$ – Trenin Mar 9 '17 at 19:14
  • $\begingroup$ @Trenin I updated my answer, explaining the only possible scenarios where bob could take over the board, and referencing the previous puzzle regarding the importance of choosing columns over rows. I hope I covered your concerns this time. $\endgroup$ – Vepir Mar 11 '17 at 9:31
  • $\begingroup$ In case 2 (starting on a border), aren't you assuming the column is not parallel to that border (i.e. assuming you start on the short edge of the rectangle)? To be honest, I don't follow your description of the strategy in case 3. Some pictures would definitely help. $\endgroup$ – Jaap Scherphuis Mar 11 '17 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.