1 |
b95ceafc
|
Leszek Koltunski
|
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+=" 363"; break;
|
51 |
|
|
case 2: s+=" 364"; break;
|
52 |
|
|
case 3: s+=" 361"; break;
|
53 |
|
|
}
|
54 |
|
|
break;
|
55 |
|
|
case 1: switch(po[i])
|
56 |
|
|
{
|
57 |
|
|
case 1: s+=" 043"; break;
|
58 |
|
|
case 2: s+=" 044"; break;
|
59 |
|
|
case 3: s+=" 041"; break;
|
60 |
|
|
}
|
61 |
|
|
break;
|
62 |
|
|
case 2: switch(po[i])
|
63 |
|
|
{
|
64 |
|
|
case 1: s+=" 683"; break;
|
65 |
|
|
case 2: s+=" 684"; break;
|
66 |
|
|
case 3: s+=" 681"; break;
|
67 |
|
|
}
|
68 |
|
|
break;
|
69 |
|
|
case 3: switch(po[i])
|
70 |
|
|
{
|
71 |
|
|
case 1: s+=" 331"; break;
|
72 |
|
|
case 2: s+=" 330"; break;
|
73 |
|
|
case 3: s+=" 333"; break;
|
74 |
|
|
}
|
75 |
|
|
break;
|
76 |
|
|
case 4: switch(po[i])
|
77 |
|
|
{
|
78 |
|
|
case 1: s+=" 011"; break;
|
79 |
|
|
case 2: s+=" 010"; break;
|
80 |
|
|
case 3: s+=" 013"; break;
|
81 |
|
|
}
|
82 |
|
|
break;
|
83 |
|
|
case 5: switch(po[i])
|
84 |
|
|
{
|
85 |
|
|
case 1: s+=" 651"; break;
|
86 |
|
|
case 2: s+=" 650"; break;
|
87 |
|
|
case 3: s+=" 653"; 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 |
|
|
*
|
163 |
|
|
* @param useSeparator
|
164 |
|
|
* determines if a " . " separates the phase1 and phase2 parts of the solver string like in F' R B R L2 F .
|
165 |
|
|
* U2 U D for example.<br>
|
166 |
|
|
* @return The solution string or an error code:<br>
|
167 |
|
|
* Error 1: There is not exactly one facelet of each colour<br>
|
168 |
|
|
* Error 2: Not all 12 edges exist exactly once<br>
|
169 |
|
|
* Error 3: Flip error: One edge has to be flipped<br>
|
170 |
|
|
* Error 4: Not all corners exist exactly once<br>
|
171 |
|
|
* Error 5: Twist error: One corner has to be twisted<br>
|
172 |
|
|
* Error 6: Parity error: Two corners or two edges have to be exchanged<br>
|
173 |
|
|
* Error 7: No solution exists for the given maxDepth<br>
|
174 |
|
|
* Error 8: Timeout, no solution within given time
|
175 |
|
|
*/
|
176 |
|
|
public static String solution(String facelets, int maxDepth, long timeOut)
|
177 |
|
|
{
|
178 |
|
|
int s;
|
179 |
|
|
|
180 |
|
|
Log.d("solution", facelets);
|
181 |
|
|
|
182 |
|
|
mInterrupted = false;
|
183 |
|
|
|
184 |
|
|
// +++++++++++++++++++++check for wrong input +++++++++++++++++++++++++++++
|
185 |
|
|
int[] count = new int[6];
|
186 |
|
|
try {
|
187 |
|
|
for (int i = 0; i < 54; i++)
|
188 |
|
|
count[Color.toInt(facelets.substring(i, i + 1))]++;
|
189 |
|
|
} catch (Exception e) {Log.d("error", "1");
|
190 |
|
|
return "Error 1";
|
191 |
|
|
}
|
192 |
|
|
for (int i = 0; i < 6; i++)
|
193 |
|
|
if (count[i] != 9) { Log.d("error", "2");
|
194 |
|
|
return "Error 1"; }
|
195 |
|
|
|
196 |
|
|
FaceCube fc = new FaceCube(facelets);
|
197 |
|
|
CubieCube cc = fc.toCubieCube();
|
198 |
|
|
if ((s = cc.verify()) != 0) { Log.d("error", "3");
|
199 |
|
|
return "Error " + Math.abs(s); }
|
200 |
|
|
|
201 |
|
|
// +++++++++++++++++++++++ initialization +++++++++++++++++++++++++++++++++
|
202 |
|
|
|
203 |
|
|
CoordCube c = new CoordCube(cc);
|
204 |
|
|
|
205 |
|
|
po[0] = 0;
|
206 |
|
|
ax[0] = 0;
|
207 |
|
|
flip[0] = c.flip;
|
208 |
|
|
twist[0] = c.twist;
|
209 |
|
|
parity[0] = c.parity;
|
210 |
|
|
slice[0] = c.FRtoBR / 24;
|
211 |
|
|
URFtoDLF[0] = c.URFtoDLF;
|
212 |
|
|
FRtoBR[0] = c.FRtoBR;
|
213 |
|
|
URtoUL[0] = c.URtoUL;
|
214 |
|
|
UBtoDF[0] = c.UBtoDF;
|
215 |
|
|
|
216 |
|
|
minDistPhase1[1] = 1;// else failure for depth=1, n=0
|
217 |
|
|
int mv = 0, n = 0;
|
218 |
|
|
boolean busy = false;
|
219 |
|
|
int depthPhase1 = 1;
|
220 |
|
|
|
221 |
|
|
long tStart = System.currentTimeMillis();
|
222 |
|
|
|
223 |
|
|
// +++++++++++++++++++ Main loop ++++++++++++++++++++++++++++++++++++++++++
|
224 |
|
|
do {
|
225 |
|
|
do {
|
226 |
|
|
if( mInterrupted ) return "Error 9";
|
227 |
|
|
|
228 |
|
|
if ((depthPhase1 - n > minDistPhase1[n + 1]) && !busy) {
|
229 |
|
|
|
230 |
|
|
if (ax[n] == 0 || ax[n] == 3)// Initialize next move
|
231 |
|
|
ax[++n] = 1;
|
232 |
|
|
else
|
233 |
|
|
ax[++n] = 0;
|
234 |
|
|
po[n] = 1;
|
235 |
|
|
} else if (++po[n] > 3) {
|
236 |
|
|
do {// increment axis
|
237 |
|
|
if (++ax[n] > 5) {
|
238 |
|
|
|
239 |
|
|
if (System.currentTimeMillis() - tStart > timeOut << 10)
|
240 |
|
|
return "Error 8";
|
241 |
|
|
|
242 |
|
|
if (n == 0) {
|
243 |
|
|
if (depthPhase1 >= maxDepth)
|
244 |
|
|
return "Error 7";
|
245 |
|
|
else {
|
246 |
|
|
depthPhase1++;
|
247 |
|
|
ax[n] = 0;
|
248 |
|
|
po[n] = 1;
|
249 |
|
|
busy = false;
|
250 |
|
|
break;
|
251 |
|
|
}
|
252 |
|
|
} else {
|
253 |
|
|
n--;
|
254 |
|
|
busy = true;
|
255 |
|
|
break;
|
256 |
|
|
}
|
257 |
|
|
|
258 |
|
|
} else {
|
259 |
|
|
po[n] = 1;
|
260 |
|
|
busy = false;
|
261 |
|
|
}
|
262 |
|
|
} while (n != 0 && (ax[n - 1] == ax[n] || ax[n - 1] - 3 == ax[n]));
|
263 |
|
|
} else
|
264 |
|
|
busy = false;
|
265 |
|
|
} while (busy);
|
266 |
|
|
|
267 |
|
|
// +++++++++++++ compute new coordinates and new minDistPhase1 ++++++++++
|
268 |
|
|
// if minDistPhase1 =0, the H subgroup is reached
|
269 |
|
|
mv = 3 * ax[n] + po[n] - 1;
|
270 |
|
|
flip[n + 1] = CoordCube.getFlipMove(flip[n],mv);
|
271 |
|
|
twist[n + 1] = CoordCube.getTwistMove(twist[n],mv);
|
272 |
|
|
slice[n + 1] = CoordCube.getFRtoBR_Move(slice[n] * 24,mv) / 24;
|
273 |
|
|
minDistPhase1[n + 1] = Math.max(CoordCube.getPruning(CoordCube.Slice_Flip_Prun, CoordCube.N_SLICE1 * flip[n + 1]
|
274 |
|
|
+ slice[n + 1]), CoordCube.getPruning(CoordCube.Slice_Twist_Prun, CoordCube.N_SLICE1 * twist[n + 1]
|
275 |
|
|
+ slice[n + 1]));
|
276 |
|
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
277 |
|
|
|
278 |
|
|
if (minDistPhase1[n + 1] == 0 && n >= depthPhase1 - 5) {
|
279 |
|
|
minDistPhase1[n + 1] = 10;// instead of 10 any value >5 is possible
|
280 |
|
|
if (n == depthPhase1 - 1 && (s = totalDepth(depthPhase1, maxDepth)) >= 0) {
|
281 |
|
|
if (s == depthPhase1 || (ax[depthPhase1 - 1] != ax[depthPhase1] && ax[depthPhase1 - 1] != ax[depthPhase1] + 3))
|
282 |
|
|
{
|
283 |
|
|
mNumMoves = s;
|
284 |
|
|
return solutionToString(s);
|
285 |
|
|
}
|
286 |
|
|
}
|
287 |
|
|
|
288 |
|
|
}
|
289 |
|
|
} while (true);
|
290 |
|
|
}
|
291 |
|
|
|
292 |
|
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
293 |
|
|
// Apply phase2 of algorithm and return the combined phase1 and phase2 depth. In phase2, only the moves
|
294 |
|
|
// U,D,R2,F2,L2 and B2 are allowed.
|
295 |
|
|
static int totalDepth(int depthPhase1, int maxDepth) {
|
296 |
|
|
int mv = 0, d1 = 0, d2 = 0;
|
297 |
|
|
int maxDepthPhase2 = Math.min(10, maxDepth - depthPhase1);// Allow only max 10 moves in phase2
|
298 |
|
|
for (int i = 0; i < depthPhase1; i++) {
|
299 |
|
|
mv = 3 * ax[i] + po[i] - 1;
|
300 |
|
|
URFtoDLF[i + 1] = CoordCube.getURFtoDLF_Move(URFtoDLF[i],mv);
|
301 |
|
|
FRtoBR[i + 1] = CoordCube.getFRtoBR_Move(FRtoBR[i],mv);
|
302 |
|
|
parity[i + 1] = CoordCube.parityMove[parity[i]][mv];
|
303 |
|
|
}
|
304 |
|
|
|
305 |
|
|
if ((d1 = CoordCube.getPruning(CoordCube.Slice_URFtoDLF_Parity_Prun,
|
306 |
|
|
(CoordCube.N_SLICE2 * URFtoDLF[depthPhase1] + FRtoBR[depthPhase1]) * 2 + parity[depthPhase1])) > maxDepthPhase2)
|
307 |
|
|
return -1;
|
308 |
|
|
|
309 |
|
|
for (int i = 0; i < depthPhase1; i++) {
|
310 |
|
|
mv = 3 * ax[i] + po[i] - 1;
|
311 |
|
|
URtoUL[i + 1] = CoordCube.getURtoUL_Move(URtoUL[i],mv);
|
312 |
|
|
UBtoDF[i + 1] = CoordCube.getUBtoDF_Move(UBtoDF[i],mv);
|
313 |
|
|
}
|
314 |
|
|
URtoDF[depthPhase1] = CoordCube.getMergeURtoULandUBtoDF(URtoUL[depthPhase1],UBtoDF[depthPhase1]);
|
315 |
|
|
|
316 |
|
|
if ((d2 = CoordCube.getPruning(CoordCube.Slice_URtoDF_Parity_Prun,
|
317 |
|
|
(CoordCube.N_SLICE2 * URtoDF[depthPhase1] + FRtoBR[depthPhase1]) * 2 + parity[depthPhase1])) > maxDepthPhase2)
|
318 |
|
|
return -1;
|
319 |
|
|
|
320 |
|
|
if ((minDistPhase2[depthPhase1] = Math.max(d1, d2)) == 0)// already solved
|
321 |
|
|
return depthPhase1;
|
322 |
|
|
|
323 |
|
|
// now set up search
|
324 |
|
|
|
325 |
|
|
int depthPhase2 = 1;
|
326 |
|
|
int n = depthPhase1;
|
327 |
|
|
boolean busy = false;
|
328 |
|
|
po[depthPhase1] = 0;
|
329 |
|
|
ax[depthPhase1] = 0;
|
330 |
|
|
minDistPhase2[n + 1] = 1;// else failure for depthPhase2=1, n=0
|
331 |
|
|
// +++++++++++++++++++ end initialization +++++++++++++++++++++++++++++++++
|
332 |
|
|
do {
|
333 |
|
|
do {
|
334 |
|
|
if ((depthPhase1 + depthPhase2 - n > minDistPhase2[n + 1]) && !busy) {
|
335 |
|
|
|
336 |
|
|
if (ax[n] == 0 || ax[n] == 3)// Initialize next move
|
337 |
|
|
{
|
338 |
|
|
ax[++n] = 1;
|
339 |
|
|
po[n] = 2;
|
340 |
|
|
} else {
|
341 |
|
|
ax[++n] = 0;
|
342 |
|
|
po[n] = 1;
|
343 |
|
|
}
|
344 |
|
|
} else if ((ax[n] == 0 || ax[n] == 3) ? (++po[n] > 3) : ((po[n] = po[n] + 2) > 3)) {
|
345 |
|
|
do {// increment axis
|
346 |
|
|
if (++ax[n] > 5) {
|
347 |
|
|
if (n == depthPhase1) {
|
348 |
|
|
if (depthPhase2 >= maxDepthPhase2)
|
349 |
|
|
return -1;
|
350 |
|
|
else {
|
351 |
|
|
depthPhase2++;
|
352 |
|
|
ax[n] = 0;
|
353 |
|
|
po[n] = 1;
|
354 |
|
|
busy = false;
|
355 |
|
|
break;
|
356 |
|
|
}
|
357 |
|
|
} else {
|
358 |
|
|
n--;
|
359 |
|
|
busy = true;
|
360 |
|
|
break;
|
361 |
|
|
}
|
362 |
|
|
|
363 |
|
|
} else {
|
364 |
|
|
if (ax[n] == 0 || ax[n] == 3)
|
365 |
|
|
po[n] = 1;
|
366 |
|
|
else
|
367 |
|
|
po[n] = 2;
|
368 |
|
|
busy = false;
|
369 |
|
|
}
|
370 |
|
|
} while (n != depthPhase1 && (ax[n - 1] == ax[n] || ax[n - 1] - 3 == ax[n]));
|
371 |
|
|
} else
|
372 |
|
|
busy = false;
|
373 |
|
|
} while (busy);
|
374 |
|
|
// +++++++++++++ compute new coordinates and new minDist ++++++++++
|
375 |
|
|
mv = 3 * ax[n] + po[n] - 1;
|
376 |
|
|
|
377 |
|
|
URFtoDLF[n + 1] = CoordCube.getURFtoDLF_Move(URFtoDLF[n],mv);
|
378 |
|
|
FRtoBR[n + 1] = CoordCube.getFRtoBR_Move(FRtoBR[n],mv);
|
379 |
|
|
parity[n + 1] = CoordCube.parityMove[parity[n]][mv];
|
380 |
|
|
URtoDF[n + 1] = CoordCube.getURtoDF_Move(URtoDF[n],mv);
|
381 |
|
|
|
382 |
|
|
minDistPhase2[n + 1] = Math.max(CoordCube.getPruning(CoordCube.Slice_URtoDF_Parity_Prun, (CoordCube.N_SLICE2
|
383 |
|
|
* URtoDF[n + 1] + FRtoBR[n + 1])
|
384 |
|
|
* 2 + parity[n + 1]), CoordCube.getPruning(CoordCube.Slice_URFtoDLF_Parity_Prun, (CoordCube.N_SLICE2
|
385 |
|
|
* URFtoDLF[n + 1] + FRtoBR[n + 1])
|
386 |
|
|
* 2 + parity[n + 1]));
|
387 |
|
|
// ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
|
388 |
|
|
|
389 |
|
|
} while (minDistPhase2[n + 1] != 0);
|
390 |
|
|
return depthPhase1 + depthPhase2;
|
391 |
|
|
}
|
392 |
|
|
}
|