4
$\begingroup$

Alice and Bob are playing a game. Alice starts by placing a knight on the chessboard. Then they take turns moving the knight to a new square (standard chess rules apply: the knight moves in an "L" shape). The first player who cannot move the knight to a new square loses the game. Who wins if both players play optimally, and what is the winning strategy?

This is a puzzle from Presh Talwalkar's youtube channel (https://www.youtube.com/watch?v=ZGWZM8PcUlY&ab_channel=MindYourDecisions) and the solution Presh gives is very clever and neat based on colouring 4×2 regions of the chessboard which is a bit unintuitive in my opinion or at least the video doesn't give an intuitive explanation on why consider these grids.

Since this seems like a classical nim as the game will eventually terminate with a winner I'm wondering if this is solvable without the clever usage of the 4×2 grids and colouring?

$\endgroup$
4
  • 1
    $\begingroup$ When you say 'new', does this mean a square not walked on by either player, or a square not walked on by the player making the move? $\endgroup$ Jul 20, 2023 at 22:19
  • 1
    $\begingroup$ It doesn't matter. Knights change color every move, so if Alice moves onto a square, Bob can't move onto that square. $\endgroup$ Jul 20, 2023 at 22:31
  • $\begingroup$ This is overkill, but the existence of knight's tours implies such a matching -- just take pairs of adjacent elements along the tour. $\endgroup$
    – xnor
    Jul 21, 2023 at 4:20
  • $\begingroup$ @xnor did you mean to post this comment to the answer? $\endgroup$
    – Bass
    Jul 21, 2023 at 7:45

1 Answer 1

9
$\begingroup$

Here is a solution without the 4x2 grids (although it is a generalization of that solution).

Pair up the squares such that the two squares in each pair are separated by a knight's move.

On each of Bob's moves, find the pair including the current square, and move to the other square of the pair. (Thus, after Bob's move, for all pairs, either both square have been visited or neither square has been visited, so Alice must move to a new pair.)

It is perhaps not immediately obvious that such a pairing is possible, but the 4x2 coloring solution is one simple way of doing this (which I think is quite natural and can be arrived at quite quickly). But, e.g. it can also be done using adjacent moves from a knight's tour.

$\endgroup$
2
  • $\begingroup$ This proves that Bob cannot lose, right? What about winning? $\endgroup$
    – daw
    Jul 21, 2023 at 6:51
  • 4
    $\begingroup$ Eventually all the squares are exhausted and someone loses. If it's not Bob, it's Alice. $\endgroup$
    – tehtmi
    Jul 21, 2023 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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