# Two knights searching for a princess in a castle

There is a castle with rooms arranged in a 3x3 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 on the previous night. She is free to choose any room in which to sleep on the first night. Two 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 one knight and rooms arranged in a row: Why does this solution guarantee that the prince knocks on the right door to find the princess?

Good luck!

Just as in the previous problem,

the two cases of different parity must be handled entirely independently. A single knight cannot prevent any room from being inaccessible, and so checking rooms of opposite parity will never be helpful.

So we start by

assuming that the princess starts on one of the four edge cells.

Numbering the cells

789
456
123


you can check

4 and 2 first, to eliminate 1 as an option for her next move. (If you don't eliminate an option, then the check is guaranteed to not be as efficient as possible: no matter how you check with two knights, there's no way to eliminate any rooms as options if the princess can currently be in all five odd rooms. So if you don't check two adjacent rooms, you'll be back where you started in two turns.)

Turn 2:

the princess can now only be in rooms 3, 5, 7, or 9. You must check the center (or on the next turn, the princess could be in any room, meaning you're back to where you started). Rooms 7 and 3 both being open would also allow her to move anywhere, so we must pick one of them as our other room to cover: let's say it's 3.

Turn 3:

The princess can now only be in 4, 6, or 8. It doesn't matter what we pick here - she'll have the choice of any three rooms on the next night. So let's pick 4 and 6, leaving 8 open.

Turn 4:

Now the princess must have been in 8 the previous night. So she can be in 7, 5, or 9; we must pick 5 and one of the other two. Let's arbitrarily choose 7.

Turn 5:

The princess must have been in 9 the previous night; pick 8 and 6 to find her.

And so:

This is clearly the optimal strategy for dealing with the "princess starts on even" parity. If she started on an odd instead, she is now on an even, so we can repeat the strategy to find her. So the optimal strategy is 10 moves, and one example is:

24; 35; 46; 57; 68; 24; 35; 46; 57; 68

• That was incredibly fast! Only about 15 minutes. Well done. It took me hours to solve this puzzle. In that case I will post a harder version of this puzzle later. – Dmitry Kamenetsky Sep 16 '19 at 2:19