Akbar Simple Ruby Constraint Satisfaction Problem Library August 13th, 2007
Constraint Satisfaction Problem (CSP) is a interesting topic. This was my thesis topic. CSP is something like this. Let’s say you have three variables, a, b, and c. Variable a has domain from 1 to 10 (integer). That means you can only give one of these values (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) to variable a. Variable b has domain from 5 to 15 (integer). Variable c has domain from 9 to 12 (integer). Domain is something like valid values for its variable. Then you have constraint. Let’s say we have two constraint. The first is a > c. The second is b is same as c. So we need to find the solution which need to satisfy these two constraints. Solution is described as process to give values to these three variables in one time. Giving a 2, b 7, and c 11 value is one of solution. But this is not a valid solution because it does not satisfy the first constraint. The a value (2) is lower than c value (11). The valid solution is giving a 10, b, 9, and c 9.
But how we do find the valid solution (or just call it solution to make it simple)? By searching. The most primitive solution is called Generate and Test. We start with the first value from “a” domain, that is 1. Then we go to the first value of b domain, that is 5. Then we go to the first value of c domain, that is 9. We have first solution candidate. Test this solution candidate with our constraint. This solution candidate does not satisfy constraint “a > c” because c is bigger than a. Then we go to the next value from c domain, that is 10. Test it again. If the solution candidate can not satisfy all constraints then go to the next value from c domain. If we have tried all value from c domain, we choose next value from b domain. Then we start again from the first value of c domain. Basically we try all combination of a, b, and c value. Another name for this approach is brute force attack.
We make it smarter. Born backtracking. The algorithm is like this. Previously we check values from a, b, to c. Now to make my point, we check values from a, c, to b. I am making my point here. Give value 1 to “a”. After these labeling, we check if this temporary labeling satisfy the constraint. Because there is no unary constraint for variable “a”, then move on. Unary constraint is something like this: a > 4, b <= 4. We can say it as constraint for one variable only. Then we give value 9 to c. After this labeling, we check again whether the temporary labeling (a = 1, c = 9, b = ?) satisfy all the constraints. It doesn’t. Then we backtrack. We does not check the values from b domain for this combination (a = 1, c = 9). We give another value to c (a = 1, c = 10). We check again. And so on. So this is the main difference between backtracking with generate and test. Generate and test gives values to all variables before checking the labeling with constraint. But backtracking check the labeling with constraint every time new value is given to the variable. So when the temporary labeling does not satisfy the constraints, we don’t need to check the other variables. Backtracking is smarter than generate and test.
The example of CSP is 8 queens problem. We can model the 8 queens problem to CSP like this. We have 8 variables, that is 8 rows. Every row can have value from 1 to 8. Or we can say every row have 8 columns. Placing queen to a column in a row means giving a value. So when we place queen in third column in first row it means we give value 3 to variable 1. Every row has domain values from 1 to 8. How about the constraints? Every two queens should not be in the same column. So our constraints are variable 1 != variable 2, variable 1 != variable 3, and so on. != is “not same as”. Every two queens should not be in a diagonal line. So our additional constraints are “variable 1” + 1 != “variable 2”, “variable 1” – 1 != “variable 2”, “variable 1” + 2 != “variable 3”, “variable 1” – 2 != “variable 3”, and so on.
We can find the solutions (yes, there are many solutions) with backtracking. I have wrote the simple demo program using the simple ruby CSP library. To download the simple ruby CSP library, download here. The simple demo program using that library can be downloaded here. 4 queens? Yes, to make the program short, I make it 4 queens rather than 8 queens. This is demo program to show the CSP concept. You can make the 8queen.rb based on this program. Extend it is very easy. Put 4queen.rb and csp.rb in same directory first before you run 4queen.rb. This is the output if you run 4queen.rb.3 => 1 1 => 2 4 => 3 2 => 4 2 => 1 4 => 2 1 => 3 3 => 4
There are two solutions for this 4 queens problem. Basically, it goes like this. “row” => “column”. So 3 => 1 means place queen in first column of third row. Okay, it is easy to understand, huh?!!!
The CSP topic is very broad. You can not explain CSP in a single blog post. There is a thing called optimization. My simple library support that thing. It means you need to find the most optimal solution from all the valid solutions (the optimal measure is defined by you). The valid solutions is not enough. At least you need to find the solutions that pass the optimal measure. But you think, why not just find all the solutions then pick one that most optimal or pass the optimal measure? Yes, that is one of the way. But it is not fast enough. We need to make it faster. My library use branch and bound technique to support optimization feature. The other way which is not supported by my library is genetic algorithm.
There are other things from CSP topic that can not be described in single blog post. Forward checking, node consistency, arc consistency, etc. Also you can put statistic thing in searching method to make it more heuristic.
So make sure you check out these things:
http://kti.mff.cuni.cz/~bartak/constraints/
http://cswww.essex.ac.uk/Research/CSP/edward/FCS.html
There is a programming language which has CSP support. Try to check Mozart.