# Knight on a 5 by 5 board

Alice and Bob play a game with a $5\times 5$ chessboard, and a chess knight. Alice begins by placing the knight somewhere on the board. Then, starting with Bob, the players alternate moving the knight (the way it moves in chess) to a square it hasn't occupied before. If a player has no legal moves, he/she loses.

Which player wins under optimal play, and how?

• Looking back, I think this puzzle is better presented on an 8x8 board. It's large enough to avoid strategies with forced moves, the winner is the second player which is more surprising, and 8x8 is the standard size of a chessboard anyway. – xnor Jul 8 '15 at 1:07
• @xnor I hadn't anticipated Alice being able to force so many of Bob's moves on the 5x5! What I didn't like about the 8x8 version was that its really easy to pair up squares so that each pair is a knight's move apart, which quickly yields Bob's strategy. I think 7x7 would be good for this – Mike Earnest Jul 8 '15 at 1:35

Alice starts and wins

As shown below Alice gives the red moves and Bob gives blue moves... Moves 2 and 10 have symmetrical options which end up with same result. All other moves are forced.

The winner is:

Alice

The winning strategy is to

Alice places the knight in the corner, and forces the following sequence of moves, with Alice making the odd-numbered moves and Bob making the even-numbered ones:
01 10 21 16 07 20 15 08 11 22 09 02 25 06 17 14 19 04 23 12 03 24 13 18 05
Note that each of Bob's moves (even numbers) is forced because there's only one available unvisited square, except for 02 and 10, in which the two options are symmetrical and equivalent. Alice makes Bob trace out a path that visits the four corners, then makes laps clockwise, and finally she takes the last remaining cell of the center.

Alice can always win by picking any square of the 13 of the same colour.

Proof.

Consider an open Knight's Tour of the 5x5 board. Remove any square at an odd position in the tour, which becomes the starting square, and divide the tour up into pairs of squares. Whichever square Bob moves to, Alice simply moves to matching square from her list of pairs.

Example.

1 14 9 20 3
24 19 2 15 10
13 8 25 4 21
18 23 6 11 16
7 12 17 22 5
Alice wishes to start on (5, 3) [17]; if Bob moves to (4, 1) Alice moves to (2, 2); if Bob moves to (3, 2) Alice moves to (5, 1); if Bob moves to (3, 4) Alice moves to (1, 5) and if Bob moves to (4, 5) Alice moves to (2, 4).

• This was the strategy I had in mind – Mike Earnest May 19 '15 at 22:21
• What a pretty and flexible proof! Since there's open knight tours on all boards at least 4x5, this extends to 7x7, 9x9, 11x11,... boards. – xnor May 20 '15 at 21:02
• Amusingly, this proof shows that Alice always wins, even if Bob cheats by making an illegal move with the knight. – user3294068 Oct 2 '15 at 18:36