Out of Storybook, a side project I’ve been doing for a friend, I had the opportunity to model the problem domain as a constraint satisfaction problem (CSP). It goes:
A set of students are assigned a book a week. Write plan generator to create a set of student-book assignments for that week, given the following constraints:
- All students must receive a book.
- Each book may only be assigned to one student at a time.
- A student may not be assigned a book s/he has received before.
Being that this was a Rails app, I put Amb, a Ruby-based CSP solver, to use. Amb is derived off Jim Weirich’s original source code, implementing a simple backtracking algorithm. (More interesting reading on the original idea behind the
amb operator, proposed in a paper by LISP founder John McCarthy in 1963.)
Not having written any CSP logic since my university days, I tried to come up with a naive solution. It goes something like this:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Well this would work for 2 students and 2 bags, 3 and 3, 4 and 4, but would blow up and overflow the stack when we got to 5 students and 5 bags. Why? I was forcing Ruby to generate the full solution space before starting the CSP search problem:
1 2 3 4 5
Then I was taking that cross product and brute-force generating all possible permutations internal to that:
1 2 3 4 5 6 7
The most obvious thing that stood out to me like a sore thumb was how I wasn’t simply trusting the constraint-based nature of the problem and expressing the problem in terms of the constraints, instead of attempting to imperatively generate the solution. Usage of
Enumerable#permutation resulted in an O(n!) algorithm, which is unacceptable. Back to the drawing board:
1 2 3 4 5 6 7 8 9 10 11 12
Note the main difference here is how I’ve re-tooled the solver to assign variables one at a time (in L5) and check constraints after each assignment. This simplifies the domain of the problem as a graph search and helps us more easily reason about this program.
Follow my csp-solvers project, where I attempt to rewrite this in Prolog and Clojure in an attempt to see how language affects how we reason about problems like these. It’s gonna be fun.
- Artificial Intelligence: A Modern Approach (3rd Edition)
- Ruby Forum – Using Amb
- SchemeWiki: amb