使用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
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:
$ 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 assignments.
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.
$ 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 assignment 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
INPUTargument (the path to thecspfile to be solved) always needs to go last, - In this assignment, we always use the
backtrackingalgorithm. Thus you can ignore theSEARCH,RNGandMAX_STEPSoptions as they’re only used in local search. - The
-p,\--preprocessingoption will have the solver to invoke the inference procedurePREat 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:
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:
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:
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:
allsame ACT NSW WA
—|—
As with unary and binary constraints, only one constraint can be specified per
line.
