Three knights searching for a princess in a castle

Question

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? — Helena, Sep 16 '19 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 :) — Dmitry Kamenetsky, Sep 17 '19 at 01:15

npkllr · Accepted Answer · 2019-09-16T14:31:49.723

18

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.

edited Sep 16 '19 at 14:31

answered Sep 16 '19 at 09:56

npkllr

1,584
1
10
21

2

This is very cool and you have my upvote - just out of curiosity is there a way to prove optimality? – hdsdv Sep 16 '19 at 10:02
1

You got it! Well done. – Dmitry Kamenetsky Sep 16 '19 at 10:35
1

Your un-spoilered text gives away your answer... – simonalexander2005 Sep 16 '19 at 14:22
Thanks @simonalexander2005 ! Changed it :) – npkllr Sep 16 '19 at 14:32
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? – Darrel Hoffman Sep 16 '19 at 18:11
It is interesting that you didn't even use the third knight on step 6. – Dmitry Kamenetsky Sep 17 '19 at 06:54

Dmitry Kamenetsky · Answer 2 · 2019-09-17T06:53:16.380

1

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

edited Sep 17 '19 at 06:53

answered Sep 17 '19 at 01:13

Dmitry Kamenetsky

35,897
5
66
276

Three knights searching for a princess in a castle

2 Answers2