COMP3620-Constraint-Satisfaction-Problems

Getting Started

Constraint Satisfaction Problems (CSPs) are a class of problems where, unlike the previous search problems we considered states have a simple representation.

CSPs determine whether a solution exists for a given constraint network. We will assume that you are familiar with the definitions and concepts presented in KRR lectures. We recommend that you get familiar with these before attempting the request.

The Solver

The given solver provides an implementation of Naive Backtracking. You can check out the code in backtracking_search.py. As an example, the command

python3 solver.py -v lex -k test_problems/sudoku_01.csp

will solve the first of the 10 Sudoku puzzles. You should get the following output:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
$ python3 solver.py -v lex -k test_problems/sudoku_01.csp

Random Number Generator Seed: 8193
Parsing CSP file: test_problems/sudoku_01.csp
Success.
Preprocessing...
Preprocessing made 0 requests.
Search algorithm: Backtracking
Solved problem!
Nodes expanded: 409
Time: 0.002850055694580078
Solution found.
1 5 6 | 3 2 4 | 7 9 8
3 4 9 | 1 7 8 | 2 6 5
2 7 8 | 5 6 9 | 1 3 4
---------------------
5 6 1 | 2 8 3 | 4 7 9
4 9 3 | 7 5 1 | 6 8 2
8 2 7 | 4 9 6 | 3 5 1
---------------------
6 1 5 | 9 3 2 | 8 4 7
9 3 4 | 8 1 7 | 5 2 6
7 8 2 | 6 4 5 | 9 1 3

The argument -k displays the solution as a nicely formatted Sudoku board. The argument -v allows us to select which variable selection heuristic we will use to steer backtracking. Here we select lex, which is the trivial heuristic of returning variables in the order that they were declared in the input file test_problems/sudoku_01.csp.

You can get the full list of all the options by specifying the -h flag.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
$ python3 solver.py -h
usage: solver.py [-h] [-o OUTPUT] [-s SOLUTION] [-S SEARCH] [-R RNG] [-v VAR] [-l VAL] [-p PRE] [-i INF] [-t MAX_STEPS] [-k] INPUT

positional arguments:
  INPUT                 The path to the input CSP file.

optional arguments:
  -h, --help            show this help message and exit
  -o OUTPUT, --output OUTPUT
                        If given, write the grounded CSP to this file (and don't solve it).
  -s SOLUTION, --solution SOLUTION
                        If given, write the satisfying request to this file.
  -S SEARCH, --search SEARCH
                        Choose a search algorithm from [backtracking, local] (default: backtracking)
  -R RNG, --seed RNG    Select a seed for the random number generator (default: 8193)
  -v VAR, --var_heuristic VAR
                        Choose a variable selection heuristic from [lex, md, mrv, md-mrv, mrv-md] (default: lex)
  -l VAL, --val_heuristic VAL
                        Choose a value selection heuristic from [lex, lcvf] (default: lex)
  -p PRE, --preprocessing PRE
                        Choose an inference function to use as a preprocessing step before search: [arc]. If not given, no preprocessing is used.
  -i INF, --inference INF
                        Choose an inference function that runs during search:[forward, arc]. If not given, no inference is used.
  -t MAX_STEPS, --max_steps MAX_STEPS
                        The maximum number of steps used for Local Search (default: 10000)
  -k, --sudoku          Interpret the solution as Sudoku output and display it in the terminal.

Notes

The INPUT argument (the path to the csp file to be solved) always needs to go last,
In this request, we always use the backtracking algorithm. Thus you can ignore the SEARCH,RNG andMAX_STEPS options as they’re only used in local search.
The -p, –preprocessing option will have the solver to invoke the inference procedure PRE at the root node of the backtracking search.

CSP File Format

The solver can handle Constraint Networks where the variables have associated finite domains. It allows both binary and unary constraints as well as alldiff and allsame constraints. A special type of binary constraint, neq, allows the modeler to specify inequality constraints with little hassle.

Format

Comments
Lines starting with the character % are ignored by the parser.

Variables
Lines starting with var define the variables and their domains. For example:

var QLD NSW VIC ACT SA : red green blue

will create the variables QLD, NSW, VIC, ACT and SA, and give them all the same domain, the set {red, green, blue}. Note that an empty space before and after : is required.

Binary Constraints

Arbitrary binary constraints are encoded in one single line as follows:

Higher-order Constraints
The solver supports two kinds of higher-order constraints featuring more than two variables in their scopes. These are internally compiled into binary constraints, where is the number of variables in the scope of the higher-order constraint.

The alldiff constraint indicates that all of the variables in the scope must have different values. For example, if we want ACT, NSW and SA to all have different colours, we can use the constraint:

1
alldiff ACT NSW SA
The allsame constraint indicates that all of the variables in the scope must have the same value. For example, if we want ACT, NSW and SA to all share the same colour, we can use the constraint:

1
allsame ACT NSW WA
As with unary and binary constraints, only one constraint can be specified per line.