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 be a collection of 3SAT clauses over variables . The reduced instance of BunnyCarrot
corresponding to looks like this:
What we have here is the following in terms of the structure of graph:
a path on vertices, with the left most vertex in and the rightmost one in ;
a pair of vertices for every , and an edge between them, where all the ’s are in ’ — the vertex represents the literal while the vertex represents the literal ;
a pair of vertices and in , with adjacent to all ’s and adjacent to all ’s.
Now here be the instructions associated with the edges:
the edge to the -th vertex on is active only if there is a bunny on at least one of the literals present in the clause ;
the edges between and are active only when there is a bunny on the leftmost vertex of ; and
finally, the edges incident on and are active only when there is a bunny on the rightmost vertex of .
The Forward Direction
We first claim that we can “win” this game if has a satisfying assignment. Indeed, let be a truth assignment that satisfies all the clauses of . Then:
If , move the bunny on to .
Move the bunny on the leftmost vertex of the path to the rightmost vertex: note that all edges are active because is a satisfying assignment.
Move all bunnies on ’s to and those on ’s to .
The Backward Direction
Now suppose there is a winning sequence of moves . We will show that we can extract from this sequence a satisfying assignment for , which will firmly establish the equivalence of the generated instance of BunnyCarrot
with the OG hard instance .
Note that to begin with, all the blue edges are inactive. Now, in the sequence , let us say that a step is key if it involves a bunny moving along the first edge of the path and critical if it involves a bunny moving along the last edge of the path .
Suppose the -th step is the first critical step in . Further, suppose that the -th step is the last key step to occur before the -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 -th step and before the -th step, note that edges incident to and are inactive for all . This implies that every step between the -th and -th steps involves a bunny moving along , and in particular, every edge in is crossed at least once in this phase of the game.
Let us note the positions of the bunnies who are on the ’s and ’s after the -th step is executed. Observe that this naturally translates to an assignment on the variables as follows:
We argue that must in fact be a satisfying assignment.
Assume to the contrary: suppose some clause is, in fact, not satisfied by .
Then, we claim that the edge connecting the -th and -th vertices is not active.
As an example, suppose . Since does not satisfy , it must be the case that:
- — and hence there is a bunny on ;
- — and hence there is a bunny on ;
- — and hence there is a bunny on .
However, the condition for the edge to the -th vertex on to be active is simply that there is a bunny present on at least one of the literals present in the clause , i.e, one of , or . However, because of the structure of the graph, and the fact that all edges incident on and are inactive at all times before the first critical step, observe that:
- If there is a bunny on , there is no bunny on .
- If there is a bunny on , there is no bunny on .
- If there is a bunny on , there is no bunny on .
By our assumption that falsifies , all the premises above are true! So there is an edge on the path that is not active between the -th and -th steps, which violates our understanding that every edge was crossed between these steps. This is a contradiction, and hence 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 . 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!