# Let's solve zebra and implement conflict-directed backjumping (AIMA ch. 6).

• Jul 8, 2013 · 6:00 PM

The zebra problem kicked our ass: we debated whether the domain-as-tuple vs. many-variable approach was better; let's implement one of them.

It's also disappointing that constraint-satisfaction is a glorified depth-first search; we can complicate our lives a little bit, it turns out, by implementing a more "intelligent" form a backtracking, viz. conflict-directed backjumping, which selectively backtracks assignments that are relevant to the apparent contradiction.

Chronological backtracking is what you get if you rely on the mechanics of the call-stack to do your backtracking; it turns out, though, that chronological backtracking may result in extra work.

• ##### Ryan H.

Sorry guys, I'm not going to be able to make it out tonight. Life and responsibilities and all that. However I did learn quite a lot and I'm hoping to be at the next meet.

If you are still discussing standard CSP, here's my contribution to the discussion. I reformulated my Zebra problem such that there are 25 variables - what we were previously calling "values". (e.g., fox, milk, tea, red). This reduces the size of the problem from the previously suggested 125, and also introduces a shared domain into the problem. That domain is simply:

{1, 2, 3, 4, 5}

By reconsidering the constraints, I was able to represent the problem with 3 naive, simple relational constraints. Moreover I consider this to be verbose - I could have used only two, but preferred the aesthetic of an imposed artificial distinction.

Note that the higher level constraints we discussed before are not needed if proper forward checking is used, as the relevant nodes will be preemptively pruned.

... (continued)

July 8, 2013

• ##### Ryan H.

I've been reworking it so that I'm dealing with it from a graph-theoretic point of view. There are three graphs: the arc representation, the constraint-to-constraint­ representations (not needed yet) and the bipartite variable->value graph. You can also consider this a hypergraph of sub-graphs.

In order to *efficiently* handle the Alldiff, we have to rewrite the graph at every step to get the bipartite value-graph. Then we deal with it on a meta-level, we never actually compare the values. By setting a value and finding an augmenting path, you can establish a matching. (A perfect matching is a solution)

July 11, 2013

• ##### Ryan H.

I know there are tricks, such as stitching together matchings, and automatically inferring from a k-regular graph, but I'm still working on the algorithm for this, and I don't know if it will extend to any other sort of global constraint. All I know is I'm not satisfied with the alternatives. (Implied constraints, hidden variables for reformulating n-ary to binary).

If I can make it in on Sunday, I could use your help with the hypergraph as I'm fairly new to graph theory in general.

July 11, 2013

• ##### Peter D.

Thanks, you guys, for staying late last night; it was nice to walk away from a meetup with working code that sprang from non-working code.

There were some fun conceptual things to work through converting zebra to a binary problem; not to mention thinking about xor on low blood-sugar.

July 9, 2013

• ##### David M.

I found a useful discussion of the problem at http://csweb.ucc.ie/~dongen/ZEBRA.pdf (the problem is the same, only some values have been changed). It looks to me like the same approach that Ryan settled on.

1 · July 8, 2013

• ##### Peter D.

Thanks for finding this, by the way, David; it and Ray's help (also Ethan's and Martin's) led to the breakthrough that an extra variable to store the address was superfluous.

1 · July 9, 2013

• ##### David M.

Congratulations on solving the problem. When I left I was thinking that even after a working syntax had been found to specify the constraints, that would only get you as far as arc consistency. Looking at the code now, I'm not clear on where "backtracking-search" is defined. Is that a function that Scheme provides? (nvm - I see it's in https://github.com/klutometis/aima/blob/master/backtracking.scm Is that code also in aima-csp-core.scm?).

Did the Norwegian own the zebra?

July 9, 2013

• ##### Peter D.

Here's backtracking-search: https://github.com/klu...;­ it's really just a special case of backtracking-enumerate, though, with n = 1: https://github.com/klu...­.

Backtracking-enumerate is a translation of the backtracking-search on page 215; except that, instead of stopping at the first solution, it gathers up to n of them.

July 9, 2013

• ##### Ryan H.

I just had a flash of inspiration on the Zebra/Einstein problem. If I'm correct in this, all of us were wrong on Monday. Both proposed formulations were fundamentally incorrect, and a slight variation to the accepted scheme-based algorithm for map coloring would be in order.

Here's a hint: The structure of the two problems should not differ. The given specification for the map coloring problem is redundant by half. Our constraints should be very stupid, but we learn something valuable from them before we even start.

If I'm wrong I'm going to look like a bumbling idiot who speaks in riddles!

July 3, 2013

### 7 went

• ##### Tony A.
• A former member

### Mountain View, CA

Founded May 23, 2012