|
1
|
/*
|
|
2
|
* Herbert Kociemba
|
|
3
|
*
|
|
4
|
* BSD-licensed. See https://opensource.org/licenses/BSD-3-Clause
|
|
5
|
*/
|
|
6
|
|
|
7
|
package org.distorted.objectlib.kociemba;
|
|
8
|
|
|
9
|
import org.distorted.objectlib.helpers.OperatingSystemInterface;
|
|
10
|
|
|
11
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
|
12
|
|
|
13
|
public class SolverSearch
|
|
14
|
{
|
|
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(OperatingSystemInterface os)
|
|
94
|
{
|
|
95
|
SolverCoordCube.initialize(os,0);
|
|
96
|
SolverCoordCube.initialize(os,1);
|
|
97
|
SolverCoordCube.initialize(os,2);
|
|
98
|
SolverCoordCube.initialize(os,3);
|
|
99
|
SolverCoordCube.initialize(os,4);
|
|
100
|
SolverCoordCube.initialize(os,5);
|
|
101
|
SolverCoordCube.initialize(os,6);
|
|
102
|
SolverCoordCube.initialize(os,7);
|
|
103
|
SolverCoordCube.initialize(os,8);
|
|
104
|
SolverCoordCube.initialize(os,9);
|
|
105
|
SolverCoordCube.initialize(os,10);
|
|
106
|
SolverCoordCube.initialize(os,11);
|
|
107
|
}
|
|
108
|
|
|
109
|
///////////////////////////////////////////////////////////////////////////////////////////////////
|
|
110
|
/**
|
|
111
|
* Computes the solver string for a given cube.
|
|
112
|
*
|
|
113
|
* @param facelets
|
|
114
|
* is the cube definition string, see {@link SolverFacelet} for the format.
|
|
115
|
*
|
|
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
|
count[SolverColor.toInt(facelets.substring(i,i+1))]++;
|
|
144
|
}
|
|
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
|
SolverFaceCube fc = new SolverFaceCube(facelets);
|
|
159
|
SolverCubieCube cc = fc.toCubieCube();
|
|
160
|
if ((s = cc.verify()) != 0)
|
|
161
|
{
|
|
162
|
android.util.Log.d("error", "3");
|
|
163
|
return "Error " + Math.abs(s);
|
|
164
|
}
|
|
165
|
|
|
166
|
SolverCoordCube c = new SolverCoordCube(cc);
|
|
167
|
|
|
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
|
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
|
+ 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
|
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
|
}
|
|
280
|
|
|
281
|
if( (d1 = SolverCoordCube.getPruning(SolverCoordCube.Slice_URFtoDLF_Parity_Prun,
|
|
282
|
(SolverCoordCube.N_SLICE2 * URFtoDLF[depthPhase1] + FRtoBR[depthPhase1]) * 2 + parity[depthPhase1])) > maxDepthPhase2)
|
|
283
|
return -1;
|
|
284
|
|
|
285
|
for( int i=0; i<depthPhase1; i++)
|
|
286
|
{
|
|
287
|
mv = 3 * ax[i] + po[i] - 1;
|
|
288
|
URtoUL[i + 1] = SolverCoordCube.getURtoUL_Move(URtoUL[i],mv);
|
|
289
|
UBtoDF[i + 1] = SolverCoordCube.getUBtoDF_Move(UBtoDF[i],mv);
|
|
290
|
}
|
|
291
|
|
|
292
|
URtoDF[depthPhase1] = SolverCoordCube.getMergeURtoULandUBtoDF(URtoUL[depthPhase1],UBtoDF[depthPhase1]);
|
|
293
|
|
|
294
|
if ((d2 = SolverCoordCube.getPruning(SolverCoordCube.Slice_URtoDF_Parity_Prun,
|
|
295
|
(SolverCoordCube.N_SLICE2 * URtoDF[depthPhase1] + FRtoBR[depthPhase1]) * 2 + parity[depthPhase1])) > maxDepthPhase2)
|
|
296
|
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
|
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
|
|
|
377
|
minDistPhase2[n+1] = Math.max(SolverCoordCube.getPruning(SolverCoordCube.Slice_URtoDF_Parity_Prun, (SolverCoordCube.N_SLICE2
|
|
378
|
* URtoDF[n+1] + FRtoBR[n+1])
|
|
379
|
* 2 + parity[n+1]), SolverCoordCube.getPruning(SolverCoordCube.Slice_URFtoDLF_Parity_Prun, (SolverCoordCube.N_SLICE2
|
|
380
|
* 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
|
}
|