Pipes, Clojure and Choco (part 2: Direct Search)
This is the second in a series of posts that explore constraint programming. It’s always more fun to learn with a good example, so we’re writing a solution for this problem.
The routines I will show rely on a fair number of unexciting support routines
in puzzle.clj. These support reading and writing puzzles, as well as
testing for valid moves, etc. They are based around an immutable Puzzle
record:
(defrecord Puzzle [n tiles cells])
where:

n
is the size of one side of the (square) puzzle; 
tiles
is a mapping from mask values to the number of (free) tiles available; 
cells
is a mapping from[i j]
coordinates to a mask value (or nill, if the cell is empty).
So a complete puzzle will have an empty tiles
and a full (n * n
values)
cells
map.
This uses “mask values” which are simple binary descriptions of the tiles. The zeroth bit of the mask indicates whether there is a pipe entering from the top; the next bit from the right; etc.
I use maps rather than 2D arrays because they are immutable in Clojure. This
avoids any risk of corrupted state when backtracking and is still moderateely
efficient (creating a new Puzzle
typically involves adding one value to the
tree behind cells
and removing one value from the tree behind tiles
).
Given all that, the search code is fairly simple. The state for
a node consists of a Puzzle
and the [i j]
location of the last cell
modified (which rasters across the puzzle as we deepen the search). And
search consists of (1) finding the next empty cell and (2) listing all
possible tiles (given the constraints from edges and neigbours):
(defn nextempty
([puzzle ij]
(nextempty puzzle ij (dec (:n puzzle)) (:cells puzzle)))
([puzzle [i j] m cells]
(cond
(nil? (cells [i j])) [i j]
(< i m) (recur puzzle [(inc i) j] m cells)
(< j m) (recur puzzle [0 (inc j)] m cells)
:else nil)))
(defn expand [[puzzle ij]]
(let [ij (nextempty puzzle ij)]
(for [mask (shuffle (keys (:tiles puzzle)))
:when (validmove? puzzle ij mask)]
[(setcell puzzle ij mask) ij])))
(defn solve [puzzle trace]
(letfn [(solution? [[puzzle ij]]
(complete? puzzle))]
(dfs [puzzle [0 0]] solution? expand (atom 0) trace)))
So, how well does it perform? Again, I’m going to gloss over the support routines and focus on the resuts. The command
(solveexamples solve tracediagram extract)
runs the search on the test data and prints some sweet diagrams as it goes:
1 2 3 4 5 6 7 8 9 10
▒═▒▒▒ ╔═▒▒▒ ╔══▒▒ ╔══╗▒ ╔═╗▒▒ ╔═╗╔▒ ╔═╗╔╗ ╔═╗╔╗ ╔═╗╔╗ ╔═╗╔╗
▒═▒▒▒ ▒═▒▒▒ ▒═▒▒▒ ▒═▒▒▒ ▒═▒▒▒ ▒═▒▒▒ ▒═▒▒▒ ╠═▒▒▒ ╠═╣▒▒ ╠═╣║▒
▒╔▒╬▒ ▒╔▒╬▒ ▒╔▒╬▒ ▒╔▒╬▒ ▒╔▒╬▒ ▒╔▒╬▒ ▒╔▒╬▒ ▒╔▒╬▒ ▒╔▒╬▒ ▒╔▒╬▒
▒▒▒▒╗ ▒▒▒▒╗ ▒▒▒▒╗ ▒▒▒▒╗ ▒▒▒▒╗ ▒▒▒▒╗ ▒▒▒▒╗ ▒▒▒▒╗ ▒▒▒▒╗ ▒▒▒▒╗
╚▒▒▒▒ ╚▒▒▒▒ ╚▒▒▒▒ ╚▒▒▒▒ ╚▒▒▒▒ ╚▒▒▒▒ ╚▒▒▒▒ ╚▒▒▒▒ ╚▒▒▒▒ ╚▒▒▒▒
11 12 13 14 15 16 17 18 19 20
╔═╗╔╗ ╔═╗╔╗ ╔═╗╔╗ ╔═╗╔╗ ╔═╗╔╗ ╔═╗╔╗ ╔═╗╔╗ ╔═╗╔╗ ╔═╗╔╗ ╔═╗╔╗
╠═╣║║ ╠═╣║║ ╠═╣║║ ╠═╣║║ ╠═╣║║ ╠═╣║║ ╠═╣║║ ╠═╣║║ ╠═╣║║ ╠═╣║║
▒╔▒╬▒ ║╔▒╬▒ ║╔╬╬▒ ║╔╬╬╝ ║╔╬╬╝ ║╔╬╬╝ ║╔╬╬╝ ║╔╬╬╝ ║╔╬╬╝ ║╔╬╬╝
▒▒▒▒╗ ▒▒▒▒╗ ▒▒▒▒╗ ▒▒▒▒╗ ║▒▒▒╗ ║╚▒▒╗ ║╚╝▒╗ ║╚╝╚╗ ║╚╝╚╗ ║║▒▒╗
╚▒▒▒▒ ╚▒▒▒▒ ╚▒▒▒▒ ╚▒▒▒▒ ╚▒▒▒▒ ╚▒▒▒▒ ╚▒▒▒▒ ╚▒▒▒▒ ╚═▒▒▒ ╚▒▒▒▒
21 22 23 24 25 26
╔═╗╔╗ ╔═╗╔╗ ╔═╗╔╗ ╔═╗╔╗ ╔═╗╔╗ ╔═╗╔╗
╠═╣║║ ╠═╣║║ ╠═╣║║ ╠═╣║║ ╠═╣║║ ╠═╣║║
║╔╬╬╝ ║╔╬╬╝ ║╔╬╬╝ ║╔╬╬╝ ║╔╬╬╝ ║╔╬╬╝
║║║▒╗ ║║║╚╗ ║║║╚╗ ║║║╚╗ ║║║╚╗ ║║║╚╗
╚▒▒▒▒ ╚▒▒▒▒ ╚╝▒▒▒ ╚╝╚▒▒ ╚╝╚═▒ ╚╝╚═╝
1 2 3 ... 374
▒▒▒▒▒▒ ╔▒▒▒▒▒ ╔╗▒▒▒▒ ╔╗╔╗╔╗
▒╠▒▒▒▒ ▒╠▒▒▒▒ ▒╠▒▒▒▒ ║╠╣║║║
▒▒▒▒▒▒ ▒▒▒▒▒▒ ▒▒▒▒▒▒ ║║║║║║
▒▒▒▒▒▒ ▒▒▒▒▒▒ ▒▒▒▒▒▒ ║║║║║║
▒▒▒▒╣▒ ▒▒▒▒╣▒ ▒▒▒▒╣▒ ║║║╠╣║
▒▒▒▒▒▒ ▒▒▒▒▒▒ ▒▒▒▒▒▒ ╚╝╚╝╚╝
The first solution is so wellconstrained that there is almost no backtracking (the biggest regression seems to be between 19 and 20  at 19 there were no suitable pieces; 20 uses the child following 1516). The second solution is a lot more open  if you run the code these diagrams are printed to screen and you can “animate” the search progress by scrolling the console.
Note that the exact depths required will change on each run because I shuffle
the candidate tiles within expand
(to avoid any systematic bias with the
limited number of tests).
Those examples have initial constraints and are fairly small. To see how the search scales I also fitted it to empty puzzles with tiles suitable for concentric circles (squares?):
28207 1439846
╔══════╗ ╔════════╗
║╔════╗║ ║╔══════╗║
║║╔══╗║║ ║║╔════╗║║
║║║╔╗║║║ ║║║╔══╗║║║
║║║╚╝║║║ ║║║║╔╗║║║║
║║╚══╝║║ ║║║║╚╝║║║║
║╚════╝║ ║║║╚══╝║║║
╚══════╝ ║║╚════╝║║
║╚══════╝║
╚════════╝
As expected, these require many more iterations.
And, finally, here are timings (ms per puzzle in ms / average number of iterations):
examples concentric per iteration
5x5 6x6 8x8 10x10 average
direct 0.2ms/40 2ms/300 200ms/30,000 10s/1,000,000 510us
You can see all the code in the repo.
Next time I’ll show how to make the search smarter (and then, in the final article, see how Choco compares against these “hand crafted” solutions).
Andrew
Related Posts
 Pipes, Clojure and Choco (part 3: Smart Search)
 Pipes, Clojure and Choco (part 5: Choco)
 Pipes, Clojure and Choco (part 1: Limits of Laziness)
 Pipes, Clojure and Choco  Optimisation
 An ORM for C?
 Choco and Regular Expressions
 Pipes, Clojure and Choco (part 4: Benchmarking)
 CMake with Check Unit Tests
 How to Average Complex Responses
 Javascript Graphics w/ Raphael