Solving Pipes Puzzles with Constraint Propagation | Minimally Sufficient

One of my guilty timewasters is playing pipe puzzles on my phone. The<br>rules are fairly simple: you get a grid of pipes and you need to<br>rotate them such that all of the pipes connect with no broken<br>connections and no cycles. I vibecoded a JavaScript implementation to<br>embed here so you can play around to understand the mechanics. If you<br>want to play for real go to puzzle-pipes.com.

Solving these individually is certainly a waste of my time. A<br>marginally better use of my time is writing a solver. At least this<br>way I might learn something.

Solving Pipes Puzzles#

Depth First Search#

One approach we could take is to just check every possible<br>configuration to see whether it&rsquo;s a solution. This is clearly a<br>terrible idea (an n×n grid has up to \(4^{n^2}\) configurations) but let&rsquo;s<br>run with it conceptually. The biggest issue is to figure out how to<br>generate all of these configurations efficiently. Enter depth first<br>search (with this stylized Julia code).

function dfs_solve(initial_state)<br>stack = [initial_state]<br>while !isempty(stack)<br>state = pop!(stack)

is_solved(state) && return state

branch_pt = next_branch_point(state)

for next_states in make_branch(state, branch_pt)<br>push!(stack, next_states)<br>end<br>end<br>end

Our initial state is all possible assignments for each pipe. Our<br>branching points will be selecting a definite assignment for each<br>pipe. If it turns out we were correct on all assignments we&rsquo;re done;<br>otherwise we continue iterating through the search.

Short-Circuiting#

We can obviously make this more efficient. Notably, we can start<br>short-circuiting our search when we know the remaining solution is<br>infeasible. If we&rsquo;ve set up our pipes in such a way that we already<br>have a cycle or two incompatible pipes are connected then there&rsquo;s no<br>point in further examining states from that tree. Thus we can augment<br>our search with one further line.

function dfs_solve_with_stopping(initial_state)<br>stack = [initial_state]<br>while !isempty(stack)<br>state = pop!(stack)

!is_valid_state(state) && continue # added to stop early<br>is_solved(state) && return state

branch_pt = next_branch_point(state)

for next_states in make_branch(state, branch_pt)<br>push!(stack, next_states)<br>end<br>end<br>end

Constraint Propagation#

This is getting much better but it&rsquo;s still fairly inefficient. I might<br>introduce an inevitable contradiction towards the start of my search but we won&rsquo;t know it<br>until the very end. It would be nice if we could catch it earlier: we<br>can do this via constraint propagation and just never generate these<br>assignments in the first place.

function dfs_with_constraint_propagation(initial_state)<br>stack = [initial_state]

while !isempty(stack)<br>(states, queue) = pop!(stack)

propagate_constraints!(states, queue) # added to remove impossible next states

!is_valid_state(states) && continue<br>issolved(states) && return states

branch_pt = next_branch_point(states)

for next_states in make_branch(states, branch_pt)<br>push!(stack, (next_states, [branch_pt]))<br>end<br>end<br>end

function propagate_constraints!(states, queue)<br>while !isempty(queue)<br>idx = pop!(queue)

possible_states = states[idx]

for (neighbor_idx, dir) in neighbors(idx, states)<br>existing = states[neighbor_idx]<br>allowed = possible_neighboring_states(possible_states, dir)<br>new_set = intersect(existing, allowed)

if length(new_set) length(existing)<br>states[neighbor_idx] = new_set<br>push!(queue, neighbor_idx)<br>end<br>end<br>end<br>end

This starts with an initial queue of states to consider: let&rsquo;s just<br>use the pipe whose state we just branched on. It then takes that state<br>and looks at all the neighbors. For each neighbor, it calculates which<br>neighbor states are consistent with the current state and only keeps<br>those. If we removed any states in this process then we&rsquo;ve<br>successfully propagated a constraint; but now we might have follow-on<br>effects! So we add that neighbor to the queue and see if we can<br>propagate any further constraints. We keep doing this until we run out<br>of the chain.

Going faster with mutable state#

This already gets us a reasonably fast solver. However it&rsquo;s not going<br>to be the fastest; in particular we have a lot of memory allocation<br>going on here due to making passing around a lot of copies of our<br>states as next_state. It would be nicer if we just manipulated a<br>single mutable state data structure

This only works, however, if there&rsquo;s an easy way to backtrack and undo<br>certain transformations. Fortunately this is relatively easy for us:<br>we can maintain an undo log which stores the state changes so undoing<br>an operation is simply assigning the old value to a field. So if we<br>found out we had a contradiction we iterate back through our<br>propagated constraints restoring the old sets.

But interestingly the constraint propagation is the easy part: it&rsquo;s<br>is_valid_state that benefits the most from this mutability.

Incrementally Detecting Invalid...