Repository navigation
Expand file tree
/
Copy pathCSPSolver.java
More file actions
238 lines (190 loc) · 6.26 KB
/
Copy pathCSPSolver.java
File metadata and controls
238 lines (190 loc) · 6.26 KB
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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
/**
* A CSP solver using the static variable order. Prepared for COSC 322.
*
* @author yongg
*
*/
public class CSPSolver {
public int consistencyLevel = ConstraintPropagator.CONSISTENCY_LEVEL_ARC_CONSISTENCY;
public int[] solution; //the assignment to the variables
public CSPInstance csp = null; // the CSP instance to solve
public int backtracking = 0; //recording the number of backtracks
/**
Calls the forward checking method
*/
private boolean forwardChecking(int current, int value){
//CSPInstance csp = new CSPInstance(C, domains);
boolean nonemptyDomain = ConstraintPropagator.forwardChecking(csp, current, value);
return nonemptyDomain; // true;
}
/**
Calls the arcConsistency method
*/
private boolean arc_consistency(int currentLevel){
//CSPInstance csp = new CSPInstance(C, domains);
boolean nonemptyDomain = ConstraintPropagator.arcConsistency(csp, currentLevel);
return nonemptyDomain; //true;
}
/**
* Call this to start the solver
* @param csp: a CSP instnace
* @param consistencyLevel: the level of consistency to be maintained
*/
public void solve(CSPInstance csp, int consistencyLevel)
{
this.csp = csp;
solution = new int[csp.numOfVariables];
// do an arc consistency as a pre-processing step.
if(consistencyLevel == ConstraintPropagator.CONSISTENCY_LEVEL_ARC_CONSISTENCY)
{
boolean result = arc_consistency(-2);
if(result == false)
{
String msg = "Instance found unsatisfiable during pre-processing.";
output(result, msg);
return;
}
}
//call the recursive procedure to start the backtracking
boolean result = backtrackingSearch(0, consistencyLevel);
output(result, null);
}
//int current: the current level of the search tree (begins with 0, the first variable)
//int consistencyLevel: the level of constraint consistency to be maintained
private boolean backtrackingSearch(int currentLevel, int consistencyLevel )
{
// if the recursion gets to the level N, then all the variables
// have been assigned without creating any conflict
if(currentLevel == csp.numOfVariables)
{
return true;
}
// for each domain value of the current variable x_current
for(int i = 0; i < csp.numOfDomains; i++)
{
// domain value i is currently not allowed for whatever reasons
if(csp.domains[currentLevel][i] != CSPInstance.IS_VALID)
continue;
// assign the value i to the current variable
solution[currentLevel] = i;
//this is where the forward checking
boolean consistent = true;
if(consistencyLevel >= ConstraintPropagator.CONSISTENCY_LEVEL_FORWARD_CHECKING)
{
consistent = this.forwardChecking(currentLevel, solution[currentLevel]);
}
if(consistencyLevel >= ConstraintPropagator.CONSISTENCY_LEVEL_ARC_CONSISTENCY)
{
consistent = this.arc_consistency(currentLevel);
}
//dump(current);
//For now, the assignment solution[current] = i is ok, we continue the search
if(consistent)
{
boolean success = backtrackingSearch(currentLevel + 1, consistencyLevel);
if(success){
return true;
}
else{
//if at some point, the recursion call fails, we backtrack
backtracking++;
}
}
//restore the matrix int[][] domains to the state priori to
//calling to the consistency checking
restore(currentLevel);
}
//all the available domain values of x_current have been tried
//without success
return false;
}//end of backtrackingSearch
//Restore the domain matrix when backtracking
private void restore(int levelNumber)
{
for(int i = levelNumber + 1; i < csp.numOfVariables; i++)
{
for(int d = 0; d < csp.numOfDomains; d++)
{
if(csp.domains[i][d] == levelNumber)
{
csp.domains[i][d] = CSPInstance.IS_VALID;
}
}
}
}
// the rest are some helper functions for output and solution verification
//output solving info
private void output(boolean result, String msg){
System.out.println("------------------------------");
System.out.println("Solving a CSP instance: N = " + csp.numOfVariables + ", K = " + csp.numOfDomains +
", E = " +csp.numOfConstraints);
System.out.println("Num of Backtracking = " + backtracking);
if(msg != null){
System.out.println(msg);
}
if(!result){
System.out.println("Instance Unsatisfiable!");
}
else{
boolean v = verifySolution();
if(!v){
System.out.println("Fail to verify the solution");
}
else{
System.out.println("Solution Verified");
printSolution();
}
}
System.out.println("------------------------------");
System.out.println();
}
//verifyies the solution
private boolean verifySolution()
{
boolean verified = true;
for(int i = 0; i < csp.numOfVariables; i++)
{
if(csp.domains[i][solution[i]] == - 2)
{
verified = false;
return verified;
}
}
for(int i = 0; i < csp.numOfVariables; i++)
{
for(int j = i + 1; j < csp.numOfVariables; j++)
{
if(csp.constraints[i][j] != null)
{
if(!csp.constraints[i][j].isCompatible(solution[i], solution[j]))
{
verified = false;
return verified;
}
}
}
}
return verified;
}
//print the solution
private void printSolution()
{
//System.out.print(solution[0]);
for(int i = 0; i < csp.numOfVariables; i++)
{
System.out.print("[x" + i + "=" + solution[i] + "]");
}
System.out.println();
}
//dump the state of the CSP instance
private void dump(int current)
{
printSolution();
for(int i = 0; i < csp.numOfVariables; i++){
for(int j = 0; j < csp.numOfDomains; j++){
System.out.print(csp.domains[i][j] + " ");
}
System.out.println();
}
}
} //end of the class