4
$\begingroup$

Perhaps, this game is already known, but I did not find anything about it, I call it "knight".

The rules :

Player 1 chooses the starting square of a knight on a normal 8x8 - chessboard. The players alternately move the knight to a square which was not already visited. The player having no more move loses.

Which player has a winning strategy and why ?

$\endgroup$
  • $\begingroup$ Just to clarify. Player 2 makes the first move with the knight after Player 1 has chosen the starting square. $\endgroup$ – Peter Aug 14 '14 at 9:30
  • $\begingroup$ On a 4x4 - board, Player 2 has a winning strategy. On a 5x5 - board, Player 1 has a winning strategy. $\endgroup$ – Peter Aug 14 '14 at 10:27
  • 1
    $\begingroup$ Maybe obvious, but can you clarify that the players can only move the knight like it is a chess knight? $\endgroup$ – Jonny Mar 21 '15 at 2:29
  • $\begingroup$ Related: youtube.com/watch?v=ZGWZM8PcUlY $\endgroup$ – Gabriel Romon May 4 '18 at 10:24
  • $\begingroup$ Any particular reason you haven't accepted this answer (or my answer to your similar question on chess.stackexchange.com)? Do you have some question about it, or are you just waiting to see if someone posts a better answer? $\endgroup$ – bof Nov 30 '18 at 9:02
12
$\begingroup$

The $m\times n$ knight's graph is the graph whose vertices are the squares of the $m\times n$ chessboard, two squares being adjacent if a knight can move from one to the other.

Player 2 has an obvious winning strategy on the $m\times n$ chessboard if the corresponding knight's graph has a perfect matching; namely, he moves the knight to the square which is matched with the knight's current square. In particular, assuming $mn$ is even, Player 2 has a winning strategy if the knight's graph has a Hamiltonian path; in chessic terms, if a knight's tour (open or closed) exists.

Hence Player 2 has a winning strategy on the normal $8\times8$ chessboard and many others. Namely, Player 2 has a winning strategy on boards of the following sizes:
(a) $m\times n$ where $m,n\ge5$ and $mn$ is even;
(b) $2\times n$ where $n$ is divisible by $4$;
(c) $3\times n$ where $n$ is even and $n\ge4$;
(d) $4\times n$ where $n\ge2$.

For case (a) we can use the fact that a knight's tour exists. For the remaining cases, it suffices to observe that the $2\times4$, $3\times4$, and $3\times6$ knight's graphs have perfect matchings, since the boards in cases (b), (c), and (d) can be tiled with $2\times4$, $3\times4$, and $3\times6$ boards.

In a similar way, it can be shown that Player 1 wins in all other cases. That is, Player 1 has a winning strategy on boards of the following sizes:
(e) $m\times n$ where $mn$ is odd;
(f) $1\times n$ where $n\ge1$;
(g) $2\times n$ where $n$ is not divisible by $4$.

Example. Here is a "perfect matching" for the ordinary $8\times8$ chessboard:

a1c2, b1d2, c1a2, d1b2, e1g2, f1h2, g1e2, h1f2,
a3c4, b3d4, c3a4, d3b4, e3g4, f3h4, g3e4, h3f4,
a5c6, b5d6, c5a6, d5b6, e5g6, f5h6, g5e6, h5f6,
a7c8, b7d8, c7a8, d7b8, e7g8, f7h8, g7e8, h7f8.

That is, square a1 is paired with square c2, b1 is paired with d2, and so on. Note that the 64 squares are partitioned into nonoverlapping pairs, and each set of paired squares are a knight's move apart. The winning strategy for Player 2 is: WHEREVER PLAYER 1 PUTS THE KNIGHT, MOVE IT TO THE OTHER SQUARE IN THE SAME PAIR. For instance, if Player 1 starts the game by dropping the knight on e8, Player 2 replies by playing Ng7. If Player 1 now plays Ne6, Player 2 plays Ng5, and so on. Here is a sample game, with Player 1 making random moves, and Player 2 following the winning strategy described above:

  1. Ne8 Ng7 2. Ne6 Ng5 3. Nf3 Nh4 4. Nf5 Nh6 5. Nf7 Nh8 6. Ng6 Ne5 7. Nc6 Na5 8. Nb3 Nd4 9. Ne2 Ng1 10. Nh3 Nf4 11. Nh5 Nf6 12. Ng4 Ne3 13. Nc5 Na3 14. Nb1 Nd2 15. Nf1 Nh2 and Player 2 wins.

P.S. Of course the strategy still works if White is allowed to move the knight to any square not already visited, and only Black is limited to making knight moves.

$\endgroup$
  • $\begingroup$ Why is a knight's tour sufficient to prove a winning strategy? No matter where player one moves the knight's tour still exists? $\endgroup$ – Jonny Mar 21 '15 at 2:32
  • 1
    $\begingroup$ @Jonny Because if there's a knight's tour (on a board with an even number of squares) then there's a matching: we can match square 1 of the knight's tour with square 2, square 3 with square 4, and so on. Then the winning strategy for Player 2 is, whenever Player 1 puts the knight on a square, move it to the matched square. $\endgroup$ – bof Mar 21 '15 at 2:38
  • 1
    $\begingroup$ need a few examples to demonstrate the words. $\endgroup$ – JLee Mar 21 '15 at 2:42
  • $\begingroup$ i'm not following what you are saying, and i thought an example, with an actual 8x8 board and some moves and explanations might help. no need to speak to other boards and answer other questions. 8x8 is the question. $\endgroup$ – JLee Mar 21 '15 at 2:59
  • $\begingroup$ excellent! thanks. $\endgroup$ – JLee Mar 23 '15 at 16:05

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.