-
Notifications
You must be signed in to change notification settings - Fork 0
/
csp.py
91 lines (75 loc) · 2.16 KB
/
csp.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
'''Implementation of the Generalized Lookahead Search algorithms'''
import json
import copy
import gui
class csp():
def __init__(self, filename):
with open(filename) as data_file:
data = json.load(data_file)
self.domain = {}
for var in data["variables"]:
self.domain[var["name"]] = var["domain"]
self.constraints = {}
for c in data["constraints"]:
a = c["scope"][0]
b = c["scope"][1]
self.constraints[(a,b)] = c["relation"]
self.order = data["ordering"]
self.assign = {}
self.pruned = {}
self.gui = gui.gui(self.domain, self.constraints, self.order)
def consistent(self, x1, v1, x2, v2):
if((x1,x2) in self.constraints.keys()):
rel = self.constraints[(x1,x2)]
return ([v1,v2] in rel)
elif((x2,x1) in self.constraints.keys()):
rel = self.constraints[(x2,x1)]
return ([v2,v1] in rel)
else:
return True
def selectValueFC(self, index, var, dom, assignment):
while len(dom[var[index]]):
flag = 0
temp = copy.deepcopy(dom)
val = dom[var[index]][0]
dom[var[index]].remove(val)
for k in range(index+1, len(var)):
for b in dom[var[k]]:
if(not self.consistent(var[index], val, var[k], b)):
dom[var[k]].remove(b)
self.gui.update(dom,self.assign,var[index], val)
if(not len(dom[var[k]])): # inconsistent
temp[var[index]] = copy.deepcopy(dom[var[index]])
dom = copy.deepcopy(temp)
flag = 1
break
self.gui.update(dom,self.assign, var[index], val)
if(not flag):
return val, dom
return None, dom
def genaralisedLookAhead(self):
dom = copy.deepcopy(self.domain)
var = self.order
domains = []
i = 0
while(i>=0 and i<len(var)):
domains.append(copy.deepcopy(dom))
a, dom1 = self.selectValueFC(i, var, dom, self.assign)
if(not a):
# print "Backtrack at "+var[i]
i = i-1
dom = domains.pop()
dom = domains.pop()
dom[var[i]] = dom1[var[i]]
self.assign.pop(var[i])
else:
self.assign[var[i]] = a
dom = copy.deepcopy(dom1)
i = i+1
self.gui.update(dom,self.assign)
if i<0:
return None
else:
return self.assign
pb = csp('t1.json')
print pb.genaralisedLookAhead()