# Three knights searching for a princess in a castle

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!

• 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? Sep 16, 2019 at 21:10
• 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 :) Sep 17, 2019 at 1:15

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.

• This is very cool and you have my upvote - just out of curiosity is there a way to prove optimality? Sep 16, 2019 at 10:02
• You got it! Well done. Sep 16, 2019 at 10:35