Dog Bunny Puzzle

Dog Bunny: A Cute Puzzle

Conrad Barski (@lisperati)‘s latest, Dog Bunny Puzzle, had jumped to #1 on HN. The puzzle presents the following somewhat minimalist interface:

If you haven’t played it yet, you might want to go ahead and give it a shot first. Most people figured out the mechanics without any explicit instructions. A couple of things that may not be immediately clear, but typically discovered quickly within a few moves:

• The edges are labeled with conditions, and can be used only if all of the said conditions are met.

• The bunny or dog icons may sometimes cover up what kind of location they are at. You can drag them away to find out!

• Multiple animals can occupy the same spot at a time.

• It is possible to get into a dead end, a situation from where no legal moves are possible. In the verison of the game that is available at the time of this writing, the game offers no sign that you might be in this situation. This may however change.

After winging it on the puzzle, several questions seemed natural:

So the last question may strike you as a bit left-field, but that’s what I’m going to ramble about for the rest of this post :) It turns out that the answer is in the affirmative, and here is a lovely reduction by @lokshtanov showing as much.

The Reduction

Let’s just set up the game as a computational problem just to be sure that we agree on the abstraction. In fact, we’ll be working with a simpler version that we will call BunnyCarrot.

We are going to show that BunnyCarrot is NP-complete by reducing from 3SAT. So let $\phi := \{C_1, \ldots, C_m\}$ be a collection of $m$ 3SAT clauses over variables $\{x_1, \ldots, x_n\}$. The reduced instance of BunnyCarrot corresponding to $\phi$ looks like this:

What we have here is the following in terms of the structure of graph:

• a path $X$ on $m+2$ vertices, with the left most vertex in $B$ and the rightmost one in $C$;

• a pair of vertices $(u_i,v_i)$ for every $i \in [n]$, and an edge between them, where all the $u_i$‘s are in $B$’ — the vertex $u_i$ represents the literal $x_i$ while the vertex $v_i$ represents the literal $\overline{x_i}$;

• a pair of vertices $p$ and $q$ in $C$, with $p$ adjacent to all $u_i$‘s and $q$ adjacent to all $v_i$‘s.

Now here be the instructions associated with the edges:

• the edge to the $\ell$-th vertex on $X$ is active only if there is a bunny on at least one of the literals present in the clause $C_{\ell-1}$;

• the edges between $u_i$ and $v_i$ are active only when there is a bunny on the leftmost vertex of $X$; and

• finally, the edges incident on $p$ and $q$ are active only when there is a bunny on the rightmost vertex of $X$.

The Forward Direction

We first claim that we can “win” this game if $\phi$ has a satisfying assignment. Indeed, let $\tau: \{x_1,\ldots,x_n\} \rightarrow \{0,1\}$ be a truth assignment that satisfies all the clauses of $\phi$. Then:

1. If $\tau(x_i) = 0$, move the bunny on $u_i$ to $v_i$.

2. Move the bunny on the leftmost vertex of the path $X$ to the rightmost vertex: note that all edges are active because $\tau$ is a satisfying assignment.

3. Move all bunnies on $u_i$‘s to $p$ and those on $v_i$‘s to $q$.

The Backward Direction

Now suppose there is a winning sequence of moves $\sigma$. We will show that we can extract from this sequence a satisfying assignment for $\phi$, which will firmly establish the equivalence of the generated instance of BunnyCarrot with the OG hard instance $\phi$.

Note that to begin with, all the blue edges are inactive. Now, in the sequence $\sigma$, let us say that a step is key if it involves a bunny moving along the first edge of the path $X$ and critical if it involves a bunny moving along the last edge of the path $X$.

Suppose the $\ell$-th step is the first critical step in $\sigma$. Further, suppose that the $t$-th step is the last key step to occur before the $\ell$-th step. Notice that there must be at least one key step before a critical step — we must begin before we can end :)

Now, for all steps after the $t$-th step and before the $\ell$-th step, note that edges incident to $u_i$ and $v_i$ are inactive for all $i \in [n]$. This implies that every step between the $t$-th and $\ell$-th steps involves a bunny moving along $X$, and in particular, every edge in $X$ is crossed at least once in this phase of the game.

Let us note the positions of the bunnies who are on the $u_i$‘s and $v_i$‘s after the $t$-th step is executed. Observe that this naturally translates to an assignment on the variables as follows:

$$\begin{equation*} \tau(x_i) = \begin{cases} 1 & \text{if } u_i \in B,\\ 0 & \text{if } v_i \in B. \end{cases} \end{equation*}$$

We argue that $\tau$ must in fact be a satisfying assignment.

Assume to the contrary: suppose some clause $C_k$ is, in fact, not satisfied by $\tau$.

Then, we claim that the edge connecting the $k$-th and $(k+1)$-th vertices is not active.

As an example, suppose $C_k = \{x_1,x_2,\overline{x_3}\}$. Since $\tau$ does not satisfy $C_k$, it must be the case that:

• $\tau(x_1) = 0$ — and hence there is a bunny on $v_1$;
• $\tau(x_2) = 0$ — and hence there is a bunny on $v_2$;
• $\tau(x_3) = 1$ — and hence there is a bunny on $u_3$.

However, the condition for the edge to the $(k+1)$-th vertex on $X$ to be active is simply that there is a bunny present on at least one of the literals present in the clause $C_{k}$, i.e, one of $u_1$, $u_2$ or $v_3$. However, because of the structure of the graph, and the fact that all edges incident on $p$ and $q$ are inactive at all times before the first critical step, observe that:

• If there is a bunny on $v_1$, there is no bunny on $u_1$.
• If there is a bunny on $v_2$, there is no bunny on $u_2$.
• If there is a bunny on $u_3$, there is no bunny on $v_3$.

By our assumption that $\tau$ falsifies $C_k$, all the premises above are true! So there is an edge on the path $X$ that is not active between the $t$-th and $\ell$-th steps, which violates our understanding that every edge was crossed between these steps. This is a contradiction, and hence $\tau$ must indeed be a satisfying assignment.

I’ll just remark here that this construction can be modified so that every vertex in the graph has constant degree, and there is only one vertex in $C$. It can also be modified to change the “or” condition on the edges to an “and”, by simply separating the conditions out along multiedges.

Food for thought

Here are some more questions :)

Important

1. What’s the complexity of this game when the underlying graph has some simple structure (e.g, a tree)?

2. Does the problem get harder if we introduce attacking entities like wolves?

3. Can we come up with an algorithm that runs in polynomial time on instances where there is a valid winning sequence of constant length?

4. Is the problem hard even for a constant number of bunnies?

PS. Here’s a sketch of a slighty different reduction from vertex cover. Thanks again to Daniel for sharing the reduction described here! Comments welcome here, or continue the conversation on Twitter!