12
$\begingroup$

The king is on a chessboard filled with poison ivy bushes. Can the king get to safety?

Details:

The king is initially located at the top left-hand corner square of the chessboard.

The finite chessboard is of size $n \times n$ where $n \ge 4$.

There are $n$ poison ivy bushes each on a different square of the chessboard.

Two poison ivy bushes are never in the same horizontal row, vertical column or any diagonal.

The above restriction on the poison ivy bushes is the same as the restriction on the queens in the Eight Queens Puzzle.

If the king moves to a square that contains a poison ivy bush, the king suffers greatly.

The king’s initial square and the safety square (which is located at the lower right-hand corner square of the chessboard) do not contain poison ivy bushes.

At any point in time, the king can only move either one square down or one square to the right. The king can not move diagonally.

The king has limited vision and can see if there are poison ivy bushes in the two squares that he can move to but not other squares.

The king knows all the above information (including the value of $n$) but does not know where the poison ivy bushes are located.

QUESTION:

Is there a strategy that would allow the king to succeed in moving to the safety square without ever moving to a square that contains a poison ivy bush? For the strategy to be valid, it must allow the king to avoid all the poison ivy bushes no matter where they are located and no matter how large the chessboard is.

$\endgroup$
1
  • 10
    $\begingroup$ Another missed opportunity to use the wazir $\endgroup$
    – Jafe
    Sep 3, 2023 at 1:21

1 Answer 1

18
$\begingroup$

The king can get to safety via this simple strategy:

  • Look upon the squares on the main diagonal. Think of each square as a jumping target.

(Image: Light gray squares represent the position of the king, or the position of a diagonal square, blue squares represent the king's path, and red squares represent ivies.

  • If you are forced to move down from a diagonal square due to a poison ivy square, immediately move right to the next diagonal square. This is safe due to the ivies not being horizontally adjacent.

example1

  • Otherwise, move right. If you find that the next diagonal square has an ivy by vision, run around it, moving right, down 2. This is possible because of the queens requirement that the ivies not be horizontally, vertically or diagonally adjacent.

example2

  • Else, move down to the next diagonal square.

Here is an example with an $8$ by $8$ board:

8x8 board

$\endgroup$
2
  • $\begingroup$ @WillOctagonGibson Thanks for the feedback, I have attempted to add some helpful visuals $\endgroup$ Sep 2, 2023 at 23:57
  • $\begingroup$ Summary (rot13): 1.) Qba'g jnyx va gur cbvfba vil. 2.) Fgnl ba gur qvntbany. $\endgroup$ Sep 4, 2023 at 6:42

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.