21
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – xnor
    Commented Jul 8, 2015 at 1:07
  • $\begingroup$ @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 $\endgroup$
    – Mike Earnest
    Commented Jul 8, 2015 at 1:35

3 Answers 3

Reset to default
25
$\begingroup$

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

Improve this answer
$\endgroup$
23
+100
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ 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! :) $\endgroup$
    – Mr Pie
    Commented Jul 6, 2019 at 2:44
  • $\begingroup$ @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.) $\endgroup$
    – Gareth McCaughan ♦
    Commented Jul 6, 2019 at 11:28
  • $\begingroup$ @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!" $\endgroup$
    – Mr Pie
    Commented Jul 6, 2019 at 11:50
9
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\begingroup$ This was the strategy I had in mind $\endgroup$
    – Mike Earnest
    Commented May 19, 2015 at 22:21
  • $\begingroup$ 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. $\endgroup$
    – xnor
    Commented May 20, 2015 at 21:02
  • $\begingroup$ Amusingly, this proof shows that Alice always wins, even if Bob cheats by making an illegal move with the knight. $\endgroup$
    – user3294068
    Commented Oct 2, 2015 at 18:36

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.