Back to help contents.
Contents
Overview
A constraint satisfaction problem, or CSP, is a problem which can be expressed
as a set of variables, each with a particular domain, and a set of constraint
relations between variables. A solution to a CSP is an assignment of a
unique value to each variable such that all the of the constraint relations
are satisfied.
This applet is designed to let you create such a problem and solve it
using a consistency based algorithm with backtracking.
Menus
File Menu
-
Create New CSP- Discard the current CSP and start creating from an
empty CSP.
-
Load Sample CSP - Load a problem from a set of sample problems.
- Load From File - Load a problem from
the local disk.
- Load From URL - Load a problem by specifying a url where the CSP is located.
-
Save CSP - Save the CSP to the
local disk.
-
Print - Prints the canvas as displayed in Solve mode.
-
Quit - Close the CSP Applet window.
Edit Menu
- Undo - lets you undo the last operation if applicable. This is only available in "Create" mode.
- View/Edit Text Representation - Opens a window containing the text
representation of the CSP. The text can be edited in create mode. The CSP can be updated
from the text representation window by clicking the "Update CSP" button.
With this feature, a CSP can be indirectly loaded from a locally saved
text file by pasting the text representation of a CSP to the text representation
window.
- View Current State Text Representation - in solve mode, this allows you
to export the current state of the CSP (with domains restricted to the current assignments).
View Menu
- Font Size - Set the font size used in the CSP.
- Line Width - Set the width of lines displayed in the CSP.
- Autoscale - Adjust the CSP to be fitted in canvas.
- Pan/Zoom - Select which mode to be in. Then when right-clicking and dragging the mouse on canvas, you can pan or zoom the CSP on the canvas.
- Arrange Constraints - This will adjust the CSP so that each constraint is arranged directly between its corresponding variables.
- Enable Anti-Aliasing - Enables/disables anti-aliasing.
- Show Message Panel - Show or hide the message prompts above the main canvas.
- Show Button Text - Show or hide the text on the buttons in the toolbar.
- Show Buttons - Show or hide the removable toolbar buttons.
CSP Options Menu
- Arc-Consistency Speed - Set the speed of Auto Arc-Consistency and AutoSolving.
- AutoSolve Options - Lets you set how you want AutoSolving to split variable domains. In the AutoSolve Options dialog, you can set the order that variables are selected for domain splitting and how domains are split.
- Show Fine Steps - Determines whether fine steps such as the selection of
constraints and the highlighting of affected constraints, should be graphically displayed when solving.
Help Menu
- Legend for Nodes/Edges - Opens a dialog with a legend for describing what the graph shapes/colours mean.
- Help -
Opens this web page, which provides general help on the Decision Tree Learning applet.
- Tutorials - Opens up the Tutorial web page. Tutorials walk through how to use the applet.
- About CIspace -
Provides brief information about the CIspace project.
- About this Applet -
Identifies the applet version and names of developers.
Create
Mode
Create a Variable
- To create a variable, press the "Create Variable" button and
click on the white canvas at the location you want the variable to appear.
This will bring up a dialog box where you can enter the name, domain type,
and domain values of the variable represented by the variable you're creating.
- The variable name can be almost anything you want as long as it has no
spaces, and no "<", ">". It's best if the variable
name is capitalized and starts with an alphabetic character.
- The default domain type is boolean, and a boolean domain initially consists
of {true, false}. To get a different domain type, simply select the appropriate radio button next to "Domain Type:" of the type you
want the variable to be. The other domain types
are initially empty.
- When you've selected a domain type you can enter domain values in the text field next to "Domain:".
String values can be almost anything; it's best if they have no spaces and
contain no commas. Integers must be integers for instance; 1,2,35,10001. Boolean
values must be either "true" or "false". An example of how to enter domain values appropriately for the specified domain type is below the text field.
- Click "OK" when you are done and the new variable will appear.
Creating a Constraint
- There are four actions to initiate the creation of a constraint.
- With the "Create Constraint" button depressed:
- click on a blank space in the canvas to create a constraint with
no variables
- click on a variable and then click on a blank space in the canvas
to create a constraint with one variable
- click on a variable and then click on another variable to create
a binary constraint.
- With the "Add Variable to Constraint" button depressed:
- click on an existing constraint and then on an existing variable or vice versa to add that variable to the constraint, allowing for k-ary constraints.
- Once it has been initiated, the variable dialog will open with Custom constraint
selected. You can modify the truth table of the custom constraint by clicking on the table and selecting the appropriate true/false values. You can label custom constraints by typing the name that you want to have appear on the canvas in the text area next to "Custom Name."
- You can select a built-in constraint type by selecting one from the pull down list of available constraint types for this constraint's variables next to "Constraint Type:".
- Click "OK" when finished, and the new constraint (with its label) will
appear.
Selecting/Modifying/Removing Variables and Constraints
- You can select and move variables and constraints by pressing the "Select" button and clicking and dragging an entity.
- You can delete an entity by pressing "Delete" and clicking on variables and
constraints. In this manner you can also remove
a variable from a constraint by clicking on an edge connecting a variable
to a constraint.
- To modify variable and constraint properties, simply click on them when the "Set
Properties" button is selected, and an appropriate dialog will appear.
Editing the Text Representation
-
Sometimes the graphical user interface isn't efficient for creating the
CSP you want. By selecting "View/Edit Text Representation" from the edit
menu, you can directly edit the text representation of the CSP. This
is useful if you have many identical domains with lots of elements and
you'd like to avoid retyping all the domain elements for each Variable. It's
also useful if you want to modify a variable after you've created it. Simply
make the changes you want, and then click "Update" to load the new
CSP.
Creating a New CSP
-
To delete the current CSP and start with a blank canvas, select "Create New CSP" in the "File" menu.
-
Loading CSPs:
- A set of sample CSPs is available for loading from "Load Sample CSP" in the "File" menu.
- A CSP can be loaded from a URL from "Open Location" in the "File" menu.
- A CSP can be loaded
from a saved file on the local disk by selecting "Open CSP" in the "File"
menu.
-
Saving CSPs:
- The current CSP can be saved to a file on the local disk by selecting "Save"
in the "File" menu.
-
Loading and Saving CSPs by Cut-and-Paste:
- The user can save the text representation of the current CSP by cut-and-paste from the Text Representation Frame
(the frame is displayed by selecting the "View/Edit Text Representation"
item in the "Edit" menu). In UNIX-based systems, you select the text,
and then middle-click on a window where you want the text to be stored,
such as a text-editing program. In Windows-based systems, you can use Ctrl-C
to copy and Ctrl-V to paste.
- To load a previously saved CSP, just paste the text representation
into the "View/Edit Text Representation" window, and click the "Update CSP" button.
Solve
Mode
Manual Arc-Consistency:
-
To run through the arc consistency algorithm manually, either click the "Step" or "Fine Step" button to step through the algorithm (this selects an arc on the queue and makes it consistent), or simply click on an arc to make it consistent. A blue arc is an arc that has not been made consistent. A green arc is an arc that is
consistent. If the 'Show Fine Steps' checkbox is selected under the 'CSP Options' menu, then arcs may appear red as constraint inconsistencies arise during the arc
consistency process.
Auto Arc-Consistency:
- This button starts Auto Arc-Consistency. It continues until the network
is arc-consistent, or until the user clicks on the "Stop" button. To adjust
the speed of arc consistency, select the appropriate check box in the "Arc-Consistency Speed" menu under the "CSP Options" menu. To perform Auto Arc-Consistency without showing fine steps on each step, uncheck "Show Fine Steps", also from the "CSP Options" menu.
AutoSolve:
- This button starts AutoSolving. AutoSolving recursively makes the CSP arc consistent and splits domains if necessary until a solution is found. Each click of the AutoSolve button finds one solution until there are no more solutions to be found. AutoSolve splits domains according to what is specified in the
"AutoSolve Options" dialog. By default, AutoSolve selects the variable with the smallest number of domain values left and splits the domain in half. You can modify how AutoSolve splits domains by opening the
"AutoSolve Options" dialog under the "CSP Options" menu. The "Arc-Consistency Speed" selected under this menu also affects AutoSolving, as does the "Show Fine Steps" checkbox.
Domain Splitting and Backtracking:
-
To break the CSP recursively into two smaller parts, you can split a domain.
To do this manually, click on the variable whose domain you want to split. A
dialog box will appear, and you can choose which values from the domain
you want to keep. Click "OK" when you have done this, and then you can
perform AC on the reduced domain. Click on the "Backtrack" button when
you want to try solving the CSP using the complement of the reduced domain
(i.e., with the domain values you removed before).
-
The history of the recursive domain-splitting process is shown in the Domain-splitting History panel at the bottom of the window.
Algorithms
This applet uses an arc consistency algorithm which is implemented as follows:
-
A list, L, is maintained of all potentially inconsistent arcs. This
initially consists of all arcs.
-
Arcs are selected from L in an essentially arbitrary manner, based
only on their graph index.
-
Once selected, each value in the variable, V, connected to the arc
is compared against the constraint. Any value which is not valid given
any possible assignment to the other variables in the constraint is removed
from V.
-
Finally arcs to other variables on all other constraints connected to V
are added to L.
-
The algorithm completes once L is empty.
Domain Splitting can occur at any stage in the process and is user prompted:
-
Here values for a variable are selected by the user and the domain is pruned.
-
All information related to the current state is stored for backtracking.
Backtracking can also occur at any stage, and is user prompted:
- Variable V is the most recent variable to have been split and not
to have been backtracked on.
- V is set to all the values which were pruned the most recent time
it was split.
- The other variables are reset to the values they had when V was
last split.
CSP Specification
Domain Types:
Domains are discrete sets of elements of the following types.
- Boolean - A domain consisting of only "true" or "false"
values, there can be an unlimited number of either.
- Integer - A domain consisting of only integer values, ...-3,-2,-1,0,1,2,3...
- String - A domain consisting of a set of strings
Constraint Types:
Constraints consist of a set of variables and a relation which determines a
truth value for each combination of elements from the set of variables. Constraints
can have any number of variables but the relations are undetermined if a variable's
domain is empty. Some constraint types are restricted in the variable types
they accept. In all cases the variables can be reordered via the constraint
dialog.
- Custom - User decides the truth value for each variable assignment. Any combination
of variables are accepted.
- False - This constraint is always false. Any combination of Variables are
accepted. The complement can be taken and is equivalent to the True constraint.
- True - This constraint is always true. Any combination of Variables are accepted.
The complement can be taken and is equivalent to the False constraint.
Boolean Constraints, accept only boolean variables. In all cases complement
can be taken.
- And - Logical And, all of the variables are true.
- Or - Logical Or, one of the variables is true.
- XOr - Exactly one of the variables is true.
- Implies (->) - Implication of first variable with the conjunction (And)
of the remaining variables. True unless the first variable is false and all
remaining variables are true.
Number Constraints, accept only integer variables. In all cases complement
can be taken.
- Equal (=) - true if all variables are equal.
- LessThan (<) - true if each variable is strictly less than all variables
following it in the constraint.
- GreaterThan (>) - true if each variable is strictly greater than all variables
following it in the constraint.
- Queens - Implements Queens constraint as in the n-Queens problem. This problem
tries to put as nQueens on a chessboard such that in one move no Queen can
take another Queen (for each queen there is no queen along its diagonals or
in the same row or column. User specifies the number of rows separating adjacent
variables in the constraint. The integer value of each variable specifies
the column.
String Constraints, accept only strings. In all cases complement can be taken.
- LengthEqual - true if the length of all string elements in question have
the same number of characters.
- LengthLess - true if each variable has strictly fewer characters than all
variables following it in the constraint.
- LengthGreat - true if each variable has strictly more characters than all
variables following it in the constraint.
- Crossword - Takes two arguments, X and Y, from the user. It is true if the Xth character of the first variable is equal to the Yth character of all other
variables.
|