Constraint Satisfaction Problems

Table of contents

• Defining CSP with Map Coloring Problem
• Arc consistency
• Sudoku Example of CSP
• Backtracking Search
• Min Conflicts
• Tree CSP

Defining CSP with Map Coloring Problem

A map coloring problem is a type of CSP where each state can be assigned a color from the set (red,green,blue). The constraint involved says that no two neighbouring state is allowed to have the same color.

Given below is a map of Australia showing its states and territories. You can select a color from the color palette given on the top right and then click on any state to color it with the selected color.

Try to color all the states while satisfying the condition that neighbouring states cannot have the same color.

Arc consistency

• Y = X + 1
• Z >= Y + 1
• W != Y
• W != Z

Step by step visualization of the procedure. Click to restart the simulation.

Sudoku Example of CSP

All sudoku puzzles can be forumulated as CSP by considering each cell as a variable. The initial domain of all cells is {1,2,3,4,5,6,7,8,9}.
The constraints are formulated by the fact that in the solution of a sudoku puzzle, no two cell in a row, column or block can have identical numbers. Thus, there is an AllDiff( ) constraint for all the rows, columns and blocks.

The given sudoku puzzle calculates the reduced domain for each cell and shows them as dots. You can hover over any cell to see how the domain was reduced on the right side of the puzzle. The colors of the cross denote if the number was eliminated due to row, column or block. If the domain of a cell has reduced to just 1 variable (or number), this means we can safely assign that number there. This will further reduce the domain of other cells. Click to assign the number.

Try to solve the entire puzzle by assigning numbers by clicking on cells whose domains have reduced to 1 variable.
Use the restart button to reset the puzzle.

Backtracking Search

Backtracking Search is a type of Search algorithm that is useful to solve CSPs. It interweaves inferences and search to arrive at a solution by pruning parts of the search tree.

It repeatedly chooses an unassigned variable and tries all the possible values for it. If any inconsistency is detected, it backtracks and tries another value for the previous assignment.

In the diagram below, order of selection of variable as well as the order of values for the variable is chosen randomly. Use the Next button to move forward and Previous button to go back. You can also use the slider to go to any state directly.

Restart the diagrams several times and notice how many assignments a random ordering takes. Try to figure out why a particular ordering performs well (or bad).

Min Conflicts

Min conflicts stuff

Tree CSP

Tree CSP Stuff