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:
- 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.
Yes, the first player wins on an odd x odd board if the knight starts on gray square (where the board is colored like a checkerboard such that the corners are blue).
To describe the first player's winning strategy, tile almost all of the board with dominoes, where only one corner is uncovered. The first move will be to the other half of the domino containing the starting square. For all subsequent moves, the second player will move into a new domino, and the first player moves to the other square in that domino.
Note that the second player can never move onto the uncovered square, because the second player always moves onto a gray square.
Best Answer
Let's first imagine $r\times k$ is uneven. This means that if we ignore the starting square we can divide the grid into pairs of two (look at the image). The first player always has to tread on the first square of a pair, whilst the second player always can tread on the second square of a pair. Since every pair is whole, i.e. there's no lone square (except for the starting one naturally), the second player will always do the last move. So the winning strategy for the second player is to always move to the same color that it is currently standing on. If the product is even then we don't ignore the first square. The starting square is therefore in a pair, which means that it is the first player that has the ability to move to the second square of a pair. Using a strategy-stealing argument it is clear that the first player has the winning strategy by using the same one that the second player had in the uneven case.