-
Notifications
You must be signed in to change notification settings - Fork 0
/
solver.py
162 lines (130 loc) · 3.63 KB
/
solver.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
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
from z3 import *
import sys
from pathlib import Path
folder = Path(__file__).parent.parent
sys.path.append(str(folder))
#print(sys.path)
#from deps.PyMiniSolvers import minisolvers
class TCube:
def __init__(self, t=0, solverName='z3'):
self.t = t
if solverName == 'z3':
self.solver = Z3Solver()
else:
self.solver = MiniSat()
# abstract class. The new Solver should inherit the class.
class MSolver:
def __init__(self):
self.clauses = list()
def newVar(self, name: str):
raise NotImplementedError
def newNot(self, var):
raise NotImplementedError
def addClause(self, clause):
raise NotImplementedError
def push(self):
raise NotImplementedError
def pop(self):
raise NotImplementedError
def check(self) -> bool:
raise NotImplementedError
def getModel(self):
raise NotImplementedError
class Z3Solver(MSolver):
def __init__(self):
super().__init__()
self.solver = Solver()
def newVar(self, name: str):
return Bool(name)
def newNot(self, var):
return Not(var)
def addClause(self, clause):
self.clauses.append(Or(clause))
self.solver.add(Or(clause))
def push(self):
self.solver.push()
def pop(self):
self.solver.pop()
def check(self) -> bool:
if sat == self.solver.check():
return True
return False
def getModel(self):
if self.check():
return self.solver.model()
raise AssertionError("UNSAT")
# Only support push ONCE.
class MiniSat(MSolver):
def __init__(self):
super().__init__()
self.solver = minisolvers.MinisatSolver()
self.nameMap = dict()
self.nVar = 0
self.pushSolver = minisolvers.MinisatSolver()
self.pushNVar = 0
self.pushClauses = list()
def newVar(self, name: str):
self.solver.new_var()
self.nVar += 1
self.nameMap[self.nVar] = name
return self.nVar
def newNot(self, var):
return -1 * var
def addClause(self, clause):
self.clauses.append(clause)
self.solver.add_clause(clause)
def push(self):
self.pushSolver = self.solver
self.solver = minisolvers.MinisatSolver()
for i in range(self.nVar):
self.solver.new_var()
for i in self.clauses:
self.solver.add_clause(i)
self.pushNVar = self.nVar
self.pushClauses = self.clauses.copy()
def pop(self):
self.solver = self.pushSolver
self.nVar = self.pushNVar
self.clauses = self.pushClauses
def check(self) -> bool:
if self.solver.solve():
return True
return False
def getModel(self):
if self.check():
m = self.solver.get_model()
ret = dict()
for i, v in enumerate(list(m)):
if v == 1:
ret[self.nameMap[i + 1]] = True
else:
ret[self.nameMap[i + 1]] = False
return ret
raise AssertionError("UNSAT")
if __name__ == '__main__':
s = MiniSat()
t = s.newVar("t")
b = s.newVar('b')
s.addClause([t])
s.addClause([b])
if s.check():
print("YES")
print(s.getModel())
else:
print("OK")
s.push()
s.addClause([s.newNot(t)])
if s.check():
print("SAT")
print(s.getModel())
else:
print("UNSAT")
s.pop()
s.push()
s.addClause([s.newVar('c')])
if s.check():
print("SAT")
print(s.getModel())
else:
print("UNSAT")
s.pop()