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:
If \tau(x_i) = 0, move the bunny on u_i to v_i.
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.
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 :)
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!
