# An interesting puzzle from MathsJam

## MathsJam?

MathsJam is a monthly getting-together of people who like talking about maths in a pub.

It happens on the second-last Tuesday of each month.

The Newcastle one takes place at the Charles Grey, near the Monument.

## There are loads of them!

View MathsJams current and potential in a larger map

## The princess-in-a-castle puzzle

The setup goes like this:
• There is a castle with 17 rooms in it, arranged in a line.
• The princess who lives in the castle sleeps in a different room each night, but always one adjacent to the one she slept in the previous night. She is free pick any room to sleep in on the first night.
• A prince would like to find the princess, but she will not tell him where she is going to sleep each night.
• The prince can look in a single room each night, with no other restrictions

## The princess-in-a-castle puzzle

And the puzzle is:

Is there a strategy the prince can follow to guarantee he looks in the room the princess is sleeping in within a certain (finite) number of days?

## Step 2

### Make the problem interactive

Use pen and paper and then, if you're me, make a simulation of the puzzle on the computer.

## The game, formally

Let $G$ be the graph corresponding to the layout of the castle. Give every vertex a unique label.

The prince's strategy is a sequence $V_1, V_2, \dots$ of labels of vertices: on night $i$, the prince looks in the room with label $V_i$.

A room is occupiable on a particular night if there is a sequence of rooms the princess can choose which puts her in that room on that night, and differs from the prince's strategy every previous night.

Mark occupiable rooms with a $Y$ and non-occupiable rooms with an $N$.

1. On the first night, mark all rooms with $Y$; let $i:=1$, then repeat the following:
2. Mark room $V_i$ with $N$.
3. For each vertex in $G$, mark it with a $Y$ if there is an adjacent vertex marked $Y$ in the previous night's state; otherwise $N$.
4. If all vertices are marked $N$, done. Otherwise, let $i:=i+1$ and return to Step 2.

## Observations

• Any winning strategy prepended with arbitrarily many moves will still be a winning strategy.
• If there exists a pair of moves $(V_i,V_j), i \lt j,$ such that the state of the graph on night $i$ is the same as that on night $j$, then moves $V_{i+1}, \dots, V_j$ are redundant.

## An algorithm to find which room to pick

1. Mark all rooms with $Y$.
2. For each vertex $V$ marked $Y$ in the current state, compute the state the graph would be in after looking in $V$.
• If that state has been seen before, ignore and return null.
• If not, remember the new state and repeat Step 2 on the new state.
3. Of the rooms looked at in Step 2 which didn't return null, return the one with the shortest strategy.

## An optimisation

An automorphism, or symmetry, of a graph $G=(V,E)$ is a permutation of the graph $\sigma$ such that there is an edge $(u,v)$ in $\sigma G$ if and only if there is also an edge $(\sigma u , \sigma v)$.

$\displaystyle{\xrightarrow{\sigma=(2 3)(4 6)(5 7)}}$

So we can consider states of the graph up to symmetry, greatly reducing the running time of the algorithm.

## Which graphs are solvable?

• Any graph containing a cycle is not solvable. (only trees are solvable)
• This tree is unsolvable:
Any graph containing that tree is unsolvable.
• Every other tree is solvable.

# Thanks!

Longer blog post about the puzzle at http://checkmyworking.com/2011/12/solving-the-princess-on-a-graph-puzzle/.

/

#