A small CSP Solver written in JavaScript (circa 2013) as an exploration in Constraint Programming
After spending several days surveying Constraint Programming in general I began to write this little framework. I chose JavaScript almost tongue in cheek as I had previously only encountered Constraint Programming in lower-level or compiled languages. One of my constraints was browser compatibility for presentation purposes.
Constraints are simple predicate functions.
The CSP began as a simple adjacency list of arrays, which represented the domain of the variables. A very simple checking algorithm allowed me to reduce from the domain of the variables those values which were known to be in conflict. I used a first-solution-halting backtrack flavored tree search, initially using a vanilla AC1 algorithm. This turn d into the pseudo-AC3 algorithm. The gains prompted me to research CSP in more detail.
Days turned to into weeks as I began pouring over research in Constraint Programming and optimization.
The Constraint Graph is represented as a (sometimes) directed acyclic hypergraph.
I leverage a Bipartite Graph to incorporate the Max-Flow Min-Cut theorem, and implement a Global ALLDIFF constraint. This allows me to constrain many variables without decomposing that constraint into several weaker constraints. Using a single constraint during the tree-search helps to prune the search space.
The code itself is not optimized, but written in an intuitive object-oriented style.
The Zebra Puzzle is a toy logic puzzle used for fun and to test AI algorithms.
This particular family-friendly incarnation was derived from the writings of Russel and Norvig, Artificial Intelligence: A Modern Approach.
Given a set of variables (people, pets, drinks, etc…), a block of houses, and a set of constraints on who or what may reside in which house, the point of the puzzle is to determine a valid assignment which satisfies all of the given constraints. A typical objective is to state which person owns the zebra, hence the name of the puzzle.
- The Englishman lives in the red house.
- The Spaniard owns the dog.
- The Norwegian lives in the first house on the left.
- The green house is immediately to the right of the ivory house.
- The man who eats Hershey bars lives in the house next to the man with the fox.
- Kit Kats are eaten in the yellow house.
- The Norwegian lives next to the blue house.
- The Smarties eater owns snails.
- The Snickers eater drinks orange juice.
- The Ukrainian drinks tea.
- The Japanese eats Milky Ways.
- Kit Kats are eaten in a house next to the house where the horse is kept.
- Coffee is drunk in the green house.
- Milk is drunk in the middle house.
| House | 1 | 2 | 3 | 4 | 5 |
| Color | yellow | blue | red | ivory | green |
| Nationality | Norwegian | Ukrainian | Englishman | Spaniard | Japanese |
| Drinks | water | tea | milk | OJ | coffee |
| Pet | fox | horse | snail | dog | zebra |
| Eats | kit-kat | hershey | smarties | snickers | milkey-way |
| Method | i7-2920XM | Ryzen 7 5700G |
|---|---|---|
| Naive Solution | 22 seconds | 17 seconds |
| Optimized | 235 ms | 36ms |
npm install
node zebra.js
Dependencies
- NodeJS
- Underscore.js
Special thanks to Willem-Jan van Hoeve and Irit Katriel at Carnegie Mellon for their enlightening research on meta-problem analysis of global constraints.
Van Hoeve, W.-J., & Katriel, I. (2006). Global Constraints. In Handbook of Constraint Programming (pp. 169-203). ISBN 9780080463803. Retrieved from [https://www.andrew.cmu.edu/user/vanhoeve/papers/chapter.pdf]
Russell, S. J. 1., Norvig, P., & Davis, E. (2010). Artificial intelligence: a modern approach. 3rd ed. Upper Saddle River, NJ, Prentice Hall.
The solver and puzzle are MIT licensed