1
|
package org.distorted.solvers.cube3;
|
2
|
|
3
|
import android.content.res.Resources;
|
4
|
|
5
|
import android.util.Log;
|
6
|
|
7
|
//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
8
|
/**
|
9
|
* Class Search implements the Two-Phase-Algorithm.
|
10
|
*/
|
11
|
public class Search {
|
12
|
|
13
|
static boolean mInterrupted;
|
14
|
static int mNumMoves = 0;
|
15
|
|
16
|
static int[] ax = new int[31]; // The axis of the move
|
17
|
static int[] po = new int[31]; // The power of the move
|
18
|
|
19
|
static int[] flip = new int[31]; // phase1 coordinates
|
20
|
static int[] twist = new int[31];
|
21
|
static int[] slice = new int[31];
|
22
|
|
23
|
static int[] parity = new int[31]; // phase2 coordinates
|
24
|
static int[] URFtoDLF = new int[31];
|
25
|
static int[] FRtoBR = new int[31];
|
26
|
static int[] URtoUL = new int[31];
|
27
|
static int[] UBtoDF = new int[31];
|
28
|
static int[] URtoDF = new int[31];
|
29
|
|
30
|
static int[] minDistPhase1 = new int[31]; // IDA* distance do goal estimations
|
31
|
static int[] minDistPhase2 = new int[31];
|
32
|
|
33
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
34
|
// retyurn number of moves in the already computed solution
|
35
|
public static int numMoves()
|
36
|
{
|
37
|
return mNumMoves;
|
38
|
}
|
39
|
|
40
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
41
|
// generate the solution string from the array data
|
42
|
static String solutionToString(int length)
|
43
|
{
|
44
|
String s = "";
|
45
|
|
46
|
for (int i = 0; i < length; i++) {
|
47
|
switch (ax[i]) {
|
48
|
case 0: switch(po[i])
|
49
|
{
|
50
|
case 1: s+=" 420"; break;
|
51
|
case 2: s+=" 548"; break;
|
52
|
case 3: s+=" 164"; break;
|
53
|
}
|
54
|
break;
|
55
|
case 1: switch(po[i])
|
56
|
{
|
57
|
case 1: s+=" 388"; break;
|
58
|
case 2: s+=" 516"; break;
|
59
|
case 3: s+=" 132"; break;
|
60
|
}
|
61
|
break;
|
62
|
case 2: switch(po[i])
|
63
|
{
|
64
|
case 1: s+=" 452"; break;
|
65
|
case 2: s+=" 580"; break;
|
66
|
case 3: s+=" 196"; break;
|
67
|
}
|
68
|
break;
|
69
|
case 3: switch(po[i])
|
70
|
{
|
71
|
case 1: s+=" 161"; break;
|
72
|
case 2: s+=" 033"; break;
|
73
|
case 3: s+=" 417"; break;
|
74
|
}
|
75
|
break;
|
76
|
case 4: switch(po[i])
|
77
|
{
|
78
|
case 1: s+=" 129"; break;
|
79
|
case 2: s+=" 001"; break;
|
80
|
case 3: s+=" 385"; break;
|
81
|
}
|
82
|
break;
|
83
|
case 5: switch(po[i])
|
84
|
{
|
85
|
case 1: s+=" 193"; break;
|
86
|
case 2: s+=" 065"; break;
|
87
|
case 3: s+=" 449"; break;
|
88
|
}
|
89
|
break;
|
90
|
}
|
91
|
}
|
92
|
return s;
|
93
|
};
|
94
|
|
95
|
/**
|
96
|
* Interrupt current computation
|
97
|
*/
|
98
|
public static void interrupt()
|
99
|
{
|
100
|
mInterrupted = true;
|
101
|
}
|
102
|
|
103
|
/**
|
104
|
* Prepare pruning tables
|
105
|
*/
|
106
|
public static boolean prepare(Resources res)
|
107
|
{
|
108
|
if( mInterrupted ) return false;
|
109
|
CoordCube.initialize1(res);
|
110
|
|
111
|
if( mInterrupted ) return false;
|
112
|
CoordCube.initialize2(res);
|
113
|
|
114
|
if( mInterrupted ) return false;
|
115
|
CoordCube.initialize3(res);
|
116
|
|
117
|
if( mInterrupted ) return false;
|
118
|
CoordCube.initialize4(res);
|
119
|
|
120
|
if( mInterrupted ) return false;
|
121
|
CoordCube.initialize5(res);
|
122
|
|
123
|
if( mInterrupted ) return false;
|
124
|
CoordCube.initialize6(res);
|
125
|
|
126
|
if( mInterrupted ) return false;
|
127
|
CoordCube.initialize7(res);
|
128
|
|
129
|
if( mInterrupted ) return false;
|
130
|
CoordCube.initialize8(res);
|
131
|
|
132
|
if( mInterrupted ) return false;
|
133
|
CoordCube.initialize9(res);
|
134
|
|
135
|
if( mInterrupted ) return false;
|
136
|
CoordCube.initialize10(res);
|
137
|
|
138
|
if( mInterrupted ) return false;
|
139
|
CoordCube.initialize11(res);
|
140
|
|
141
|
if( mInterrupted ) return false;
|
142
|
CoordCube.initialize12(res);
|
143
|
|
144
|
if( mInterrupted ) return false;
|
145
|
|
146
|
return true;
|
147
|
}
|
148
|
/**
|
149
|
* Computes the solver string for a given cube.
|
150
|
*
|
151
|
* @param facelets
|
152
|
* is the cube definition string, see {@link Facelet} for the format.
|
153
|
*
|
154
|
* @param maxDepth
|
155
|
* defines the maximal allowed maneuver length. For random cubes, a maxDepth of 21 usually will return a
|
156
|
* solution in less than 0.5 seconds. With a maxDepth of 20 it takes a few seconds on average to find a
|
157
|
* solution, but it may take much longer for specific cubes.
|
158
|
*
|
159
|
*@param timeOut
|
160
|
* defines the maximum computing time of the method in seconds. If it does not return with a solution, it returns with
|
161
|
* an error code.
|
162
|
* @return The solution string or an error code:<br>
|
163
|
* Error 1: There is not exactly one facelet of each colour<br>
|
164
|
* Error 2: Not all 12 edges exist exactly once<br>
|
165
|
* Error 3: Flip error: One edge has to be flipped<br>
|
166
|
* Error 4: Not all corners exist exactly once<br>
|
167
|
* Error 5: Twist error: One corner has to be twisted<br>
|
168
|
* Error 6: Parity error: Two corners or two edges have to be exchanged<br>
|
169
|
* Error 7: No solution exists for the given maxDepth<br>
|
170
|
* Error 8: Timeout, no solution within given time
|
171
|
*/
|
172
|
public static String solution(String facelets, int maxDepth, long timeOut)
|
173
|
{
|
174
|
int s;
|
175
|
|
176
|
mInterrupted = false;
|
177
|
|
178
|
// +++++++++++++++++++++check for wrong input +++++++++++++++++++++++++++++
|
179
|
int[] count = new int[6];
|
180
|
try {
|
181
|
for (int i = 0; i < 54; i++)
|
182
|
count[Color.toInt(facelets.substring(i, i + 1))]++;
|
183
|
} catch (Exception e) {Log.d("error", "1");
|
184
|
return "Error 1";
|
185
|
}
|
186
|
for (int i = 0; i < 6; i++)
|
187
|
if (count[i] != 9) { Log.d("error", "2");
|
188
|
return "Error 1"; }
|
189
|
|
190
|
FaceCube fc = new FaceCube(facelets);
|
191
|
CubieCube cc = fc.toCubieCube();
|
192
|
if ((s = cc.verify()) != 0) { Log.d("error", "3");
|
193
|
return "Error " + Math.abs(s); }
|
194
|
|
195
|
// +++++++++++++++++++++++ initialization +++++++++++++++++++++++++++++++++
|
196
|
|
197
|
CoordCube c = new CoordCube(cc);
|
198
|
|
199
|
po[0] = 0;
|
200
|
ax[0] = 0;
|
201
|
flip[0] = c.flip;
|
202
|
twist[0] = c.twist;
|
203
|
parity[0] = c.parity;
|
204
|
slice[0] = c.FRtoBR / 24;
|
205
|
URFtoDLF[0] = c.URFtoDLF;
|
206
|
FRtoBR[0] = c.FRtoBR;
|
207
|
URtoUL[0] = c.URtoUL;
|
208
|
UBtoDF[0] = c.UBtoDF;
|
209
|
|
210
|
minDistPhase1[1] = 1;// else failure for depth=1, n=0
|
211
|
int mv = 0, n = 0;
|
212
|
boolean busy = false;
|
213
|
int depthPhase1 = 1;
|
214
|
|
215
|
long tStart = System.currentTimeMillis();
|
216
|
|
217
|
// +++++++++++++++++++ Main loop ++++++++++++++++++++++++++++++++++++++++++
|
218
|
do {
|
219
|
do {
|
220
|
if( mInterrupted ) return "Error 9";
|
221
|
|
222
|
if ((depthPhase1 - n > minDistPhase1[n + 1]) && !busy) {
|
223
|
|
224
|
if (ax[n] == 0 || ax[n] == 3)// Initialize next move
|
225
|
ax[++n] = 1;
|
226
|
else
|
227
|
ax[++n] = 0;
|
228
|
po[n] = 1;
|
229
|
} else if (++po[n] > 3) {
|
230
|
do {// increment axis
|
231
|
if (++ax[n] > 5) {
|
232
|
|
233
|
if (System.currentTimeMillis() - tStart > timeOut << 10)
|
234
|
return "Error 8";
|
235
|
|
236
|
if (n == 0) {
|
237
|
if (depthPhase1 >= maxDepth)
|
238
|
return "Error 7";
|
239
|
else {
|
240
|
depthPhase1++;
|
241
|
ax[n] = 0;
|
242
|
po[n] = 1;
|
243
|
busy = false;
|
244
|
break;
|
245
|
}
|
246
|
} else {
|
247
|
n--;
|
248
|
busy = true;
|
249
|
break;
|
250
|
}
|
251
|
|
252
|
} else {
|
253
|
po[n] = 1;
|
254
|
busy = false;
|
255
|
}
|
256
|
} while (n != 0 && (ax[n - 1] == ax[n] || ax[n - 1] - 3 == ax[n]));
|
257
|
} else
|
258
|
busy = false;
|
259
|
} while (busy);
|
260
|
|
261
|
// +++++++++++++ compute new coordinates and new minDistPhase1 ++++++++++
|
262
|
// if minDistPhase1 =0, the H subgroup is reached
|
263
|
mv = 3 * ax[n] + po[n] - 1;
|
264
|
flip[n + 1] = CoordCube.getFlipMove(flip[n],mv);
|
265
|
twist[n + 1] = CoordCube.getTwistMove(twist[n],mv);
|
266
|
slice[n + 1] = CoordCube.getFRtoBR_Move(slice[n] * 24,mv) / 24;
|
267
|
minDistPhase1[n + 1] = Math.max(CoordCube.getPruning(CoordCube.Slice_Flip_Prun, CoordCube.N_SLICE1 * flip[n + 1]
|
268
|
+ slice[n + 1]), CoordCube.getPruning(CoordCube.Slice_Twist_Prun, CoordCube.N_SLICE1 * twist[n + 1]
|
269
|
+ slice[n + 1]));
|
270
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
271
|
|
272
|
if (minDistPhase1[n + 1] == 0 && n >= depthPhase1 - 5) {
|
273
|
minDistPhase1[n + 1] = 10;// instead of 10 any value >5 is possible
|
274
|
if (n == depthPhase1 - 1 && (s = totalDepth(depthPhase1, maxDepth)) >= 0) {
|
275
|
if (s == depthPhase1 || (ax[depthPhase1 - 1] != ax[depthPhase1] && ax[depthPhase1 - 1] != ax[depthPhase1] + 3))
|
276
|
{
|
277
|
mNumMoves = s;
|
278
|
return solutionToString(s);
|
279
|
}
|
280
|
}
|
281
|
|
282
|
}
|
283
|
} while (true);
|
284
|
}
|
285
|
|
286
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
287
|
// Apply phase2 of algorithm and return the combined phase1 and phase2 depth. In phase2, only the moves
|
288
|
// U,D,R2,F2,L2 and B2 are allowed.
|
289
|
static int totalDepth(int depthPhase1, int maxDepth) {
|
290
|
int mv = 0, d1 = 0, d2 = 0;
|
291
|
int maxDepthPhase2 = Math.min(10, maxDepth - depthPhase1);// Allow only max 10 moves in phase2
|
292
|
for (int i = 0; i < depthPhase1; i++) {
|
293
|
mv = 3 * ax[i] + po[i] - 1;
|
294
|
URFtoDLF[i + 1] = CoordCube.getURFtoDLF_Move(URFtoDLF[i],mv);
|
295
|
FRtoBR[i + 1] = CoordCube.getFRtoBR_Move(FRtoBR[i],mv);
|
296
|
parity[i + 1] = CoordCube.parityMove[parity[i]][mv];
|
297
|
}
|
298
|
|
299
|
if ((d1 = CoordCube.getPruning(CoordCube.Slice_URFtoDLF_Parity_Prun,
|
300
|
(CoordCube.N_SLICE2 * URFtoDLF[depthPhase1] + FRtoBR[depthPhase1]) * 2 + parity[depthPhase1])) > maxDepthPhase2)
|
301
|
return -1;
|
302
|
|
303
|
for (int i = 0; i < depthPhase1; i++) {
|
304
|
mv = 3 * ax[i] + po[i] - 1;
|
305
|
URtoUL[i + 1] = CoordCube.getURtoUL_Move(URtoUL[i],mv);
|
306
|
UBtoDF[i + 1] = CoordCube.getUBtoDF_Move(UBtoDF[i],mv);
|
307
|
}
|
308
|
URtoDF[depthPhase1] = CoordCube.getMergeURtoULandUBtoDF(URtoUL[depthPhase1],UBtoDF[depthPhase1]);
|
309
|
|
310
|
if ((d2 = CoordCube.getPruning(CoordCube.Slice_URtoDF_Parity_Prun,
|
311
|
(CoordCube.N_SLICE2 * URtoDF[depthPhase1] + FRtoBR[depthPhase1]) * 2 + parity[depthPhase1])) > maxDepthPhase2)
|
312
|
return -1;
|
313
|
|
314
|
if ((minDistPhase2[depthPhase1] = Math.max(d1, d2)) == 0)// already solved
|
315
|
return depthPhase1;
|
316
|
|
317
|
// now set up search
|
318
|
|
319
|
int depthPhase2 = 1;
|
320
|
int n = depthPhase1;
|
321
|
boolean busy = false;
|
322
|
po[depthPhase1] = 0;
|
323
|
ax[depthPhase1] = 0;
|
324
|
minDistPhase2[n + 1] = 1;// else failure for depthPhase2=1, n=0
|
325
|
// +++++++++++++++++++ end initialization +++++++++++++++++++++++++++++++++
|
326
|
do {
|
327
|
do {
|
328
|
if ((depthPhase1 + depthPhase2 - n > minDistPhase2[n + 1]) && !busy) {
|
329
|
|
330
|
if (ax[n] == 0 || ax[n] == 3)// Initialize next move
|
331
|
{
|
332
|
ax[++n] = 1;
|
333
|
po[n] = 2;
|
334
|
} else {
|
335
|
ax[++n] = 0;
|
336
|
po[n] = 1;
|
337
|
}
|
338
|
} else if ((ax[n] == 0 || ax[n] == 3) ? (++po[n] > 3) : ((po[n] = po[n] + 2) > 3)) {
|
339
|
do {// increment axis
|
340
|
if (++ax[n] > 5) {
|
341
|
if (n == depthPhase1) {
|
342
|
if (depthPhase2 >= maxDepthPhase2)
|
343
|
return -1;
|
344
|
else {
|
345
|
depthPhase2++;
|
346
|
ax[n] = 0;
|
347
|
po[n] = 1;
|
348
|
busy = false;
|
349
|
break;
|
350
|
}
|
351
|
} else {
|
352
|
n--;
|
353
|
busy = true;
|
354
|
break;
|
355
|
}
|
356
|
|
357
|
} else {
|
358
|
if (ax[n] == 0 || ax[n] == 3)
|
359
|
po[n] = 1;
|
360
|
else
|
361
|
po[n] = 2;
|
362
|
busy = false;
|
363
|
}
|
364
|
} while (n != depthPhase1 && (ax[n - 1] == ax[n] || ax[n - 1] - 3 == ax[n]));
|
365
|
} else
|
366
|
busy = false;
|
367
|
} while (busy);
|
368
|
// +++++++++++++ compute new coordinates and new minDist ++++++++++
|
369
|
mv = 3 * ax[n] + po[n] - 1;
|
370
|
|
371
|
URFtoDLF[n + 1] = CoordCube.getURFtoDLF_Move(URFtoDLF[n],mv);
|
372
|
FRtoBR[n + 1] = CoordCube.getFRtoBR_Move(FRtoBR[n],mv);
|
373
|
parity[n + 1] = CoordCube.parityMove[parity[n]][mv];
|
374
|
URtoDF[n + 1] = CoordCube.getURtoDF_Move(URtoDF[n],mv);
|
375
|
|
376
|
minDistPhase2[n + 1] = Math.max(CoordCube.getPruning(CoordCube.Slice_URtoDF_Parity_Prun, (CoordCube.N_SLICE2
|
377
|
* URtoDF[n + 1] + FRtoBR[n + 1])
|
378
|
* 2 + parity[n + 1]), CoordCube.getPruning(CoordCube.Slice_URFtoDLF_Parity_Prun, (CoordCube.N_SLICE2
|
379
|
* URFtoDLF[n + 1] + FRtoBR[n + 1])
|
380
|
* 2 + parity[n + 1]));
|
381
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
382
|
|
383
|
} while (minDistPhase2[n + 1] != 0);
|
384
|
return depthPhase1 + depthPhase2;
|
385
|
}
|
386
|
}
|