The maths behind the mouse

Why thirteen caves take exactly twelve days, and why the mouse must move.

The puzzle

Thirteen caves lie in a circle. A thief hides in one of them. Every night he moves to a neighbouring cave. Every day two police officers can each search one cave. How many days do they need to be certain they catch him?

It is a well-known brain teaser, usually told as a Google interview question. The game swaps the thief for a mouse and the officers for a cat, and lets you play every board size from three holes up.

Don't chase the mouse. Chase the cloud.

You never know where the mouse is. What you do know is the set of holes it could be in, given everything you have seen. Call that set the cloud. In Ghosts mode the game draws it for you: one ghost per possible hole.

That is the whole game. You win when you shrink the cloud faster than the night regrows it.

Why the mouse must move

If the mouse were allowed to stay put, a hole in the cloud would stay in the cloud, and each night the cloud would grow by its two edges. Two openings a day can never keep up: on a circle the cloud regrows at least as fast as you cut it, and the puzzle is impossible. Forcing the mouse to move is what makes it solvable, because it creates a rhythm.

Number the holes 1 to 13. A mouse in an odd hole tonight is in an even hole tomorrow, and in an odd hole again the day after. If you only ever open holes of the right parity, the mouse keeps dodging you by parity, so the cloud never grows in the direction you are sweeping. This is why on a ring with an even number of holes the cloud splits cleanly in two halves that never mix.

On an odd ring there is a seam: hole 13 is next to hole 1, both odd. A mouse can slip through that seam and change parity. The optimal strategy works the seam: sweep one way, then turn around and sweep back, and the last stragglers have nowhere left to hide.

Minimum days for every board

These numbers come from a brute-force search over all possible clouds, so they are exact. The game's par is this number.

On the circle the pattern is simple: with n holes the minimum is 2 · ⌊(n − 1) / 2⌋, which for an odd ring is n − 1. Thirteen holes, twelve days. Even rings cost the same as the odd ring one smaller, which is why the game only uses odd sizes beyond the tutorial.

One perfect twelve-day run

There are many optimal strategies. This one is easy to remember: the two cats stand one hole apart and leap three holes a day, sweep around, then turn and sweep back.

Watch it with the ghosts on: replay the run. Notice how the cloud never grows behind the cats on the way out, and how the turn at hole 13 closes the seam.

Why a Schrödinger mouse is fair

The puzzle asks for a guarantee: the number of days that works whatever the thief does. A guarantee is a statement about the worst case. The Schrödinger mouse is that worst case made visible: it is in every hole of the cloud at once, and it only commits to a position when you have opened all of them on the same day.

If you catch the Schrödinger mouse in twelve days, the very same sequence of openings catches any real mouse in at most twelve days. A real mouse can only be caught sooner, by luck. The game's first tutorial level has a real mouse for exactly that reason: so you can feel the difference between being lucky and being sure.

Credits

The puzzle is the classic "13 Caves and a Thief". The idea for the game came from the reel "Can You Solve This Google Puzzle?" by @piratecodeofficial. The par table was computed with a small brute-force solver; the source is on GitHub.