-
Notifications
You must be signed in to change notification settings - Fork 0
/
csp_sample_run.py
111 lines (92 loc) · 2.98 KB
/
csp_sample_run.py
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
from cspbase import *
from propagators import *
import itertools
x = Variable('X', [1, 2, 3])
y = Variable('Y', [1, 2, 3])
z = Variable('Z', [1, 2, 3])
w = Variable('W', [1, 2, 3, 4])
def w_eq_sum_x_y_z(wxyz):
#note inputs lists of value
w = wxyz[0]
x = wxyz[1]
y = wxyz[2]
z = wxyz[3]
return(w == x + y + z)
c1 = Constraint('C1', [x, y, z])
#c1 is constraint x == y + z. Below are all of the satisfying tuples
c1.add_satisfying_tuples([[2, 1, 1], [3, 1, 2], [3, 2, 1]])
c2 = Constraint('C2', [w, x, y, z])
#c2 is constraint w == x + y + z. Instead of writing down the satisfying
#tuples we compute them
varDoms = []
for v in [w, x, y, z]:
varDoms.append(v.domain())
sat_tuples = []
for t in itertools.product(*varDoms):
#NOTICE use of * to convert the list v to a sequence of arguments to product
if w_eq_sum_x_y_z(t):
sat_tuples.append(t)
c2.add_satisfying_tuples(sat_tuples)
simpleCSP = CSP("SimpleEqs", [x,y,z,w])
simpleCSP.add_constraint(c1)
simpleCSP.add_constraint(c2)
btracker = BT(simpleCSP)
#btracker.trace_on()
print("Plain Bactracking on simple CSP")
btracker.bt_search(prop_BT)
print("=======================================================")
print("Forward Checking on simple CSP")
btracker.bt_search(prop_FC)
print("=======================================================")
print("GAC on simple CSP")
btracker.bt_search(prop_GAC)
#Now n-Queens example
def queensCheck(qi, qj, i, j):
'''Return true if i and j can be assigned to the queen in row qi and row qj
respectively. Used to find satisfying tuples.
'''
return i != j and abs(i-j) != abs(qi-qj)
def nQueens(n):
'''Return an n-queens CSP'''
i = 0
dom = []
for i in range(n):
dom.append(i+1)
vars = []
for i in dom:
vars.append(Variable('Q{}'.format(i), dom))
cons = []
for qi in range(len(dom)):
for qj in range(qi+1, len(dom)):
con = Constraint("C(Q{},Q{})".format(qi+1,qj+1),[vars[qi], vars[qj]])
sat_tuples = []
for t in itertools.product(dom, dom):
if queensCheck(qi, qj, t[0], t[1]):
sat_tuples.append(t)
con.add_satisfying_tuples(sat_tuples)
cons.append(con)
csp = CSP("{}-Queens".format(n), vars)
for c in cons:
csp.add_constraint(c)
return csp
def solve_nQueens(n, propType, trace=False):
csp = nQueens(n)
solver = BT(csp)
if trace:
solver.trace_on()
if propType == 'BT':
solver.bt_search(prop_BT)
elif propType == 'FC':
solver.bt_search(prop_FC)
elif propType == 'GAC':
solver.bt_search(prop_GAC)
#trace = True
trace = False
print("Plain Bactracking on 8-queens")
solve_nQueens(8, 'BT', trace)
print("=======================================================")
print("Forward Checking 8-queens")
solve_nQueens(8, 'FC', trace)
print("=======================================================")
print("GAC 8-queens")
solve_nQueens(8, 'GAC', trace)