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:

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 next-empty
  ([puzzle ij]
    (next-empty 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 (next-empty puzzle ij)]
    (for [mask (shuffle (keys (:tiles puzzle)))
          :when (valid-move? puzzle ij mask)]
      [(set-cell 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

(solve-examples solve trace-diagram 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 well-constrained 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 15-16). 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    5-10us

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

blog comments powered by