21

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?

f''
  • 33,665
  • 4
  • 120
  • 165
Mike Earnest
  • 32,336
  • 6
  • 92
  • 237
  • 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 08 '15 at 01: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 08 '15 at 01:35

3 Answers3

25

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.

enter image description here

User Not Found
  • 450
  • 4
  • 12
22

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.

xnor
  • 26,756
  • 4
  • 85
  • 144
  • 1
    Your answer was 2 minutes earlier than the accepted answer; also, your answer conceals the information to use as a strategy of solving the puzzle, whereas the accept answer only hides the picture. Consequently, I will award you a +100 rep bounty and boost you past 20k rep. Congratulations! :) – Mr Pie Jul 06 '19 at 02:44
  • @MrPie Interesting bounty choice. Neil's answer, while a little later than these two, generalizes enormously and (to my mind) does much more to explain what's going on. (I do agree that it seems like xnor was robbed a bit here.) – Gareth McCaughan Jul 06 '19 at 11:28
  • @GarethMcCaughan $\diamondsuit$ Admittedly, I saw xnor's 19.9k reputation and thought, "Eh, why not?" But the bounty was decided for xnor predominantly on the fact that their answer was sniped and that this is a good question (if it were a bad question, I would not wish to bump it up on the front page and potentially steal attention from a better question). I do not think it is entirely fair for someone to not get the recognition they deserve with the green checkmark because they were at least two seconds short of the accepted answer, but of course, as the saying goes: "There can be only one!" – Mr Pie Jul 06 '19 at 11:50
9

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).

Neil
  • 423
  • 4
  • 7