使用AI算法,解决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 assignment.
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
1 | 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 | $ python3 solver.py -v lex -k test_problems/sudoku_01.csp |
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 | $ python3 solver.py -h |
Notes
- The
INPUT
argument (the path to thecsp
file to be solved) always needs to go last, - In this assignment, we always use the
backtracking
algorithm. Thus you can ignore theSEARCH
,RNG
andMAX_STEPS
options as they’re only used in local search. - The
-p
,--preprocessing
option will have the solver to invoke the inference procedurePRE
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:
1 | 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:
1 | con WA NT : red green : red blue : green red : green blue : blue red : blue green |
Unary Constraints
Unary constraints are encoded similarly to binary constraints:
1 | con NT : red : blue |
This constraint restricts the domain of the variable NT
to have either the values red
or blue
. Note that unary constraints are compiled away by the solver by modifying the domains of the variables affected and setting values in the initial assignment.
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.