Maze
assignment for Constraint Processing Theory
July 27th, 2018
In this exercise you will have to write a program that can help you find a way out of a maze – labyrinth. Suppose the design of the maze is given in a form of
f ield(x1, y1, x2, y2, 1).
meaning, that there is a wall – quadratic block which you cannot pass, spread between points (x1, y1) and (x2, y2), and suppose a step that we can take inside this maze is defined in a form of
step(x1, y1, x2, y2)
meaning, that we take a step from point (x1, y1) to (x2, y2). For reference,
consider an example design below
1
In this case, the design of labyrinth could be defined as follows
field(0,−1,1,0,1). field(1,−1,2,0,1). ···
f ield(15, 7, 16, 8, 1).
and the solution to this example, found by the algorithm, should be as follows (assumed, that starting point is at (1, 1))
[step(1, 1, 2, 1), step(2, 1, 3, 1), ··· step(15, 6, 16, 6)]
This is just a reference example. The way of designing the maze is de- pendent on you. Your program should analyze the design of the maze (as its only input data) and produce a list of steps, defining a way leading from the entrance to the exit (for any labyrinth, not just the one in the example above).
2
Constraint Solver(1)
1
2014/1/9 Simplification of Constraint
2
Constraint Satisfaction Problems
A CSP consists of a constraint C over variables x1,…,xn and a domain D that maps each variable xi to a finite set of values, written D(xi), which it is allowed to take. The CSP is understood to represent the constraint C∧x1∊D(x1)∧…∧xn∊D(xn).
2014/1/9 Simplification of Constraint
3
An example of CSP
Map colouring problem
N-queens problem
And many other problems
R1≠R2∧R1≠R3∧R1≠R4∧…∧ C1≠C2∧C1≠C3∧C1≠C4∧…∧ C1-R1≠C2-R2∧C1-R1≠C3-R3∧…∧… C1+R1≠C2+R2∧C1+R1≠C3+R3∧…
Q
Q
Q
Q
2014/1/9
Simplification of Constraint
4
A simple backtracking solver
A complete solver for CSPs which has exponential time complexity.
Algorithm
Input: A CSP with constraint C and domain D Output: Returns true if C is satisfiable, otherwise false
Method: Shown in the next page
2014/1/9 Simplification of Constraint
C and C1 are constraints; c1,…,cn are primitive constraints; D is a domain;
x is a variable;
back_solve(C,D)
return partial_satisfiable(C) se
choose x∈vars(C)
for each value d∈D(X) do
let C1 be obtained from C by replacing x by d if partial_satisfiable(C1) then
if back_solve(C1,D) then return true
endif endif
endfor return false
5
endif
2014/1/9
Simplification of Constraint
if vars(C)≡Φ then
el
partial_satisfiable(C)
let C be of the form c1∧…∧…Cn
for i:=1 to n do
if vars(ci)≡Φ then
if satisfiable(ci)≡false then
return false
endif endif
endfor return true
※satisfiable(c) is a function which takes a primitive constraint c that involves no variables and returns true or false indicating whether c is satisfiable or not.
6
2014/1/9 Simplification of Constraint
7
Node consistency for binary CSPs
A primitive constraint c is node consistent with domain D if either |vars(c)|≠1 or, if vars(c)={x}, then for each d∈D(x),{x→d} is a solution of c.
A CSP with constraint c1∧…∧cn and domain D is node consistent if each primitive constraint ci is node consistent with D for 1≦i≦n.
2014/1/9 Simplification of Constraint
8
Arc consistency for binary CSPs
A primitive constraint c is arc consistent with domain D if either |vars(c)|≠2 or, if vars(c)={x,y}, then for each dx∈D(x), there is some dy∈D(y) such that {x→dx,y→dy} is a solution of c and for each dy∈D(y), there is some dx∈D(x) such that {x→dx,y→dy} is a solution of c.
A CSP with constraint c1∧…∧cn and domain D is arc consistent if each primitive constraint ci is arc consistent with D for 1≦i≦n.
2014/1/9 Simplification of Constraint
9
An example
X<Y ∧ Y<Z ∧ Z≦2
with the domain D where D(X)=D(Y)=D(Z)={1,2,3}
Is this node consistent? Or arc consistent?
2014/1/9 Simplification of Constraint
10
Node consistency algorithm
INPUT: A CSP with constraint C and domain D1
OUTPUT: Returns a domain D2 such that the CSP with constraint C and domain D2 is node consistent and is equivalent to the input CSP
METHOD: The algorithm is shown in the next page
2014/1/9
2014/1/9
x is a variable;
C is a constraint;
D is a domain;
c1, …, cn are primitive constraints; and d is a domain value.
node_consistent(C,D)
let C be of form c1∧ …∧cn for i := 1 to n do
D := node_consistent_primitive(ci , D) endfor
return D
node_consistent_primitive(c, D) if |vars(c)| = 1 then
let {x} = vars(c)
D(x) := {d∈D(x) | {x → d} is a solution of c} endif
return D
Node consistency algorithm
11
12
Arc consistency algorithm
INPUT: A CSP with constraint C and domain D1
OUTPUT: Returns a domain D2 such that the CSP with constraint C and domain D2 is arc consistent and is equivalent to the input CSP
METHOD: The algorithm is shown in the next page
2014/1/9
13
Assignment
Write down arc consistency algorithm (use pseudo code like node consistency algorithm)
- To: yoshie@waseda.jp
- Title: your student number
- Deadline: 13:00 on Jan. 16th
2014/1/9