Shadows: Spooktober in Answer Set Programming

It is Halloween and Huey, Dewey, and Louie want to scare Donald Duck. So they want to make a simple wireframe object, which will cast skeleton shadows. Their first attempt was a 2x2x2 cube but one shadow had also loops like the object itself was a single loop:

So they asked Gyro Gearloose in helping them designing the object. So he put on his thinking cap and after a lot of hammering, he came back and told them, that he even found a 3x3x3 cube solution which is in fact symmetric. What solution did he find?

The problem can be solved via answer set programming (ASP). ASP can be viewed as an extension of Prolog. Pure Prolog rules are based on definite clauses, that is Horn clauses which have exactly one positive literal, namely of the following form:

/* definite clause */
A :- B1, ..., Bn

ASP now allows two new forms of rules. Rules can have disjunctive heads or no head at all. Disjunctive heads result non-determinism while building models, no heads act as constraints while building models:

/* disjunctive clause */
A1, .., Am :- B1, ..,, Bn
/* constraint clause */
:- B1, .., Bn

Our library(minimal/asp) implements ASP via a variant of DPLL that is based on safe forward chaining. We have recently added a min_choose/2 head construct which helps generating models with a cardinality constraint.

To generate loops we simple use Euler circle property, that every vertex has an odd number of edges. When we fix the number of edges to exactly two we get non-self crossing loops:

(min_choose(2,[edge(XL, Y, Z, X, Y, Z), edge(X, YD, Z, X, Y, Z), 
               edge(X, Y, ZB, X, Y, Z), edge(X, Y, Z, XR, Y, Z), 
               edge(X, Y, Z, X, YU, Z), edge(X, Y, Z, X, Y, ZF)]),
min_choose(4,[notedge(XL, Y, Z, X, Y, Z), notedge(X, YD, Z, X, Y, Z), 
              notedge(X, Y, ZB, X, Y, Z), notedge(X, Y, Z, XR, Y, Z), 
              notedge(X, Y, Z, X, YU, Z), notedge(X, Y, Z, X, Y, ZF)])) ;
min_choose(6,[notedge(XL, Y, Z, X, Y, Z), notedge(X, YD, Z, X, Y, Z), 
              notedge(X, Y, ZB, X, Y, Z), notedge(X, Y, Z, XR, Y, Z), 
              notedge(X, Y, Z, X, YU, Z), notedge(X, Y, Z, X, Y, ZF)])
                <=
   between(0, 2, Z), /* depth size */
   ZB is Z-1, ZF is Z+1,
   between(0, 2, Y), /* vertical size */
   YD is Y-1, YU is Y+1,
   between(0, 2, X), /* horizontal size */
   XL is X-1, XR is X+1,
   posted(init).

The code also contains border and consistency constraints. And there is a constraint for symmetry. A link to the full code is given at the end of this post. If we only use the trigger "init", we get degenerate solutions.

So there is a second trigger "check". This trigger uses forward chaining rules that compute a transitive closure in the ASP facts path/6. We can then check that the solution is non-empty and connected.

fail <= \+ edge(_, _, _, _, _, _), posted(check).
fail <= once(edge(P, Q, R, _, _, _)),
   edge(X, Y, Z, _, _, _),
   \+ path(P, Q, R, X, Y, Z), posted(check).

The 3 shadows are computed by by forward chaining rules as well. And there is a variant transitive closure. The 3 shadows are then constantly monitored for not containing a loop:

fail <= posted(proj(K, P, Q, R, S)), 
   posted(walk(K, P, Q, R, S, P, Q, R, S)).

In total we get 8 solutions, which upon inspection are all rotations or mirroring of the same solution. Computing the solutions doesn't take that much time, since due to the symmetry the search space is not that big:

We used a little Prolog predicate plot/3 to generate plot data. This plot data can then be fed into MATLAB to visualize the result. The visualization is not optimal but allows a rough check, here is the 3rd solution:

The example problem is taken from the puzzle collection by the mathematician Peter Winkler. The Jekejeke Prolog solution is a preview, we will soon publish the upcoming release 1.4.1 that provides the new min_choose/2 head construct.
Open Source: Prolog Text "spook"
http://gist.github.com/jburse/7bd69fdc5ab62fca897e365b74017f4d#file-spook-p
P. Winkler (2007): Mathematical Mind-Benders
http://www.crcpress.com/Mathematical-Mind-Benders/Winkler/p/book/9781568813363