Artificial intelligence is one of my favorite subjects because it combines mathematics with algorithms to solve problems that are difficult even for computers to solve. One classification of these problems is constraint satisfaction problems (CSP). Formally, a CSP consists of a set of variables \( X = \{ x_1, x_2, \ldots, x_n \} \) , a set of domains \( D = \left\{ D_{x_i} : x_i \in V \right\} \) (each domain corresponds to a variable), and a set of constraints or restrictions \( C \) on the values of each variable. The goal of such problems is to find a suitable assignment for each variable from that variable’s domain such that all constraints are satisfied.
Sudoku is a classic example of a CSP: The variables are the cells of the 9×9 grid, the domain for each variable is the digits 1–9, and the constraints are as follows:
- No two cells in the same row may have the same value
- No two cells in the same column may have the same value
- No two cells in the same 3×3 sub-grid may have the same value
In order to guarantee a unique solution to a particular Sudoku CSP, at least 17 variables/cells must be assigned a value.
Naïvely, one might write a quick program to pick a random variable, assign it a value from its domain, check all constraints, and recursively continue solving the rest of the puzzle. If at any point a constraint is violated, the program backs up and tries the next value. If all possible assignments have been tried, then the problem is unsatisfiable. This algorithm is called backtracking, and it is notoriously slow and inefficient by itself. Solving a Sudoku problem with backtracking could take up to \( 9^{9^2-17} \approx 1.17901846 \times 10^{61} \) random assignments!
Most of the algorithms in the artificial intelligence field get their brilliance from a simple change or improvement in the algorithm: for example, the A* pathfinding algorithm is identical to the less efficient BFS and DFS algorithms save for one important difference. Each algorithm keeps a work-list containing the nodes that have yet to be searched, but the data structure of this work-list varies across these algorithms: DFS uses a LIFO stack, BFS uses a regular FIFO queue, and A* uses a priority queue ordered by a heuristic function.
One such “trick” to solving CSPs is constraint propagation, which eliminates inconsistent values from the domains of each variable. This in turn causes backtracking to terminate earlier than it would otherwise. Arc consistency, or local consistency, is a well-known constraint propagation method, but it requires that the constraints be expressed in binary form (i.e. each constraint can refer to only two variables). There are ways to convert any CSP problem to a “normalized binary CSP”. I have notes from my undergraduate AI course on this subject, so I won’t repeat them here.
As a fun project related to this topic, I have written a CSP-solver library in Ruby that uses Arc-Consistency with Backtracking and the minimum remaining values (MRV) heuristic to solve complex constraint satisfaction problems with relative efficiency. If there are multiple solutions, it will return the first solution it finds. If a solution exists, the library is guaranteed to find it, and if no solution exists, it is guaranteed to return false. Usage details are available on my main site.