13
$\begingroup$

There is a castle with rooms arranged in a 4x4 square grid. The princess living in the castle sleeps in a different room each night, but always one adjacent to the one in which she slept in the previous night. She is free to choose any room in which to sleep on the first night. Three knights would like to find the princess, but she will not tell them where she is going to sleep each night. Each night every knight can look in a single room (not necessarily adjacent to their previous room). What strategy should the knights follow in order to guarantee that they find the princess as quickly as possible? How many nights do they need in order to find her?

Related puzzle with two knights: Two knights searching for a princess in a castle

Good luck!

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Given that the princess is not telling the knights where she sleeps, I am pretty sure the prefers to stay alone. This is a nice puzzle, but the implications feel a little but uneasy. Could it just be about wolf and sheep or something? $\endgroup$
    – Helena
    Sep 16, 2019 at 21:10
  • 1
    $\begingroup$ Hehe I didn't consider that. Perhaps the princess enjoys playing hide and seek, while the knights just want to give her some flowers. Anyway if it makes you feel better you can think of them as wolves searching for a sheep :) $\endgroup$
    – Dmitry Kamenetsky
    Sep 17, 2019 at 1:15

2 Answers 2

Reset to default
18
$\begingroup$

The knights need a maximum of:

12 nights to find the princess.

I made a quick drawing to show my strategy. The yellow squares are the rooms the knights look into that night, the black squares are rooms in which the princess logically cannot be.

On day 12 all rooms but two have been eliminated, meaning that if the knights have not found the princess already, they will find her on that day.

enter image description here

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ This is very cool and you have my upvote - just out of curiosity is there a way to prove optimality? $\endgroup$
    – hdsdv
    Sep 16, 2019 at 10:02
  • 1
    $\begingroup$ You got it! Well done. $\endgroup$
    – Dmitry Kamenetsky
    Sep 16, 2019 at 10:35
  • 1
    $\begingroup$ Your un-spoilered text gives away your answer... $\endgroup$
    – simonalexander2005
    Sep 16, 2019 at 14:22
  • $\begingroup$ Thanks @simonalexander2005 ! Changed it :) $\endgroup$
    – npkllr
    Sep 16, 2019 at 14:32
  • $\begingroup$ I was thinking of these as chess knights, only able to move in L-shapes - it seems to work that way for the odd-to-even numbered steps in your solution but not the even-to-odd ones. I wonder if that's just a coincidence? $\endgroup$
    – Darrel Hoffman
    Sep 16, 2019 at 18:11
1
$\begingroup$

The solution to this problem and its generalizations (more knights on larger grids) can be found in the following sequence:

https://oeis.org/A301860

You can see the actual solutions here:

https://oeis.org/A301860/a301860.txt

Improve this answer
$\endgroup$

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.