Solving Sudoku … Think Constraint Satisfaction Problem

Important Components of Constraint Satisfaction Problem (CSP)

Here are the components of a CSP

Let us use Sudoku and identify these components

Every empty cell is a variable. Each variable can take one of 1 to 9 numbers each. This is the domain for the variable. One possible combination of values is called a “world”. So there are (d^n) worlds. d is the size of the domain and n is the number of variables. Every variable has to satisfy some constraints. In case of Sudoku, there are three such constraints. Finally, a model is a world which meets all the constraints. Below I will tie all of it.

Solving Sudoku is just searching the model(s) in all the possible worlds

If one aspect which is ubiquitously present in all AI algorithm is “Search”. Some algorithms are naïve, and some are very smart. There are various combinatorial optimization algorithms, “Constraint Satisfaction Problem(CSP),” “ Satisfiablility Problem(SAT),” “Constraint Programming(CP),” “Satisfiability Modulo Theories(SMT)”. In this blog, I will look at CSP using Sudoku.

Let us start with the easiest of all — “Generate & Test”

This is the brute force option. In this, you generate all the worlds and check every world if it is a model.

This may not be effective given the number of worlds (9⁵³) that needs to be searched.

Let us reduce the Search Space — CSP as Search

Following are the important components of a search

CSP Search using Backtracking

The main algorithm used for search is Backtracking. The search space is explored using Depth First Search(DFS) by sequential instantiation of variables by getting the values from the domain in a specific order. At each assignment, a check is made if all the variables for a constraint are bound. As soon as all the variables are bound for the constraint, it is evaluated. If the constraint fails the tree is pruned. This Pruning reduces the search space.

Improve Backtracking — Select variables smartly

Instead of selecting the variables in a sequential order. Apply heuristics to speed up the search space or in other words “fail quickly, fail often” to reveal the solution.

When it comes to Sudoku only “Minimum Remaining Values” make sense. By choosing squares with less number of values, there is less branching. For every algorithm, there are improvements by applying heuristics specific to the problem.

Using Constraint Propagation to solve CSP

Till now we have focused on the variables, now let us focus on the values. It is an obvious fact that if I am able to reduce the values, my search space would be reduced. This is the key idea behind all consistency algorithms.

When one a variable say Y’s constraint depends on X. When variable X is changed or assigned then variable Y needs to be recomputed. This, in turn, will recompute all the variables whose constraint depends on Y. This process will keep going recursively till there are no more changes. This is called constrain propagation.

Every time a variable is recomputed the domain for the variable is reduced. A reduced domain means less search. In some case this reduction mean if the solution is found in few seconds or in years.

Constraint Propagation & Types of Consistencies

A variable is recomputed to check if it maintains consistency. There are different types of consistencies.

Best strategy is use constrain propagation using different types of consistencies and then if needed perform search on a reduced set of domain values.