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