Back to Tutorials.

Tutorial 3: Solving a CSP

For this tutorial, we will refer to the CSP created in Tutorial 1 shown below:

To start solving the CSP, switch over to 'Solve' mode by clicking on the 'Solve' tab. Some menu items which were previously unavailable in 'Create' mode are now enabled. Also, a 'Domain-splitting History' panel will appear at the bottom of the window. The toolbar buttons will change to give you solving options. The solve toolbar will initially look like the toolbar below:

Generally, with CSPs, you would first make a CSP arc-consistent and then check for solutions or, if necessary, recursively split a variable's domain and make the CSP arc-consistent again. An 'arc' between variables refers to the constraint relation between the variables. An arc is arc consistent if for each domain value in one variable, there exists a value in the domain of each other variable such that the constraint between the variables is satisfied. A CSP is 'arc consistent' if all of its arcs are arc consistent. A 'solution' to a CSP is an assignment of a unique value to each variable such that all of the constraints are satisfied.

This applet provides many ways to make a CSP arc-consistent:

• Clicking on the 'Fine Step' button will randomly pick arcs in the CSP and make them arc consistent. Blue edges means that an arc has not been made arc consistent. The first fine step will highlight one of these blue edges and then proceed to make it arc consistent. If the domain of the variable connected to the edge is inconsistent with the constraint relation that it is connected to, then the second fine step will make the arc red. The third fine step will remove values from the domain of the variable that made the arc inconsistent if necessary. When an arc is consistent it will appear green. Note that a green arc may turn blue again if it becomes inconsistent as you are solving the graph and removing domain values from other variables.

• Clicking on the 'Step' button will also randomly pick arcs in the CSP and make them arc consistent. One 'Step' is equivalent to three 'Fine Steps'.

• Clicking directly on an a blue arc will carry out a 'Step' on that arc to make it consistent.

• Clicking on the 'Auto Arc-Consistency' button will fine step through the entire CSP for you, until the CSP is arc consistent or has no solution.

• Clicking on the 'AutoSolve' button will recursively make the CSP arc-consistent and split domains until a solution is found. Clicking on this button again will find another solution, and so on until there are no more solutions. You can specify how you want AutoSolve to split domains by opening the 'AutoSolve Options' dialog under the CSP Options menu. Here you can specify how AutoSolve selects variables to split and how to split them. By default, AutoSolve selects the variable with the smallest number of domain values left and splits the domain in half.

You can stop Auto Arc-Consistency and AutoSolve at any time by clicking the 'Stop' button. To start solving again from the state in which you stopped, simply carry out any of the solving methods mentioned above. You can also change the speed of arc-consistency and select whether you want each fine step to be shown as the CSP is being solved or not. Both of these options are available in the 'CSP Options' menu.

You can reset the CSP to its initial state at any time by clicking on the 'Reset' button.

Once a CSP has been made arc consistent, there are three possibilities:

• There are no domain values left in any variable, which means the CSP has no solution, or no value assignment to each variable such that each constraint is satisfied. In this case the message panel will say the CSP has no solution.

• Each variable in the CSP has exactly one value left in its domain. This is a solution to the CSP, and the final variable value assignment will appear in the message panel.

• If each variable in the CSP has one value in its domain, but at least one variable has greater than one value, then there exists a solution, but domain splitting is required to find it.

After making our example CSP arc consistent it looks like this:

This CSP needs domain splitting to find a solution. Click on any variable that has greater than one value in its domain to split it. The "Split the Domain..." dialog will be shown as below:

The domain values for this variable are displayed. You can manually select which domain values you would like to keep, to solve the CSP with, by clicking on the corresponding value checkboxes. You can also allow the applet to select the first half of the values to keep, or randomly select values to keep. Once you have a reduced domain, some of the arcs in the CSP that were green will have turned blue, meaning that the CSP has to be made arc consistent again. After each split the reduced domain values of a variable will appear in the 'Domain-splitting History' panel at the bottom of the applet window.

A solution to the CSP may not exist given a certain split. In this case a failure for that variable assignment will appear in the 'Domain-splitting History' panel. You can then recover the variable domain values that you discarded when you split a domain by clicking on the 'Backtrack' button and then try solving again.

You may have to split, solve, and backtrack through a CSP recursively until a solution is found.

The history of this process is kept for you in the 'Domain-splitting History' panel.