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 on 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