Back to help contents.

Contents

Overview

Menus

Create Mode

Solve Mode

Algorithms

CSP Specification

Overview

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

• 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.

• 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.

• 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:

• 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.