7
$\begingroup$

Knight Puzzle

Imagine a chessboard like this:

pic1

You are the white knight and can move as a knight does in chess.

Example:

pic2

Your goal is to visit every square on the board using legal chess knight moves while never touching a square you have already visited. However, someone is trying to stop you in your quest! They are the black knight:

pic3

Every time you make a move, the black knight makes a move, also (and follows the same rules that you do). You cannot move to where the black knight is, nor can you touch any of the squares the black knight has visited.

Your question is this: What is the minimum number of turns required for the black knight to ensure that you have no legal move to make? Show the game in your answer.

The person who has the smallest number of moves (tiebreaker is time) by July 1st’s answer will be accepted and (possibly) a bounty will be awarded depending on the popularity of this question.

Note: this is not an open-ended question... There is a smallest number of moves!

Improve this question
$\endgroup$
11
  • $\begingroup$ @hexomino -- Sorry I should have been more clear. No you cannot. (just made the edit :):)) $\endgroup$
    – Voldemort's Wrath
    Jun 24, 2020 at 21:13
  • $\begingroup$ The green circles in your diagram represent the 1st and 2nd moves of the knight I imagine. The top circles are not in the correct squares if so. $\endgroup$
    – MrJman006
    Jun 24, 2020 at 21:21
  • 1
    $\begingroup$ Oh, one more question. Can the black knight capture the white or do we care about that? $\endgroup$
    – hexomino
    Jun 24, 2020 at 21:24
  • 1
    $\begingroup$ @MrJman006 -- They are correct... And yes, they do represent the first two example moves. $\endgroup$
    – Voldemort's Wrath
    Jun 24, 2020 at 23:14
  • 1
    $\begingroup$ In the case of 3x3 board, after 1. Na2 Nb1 2. Nc3, black has no legal move, but white will have no legal move by the next move as well. Does this count as 2 or 1? Black knight only took one turn, and it ensured that white will have no legal move to make. $\endgroup$
    – justhalf
    Jun 25, 2020 at 8:41

3 Answers 3

Reset to default
5
$\begingroup$

Hopefully I understood the rules correctly. Assuming white does not have to play optimally, I was able to leave no legal moves for white after 5 moves:

1. Ng3 Nc7 2. Nf1 Nb5 3. Ne3 Nd4 4. Nc2 Nb3 5. Na1 (any legal move)

Then white's knight cannot go to c2 (already visited by white) or b3 (already visited by black), the only two possible moves. I haven't been able to show that this is the smallest number of moves, but it does seem to be the smallest number of moves for trapping the white knight in one of the corners, and that struck me as the best way to trap the white knight quickly.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ I'm pretty sure both players are trying to play optimally. "Ensure you have no move", "your goal is to visit every square on the board", etc. $\endgroup$
    – Quintec
    Jun 25, 2020 at 0:10
  • 2
    $\begingroup$ Mm, then my issue is "optimal" play is not well-defined. There is no way white can visit every square, so is it just to maximize the number of squares visited? Or to trap the other player first? Since the players' moves would be co-dependent, it's also not clear how to "show the game" unless you enumerate all the viable sequences of moves. $\endgroup$
    – BrainEaser
    Jun 25, 2020 at 0:31
  • $\begingroup$ @BrainEaser -- The goal for the white knight is to visit as many squares as possible. The goal for the black knight is to stop the white knight. $\endgroup$
    – Voldemort's Wrath
    Jun 25, 2020 at 2:36
  • 1
    $\begingroup$ @Voldemort'sWrath If the white knight doesn't have to make smart moves, then surely this solution must be optimal. $\endgroup$
    – Bass
    Jun 25, 2020 at 8:59
  • 3
    $\begingroup$ I feel like the wording of "What is the minimum number of turns required for the black knight to ensure that you have no legal move to make?" should imply that it should work for any line that white attempts to make. I feel like that should either be reworded or we should be assuming optimal play from white. $\endgroup$
    – Michael Moschella
    Jun 25, 2020 at 14:48
1
$\begingroup$

Having seen the clarification in the comments of the OP, it would seem that:

Black's strategy should be to trap himself and not worry about white. Since, if Black cannot move, the game is over. I haven't looked at this too closely, because maybe White can interfere with the plan, but it seems that wedging himself into a corner can be done within 7 moves.

You'd need to do something like: Na8-c7-e8-d6-f7 (blocking one exit from h8. If white has already gone to g6, then just go to h8 already. And if white's already gone there, then he's there right now and you've blocked him).

Then e5-g6-h8 and you're done. I guess the problem is if White goes and takes g6. But there's plenty of other options available. E.g. go to the opposite corner, or go Na8-b6-c8-e7-c6-d4-b6-a7 (where the bold ones provide the blocking from his final resting place of a7).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Though the black knight would have no legal move if they were trapped, the white knight would still have legal moves, so the game would not have ended. $\endgroup$
    – Voldemort's Wrath
    Jun 29, 2020 at 15:45
  • $\begingroup$ Okay, so white could just keep going and black would be stuck? $\endgroup$
    – Dr Xorile
    Jun 29, 2020 at 15:47
  • $\begingroup$ Yes, indeed.... $\endgroup$
    – Voldemort's Wrath
    Jun 29, 2020 at 20:10
1
$\begingroup$

Here is a strategy for Black that ensures that White eventually has no moves anymore:

Black just has to mirror White's moves (i.e. if White moves two up one left, than Black moves two down one right). In that way, Black always can move, while eventually White has no moves left.

After at most 32 steps White cannot move anymore.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I think that might be the worst possible strategy! :-) White might then be able to find a solution with 32 $\endgroup$
    – Dr Xorile
    Jun 29, 2020 at 20:43
  • $\begingroup$ Actually, correction. My answer has an even worse strategy, since it turns out that white can move consecutively if black gets blocked. So yours at least gets you to a worst case of 32 moves. $\endgroup$
    – Dr Xorile
    Jun 29, 2020 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.