Constraint Satisfaction Problems

Say we have a problem with a bunch of variables, each having its own domain. This domain defines the set of values that the variable is allowed to hold. If the value held by a variable is controlled by other variables, the variable is said to be constrained. This is the idea of a Constraint Satisfaction Problem (CSP), where there exist constraints between the different variables in the problem.

A CSP is said to be solved when every variable of the problem holds a value belonging to its domain such that no constraint between variables is violated. Formally, a constraint satisfaction problem has the following components:

We use the map coloring problem to demonstrate the CSP. In this problem, the color of nodes in a graph (map) are the variables, the set of available colors for each node constitutes its domain. Two connected nodes are not allowed to have the same color. This is the only constraint in this problem.

In our specific problem we have 9 nodes numbered 0 to 8. The domain for all nodes are the colors {red, green and blue}. The color black represents nodes that have not yet been assigned a color. Even though this problem is a simplified case, the algorithm would remain similar for bigger graphs.

Initial Graph — Black nodes are not assigned a color

Algorithm:

1. Try adding color to a node — In the following snippet, we try adding color to a node. If there are no constraint violations, the node color is updated and a recursive call is made starting at the next node. Depending on the return from this recursive call, we decide if we want to try the next color or stick to the assigned color (lines 8–9)

Adding Color

2. Checking if any constraints are violated — Here we need to check if the new color assigned might cause violations with colors that were already assigned in the past. The code snippet below performs color validation.

Checking validity of a color

3. Solve the problem using recursive calls and Backtracking — The code snippet below shows the main algorithm where colors are assigned to nodes recursively. The algorithm continues until a solution is found, if there exists one.

Main solve function (called recursively)

We start executing the solve function starting at the first node, which we assume to be 0 in this article. Program execution ends when all nodes are assigned a color such that there are no violations between nodes of the graph.

Results:

Working of the algorithm is shown in the gif below. Colors are assigned to nodes and this continues until a constraint is violated. When that happens, the algorithm backtracks to a previous assignment and tries assigning the node with a different color.

Assignment of color to nodes: Backtrack when color is invalid for a node

and the final solution (non-unique):

In the case where we use fewer colors than the maximum number of edges at a particular node, a solution does not exist and hence, the algorithm fails. This is shown in the gif below (using only red and green):

In this article, we showed the main idea of a Constraint Satisfaction Problem. We demonstrated the use of backtracking and recursive function calls to iterate over multiple solutions, one of which would solve the full problem. In the next article, I will try to create a sudoku solver, which will be based entirely on the same principle. So, stay tuned!

Code for this article (C++, Python) is available here. If there are suggestions with this article, feel free to contact me or comment on the article.