Revision 14cf0761
Added by Leszek Koltunski almost 2 years ago
src/main/java/org/distorted/solvers/SolverSkewb.java | ||
---|---|---|
43 | 43 |
private static final int ERROR_TWO_CENTERS = -17; |
44 | 44 |
private static final int ERROR_TWO_CORNERS = -18; |
45 | 45 |
|
46 |
private static final int ERROR_IMPOSSIBLE = -19; |
|
47 |
|
|
48 | 46 |
private TablebasesAbstract mSolver; |
49 | 47 |
private final int[] mFaceColors; |
50 | 48 |
|
... | ... | |
169 | 167 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
170 | 168 |
// free corners: 1,2,4,7 |
171 | 169 |
|
172 |
private int retCornerPermutation(int[] perm, int[][] corners) |
|
170 |
private int retFreeCornerPermutation(int[] perm, int[][] corners)
|
|
173 | 171 |
{ |
174 | 172 |
int[] map = {1,2,4,7}; |
175 | 173 |
|
176 |
perm[0] = 0;
|
|
174 |
perm[0] = -1;
|
|
177 | 175 |
perm[1] = -1; |
178 | 176 |
perm[2] = -1; |
179 |
perm[3] = 3; |
|
180 |
perm[4] = -1; |
|
181 |
perm[5] = 5; |
|
182 |
perm[6] = 6; |
|
183 |
perm[7] = -1; |
|
177 |
perm[3] = -1; |
|
184 | 178 |
|
185 | 179 |
for(int i=0; i<4; i++) |
186 | 180 |
{ |
187 |
int index = map[i]; |
|
188 |
int[] cor = corners[index]; |
|
181 |
int[] cor = corners[map[i]]; |
|
189 | 182 |
|
190 |
if( cornerIs(cor,2,5,0) ) perm[1] = index;
|
|
191 |
if( cornerIs(cor,3,4,0) ) perm[2] = index;
|
|
192 |
if( cornerIs(cor,1,2,4) ) perm[4] = index;
|
|
193 |
if( cornerIs(cor,1,3,5) ) perm[7] = index;
|
|
183 |
if( cornerIs(cor,2,5,0) ) perm[0] = i;
|
|
184 |
if( cornerIs(cor,3,4,0) ) perm[1] = i;
|
|
185 |
if( cornerIs(cor,1,2,4) ) perm[2] = i;
|
|
186 |
if( cornerIs(cor,1,3,5) ) perm[3] = i;
|
|
194 | 187 |
} |
195 | 188 |
|
196 |
if( perm[1]==-1 ) return ERROR_CORNER_025_MISSING;
|
|
197 |
if( perm[2]==-1 ) return ERROR_CORNER_034_MISSING;
|
|
198 |
if( perm[4]==-1 ) return ERROR_CORNER_124_MISSING;
|
|
199 |
if( perm[7]==-1 ) return ERROR_CORNER_135_MISSING;
|
|
189 |
if( perm[0]==-1 ) return ERROR_CORNER_025_MISSING;
|
|
190 |
if( perm[1]==-1 ) return ERROR_CORNER_034_MISSING;
|
|
191 |
if( perm[2]==-1 ) return ERROR_CORNER_124_MISSING;
|
|
192 |
if( perm[3]==-1 ) return ERROR_CORNER_135_MISSING;
|
|
200 | 193 |
|
201 | 194 |
return 0; |
202 | 195 |
} |
203 | 196 |
|
204 | 197 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
205 | 198 |
|
206 |
private void fillCornerTwists(int[] output, int[][] corners, int[] perm) |
|
207 |
{ |
|
208 |
final int[] map = { 4,2,3,5,1,5,4,1 }; |
|
199 |
// [1][] are the 3 quats the 1st 'fixed' corner will have when 'fakeTwisted' (which in case of |
|
200 |
// the fixed corners is the same as the final twist) with respectively twist 0,1,2. |
|
209 | 201 |
|
210 |
for(int i=0; i<8; i++) |
|
211 |
{ |
|
212 |
int color = mFaceColors[map[i]]; |
|
213 |
int[] c = corners[perm[i]]; |
|
202 |
private final int[][] fixedQuats = { {0,1,2},{0,7,8},{0,6,5},{0,4,3} }; |
|
214 | 203 |
|
215 |
if( c[0]==color ) output[i] = 0; |
|
216 |
else if( c[1]==color ) output[i] = 1; |
|
217 |
else output[i] = 2; |
|
218 |
} |
|
204 |
// [1][2][] are the 3 quats the 1st free corner, when permuted to the location of the 2nd corner, |
|
205 |
// will have when it is 'fakeTwisted' with fakeTwist 0,1,2. |
|
206 |
// fakeTwist is an intermediate twist which needs yet to be translated to the final twist of the |
|
207 |
// corners (which needs to sum up to something divisible by 3). |
|
208 |
|
|
209 |
private final int[][][] freeQuats= |
|
210 |
{ |
|
211 |
{ {0,3,4},{9,8,1},{6,11,2},{7,10,5} }, |
|
212 |
{ {9,2,7},{0,5,6},{1,10,3},{4,11,8} }, |
|
213 |
{ {5,1,11},{2,4,10},{0,8,7},{9,3,6} }, |
|
214 |
{ {8,6,10},{3,7,11},{9,5,4},{0,2,1} } |
|
215 |
}; |
|
216 |
|
|
217 |
private void fillInQuats(int[] output, int[] perm, int[] twist) |
|
218 |
{ |
|
219 |
output[0] = fixedQuats[0][twist[0]]; |
|
220 |
output[1] = freeQuats[0][perm[0]][twist[1]]; |
|
221 |
output[2] = freeQuats[1][perm[1]][twist[2]]; |
|
222 |
output[3] = fixedQuats[1][twist[3]]; |
|
223 |
output[4] = freeQuats[2][perm[2]][twist[3]]; |
|
224 |
output[5] = fixedQuats[2][twist[5]]; |
|
225 |
output[6] = fixedQuats[3][twist[6]]; |
|
226 |
output[7] = freeQuats[3][perm[3]][twist[7]]; |
|
219 | 227 |
} |
220 | 228 |
|
221 | 229 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
222 | 230 |
|
223 |
private int computeCenterTwist(int p1, int p2)
|
|
231 |
private int computeLocation(int quat)
|
|
224 | 232 |
{ |
225 |
if( p1==1 ) |
|
226 |
{ |
|
227 |
switch(p2) |
|
228 |
{ |
|
229 |
case 2: return 2; |
|
230 |
case 4: return 1; |
|
231 |
case 7: return 0; |
|
232 |
} |
|
233 |
} |
|
234 |
if( p1==2 ) |
|
235 |
{ |
|
236 |
switch(p2) |
|
237 |
{ |
|
238 |
case 1: return 2; |
|
239 |
case 4: return 0; |
|
240 |
case 7: return 1; |
|
241 |
} |
|
242 |
} |
|
243 |
if( p1==4 ) |
|
233 |
for(int i=0; i<4; i++) |
|
244 | 234 |
{ |
245 |
switch(p2) |
|
246 |
{ |
|
247 |
case 1: return 1; |
|
248 |
case 2: return 0; |
|
249 |
case 7: return 2; |
|
250 |
} |
|
235 |
int[] q = freeQuats[0][i]; |
|
236 |
if( quat==q[0] || quat==q[1] || quat==q[2] ) return i; |
|
251 | 237 |
} |
252 |
if( p1==7 ) |
|
238 |
|
|
239 |
android.util.Log.e("D", "error in computeLocation, quat="+quat); |
|
240 |
return -1; |
|
241 |
} |
|
242 |
|
|
243 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
244 |
|
|
245 |
private int retFixed(int index, int quat) |
|
246 |
{ |
|
247 |
int[] qs = fixedQuats[index]; |
|
248 |
|
|
249 |
if( quat==qs[0]) return 0; |
|
250 |
if( quat==qs[1]) return 1; |
|
251 |
if( quat==qs[2]) return 2; |
|
252 |
|
|
253 |
android.util.Log.e("D", "error in retFixed, index="+index+" quat="+quat); |
|
254 |
return -1; |
|
255 |
} |
|
256 |
|
|
257 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
258 |
|
|
259 |
private int retFree(int index, int quat) |
|
260 |
{ |
|
261 |
int[][] qs = freeQuats[index]; |
|
262 |
|
|
263 |
for(int i=0; i<4; i++) |
|
253 | 264 |
{ |
254 |
switch(p2) |
|
255 |
{ |
|
256 |
case 1: return 0; |
|
257 |
case 2: return 1; |
|
258 |
case 4: return 2; |
|
259 |
} |
|
265 |
if( quat==qs[i][0]) return 0; |
|
266 |
if( quat==qs[i][1]) return 1; |
|
267 |
if( quat==qs[i][2]) return 2; |
|
260 | 268 |
} |
261 | 269 |
|
262 |
return ERROR_IMPOSSIBLE; |
|
270 |
android.util.Log.e("D", "error in retFree, index="+index+" quat="+quat); |
|
271 |
return -1; |
|
263 | 272 |
} |
264 | 273 |
|
265 | 274 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
266 |
|
|
267 |
private int positionOfFirstCorner(int[] perm, int[] twist) |
|
275 |
// In case of the four 'fixed' corners (0,3,5,6) which do not change their location, |
|
276 |
// the twist is natural: 0 in the init positions and increasing 1 mod 3 on each CW turn. |
|
277 |
// |
|
278 |
// In case of the four 'free' corners their twist is relative to the position of the 'free' |
|
279 |
// tetrahedron. And so, for example the twist of free corner 1 (whose 0th face is orange) is equal |
|
280 |
// to 0 if free corner 7 is on the same face like 0th face of corner 1 (which is the case in init |
|
281 |
// position); then once free corners 2,4,7 permute CW, twist of corner 1 increases by 1 mod 3. |
|
282 |
|
|
283 |
private void computeCornerTwists(int[] twists, int[] quats) |
|
268 | 284 |
{ |
269 |
int total_fixed_twist = twist[0]+twist[3]+twist[5]+twist[6]; |
|
285 |
twists[0] = retFixed(0,quats[0]); |
|
286 |
twists[3] = retFixed(1,quats[3]); |
|
287 |
twists[5] = retFixed(2,quats[5]); |
|
288 |
twists[6] = retFixed(3,quats[6]); |
|
289 |
|
|
290 |
twists[1] = retFree(0,quats[1]); |
|
291 |
twists[2] = retFree(1,quats[2]); |
|
292 |
twists[4] = retFree(2,quats[4]); |
|
293 |
twists[7] = retFree(3,quats[7]); |
|
294 |
} |
|
270 | 295 |
|
271 |
int twist_42 = computeCenterTwist(perm[4],perm[2]); |
|
272 |
int twist_21 = computeCenterTwist(perm[2],perm[1]); |
|
296 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
273 | 297 |
|
274 |
if( twist_42<0 || twist_21<0 ) return ERROR_IMPOSSIBLE; |
|
298 |
private int retCornerPerm(int index, int[] perm) |
|
299 |
{ |
|
300 |
int[] free = {1,2,4,7}; |
|
275 | 301 |
|
302 |
switch(index) |
|
303 |
{ |
|
304 |
case 0: return 0; |
|
305 |
case 1: return free[perm[0]]; |
|
306 |
case 2: return free[perm[1]]; |
|
307 |
case 3: return 3; |
|
308 |
case 4: return free[perm[2]]; |
|
309 |
case 5: return 5; |
|
310 |
case 6: return 6; |
|
311 |
case 7: return free[perm[3]]; |
|
312 |
} |
|
276 | 313 |
|
277 |
android.util.Log.e("D", "twist42 "+twist_42+" twist21 "+twist_21+" total: "+total_fixed_twist); |
|
314 |
return -1; |
|
315 |
} |
|
316 |
|
|
317 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
|
278 | 318 |
|
279 |
if( (twist_21-twist_42+1)%3 != 0 ) return ERROR_TWO_CORNERS; |
|
280 |
if( (total_fixed_twist-twist_42)%3 !=0 ) return ERROR_CORNER_TWISTED; |
|
319 |
private void computeCornerQuats(int[] quats, int[][] corners, int[] perm) |
|
320 |
{ |
|
321 |
final int[] map = { 4,2,3,5,1,5,4,1 }; |
|
322 |
int[] twists = new int[8]; |
|
281 | 323 |
|
282 |
switch(perm[1])
|
|
324 |
for(int i=0; i<8; i++)
|
|
283 | 325 |
{ |
284 |
case 1: return 0; |
|
285 |
case 2: return 1; |
|
286 |
case 4: return 2; |
|
287 |
case 7: return 3; |
|
326 |
int color = mFaceColors[map[i]]; |
|
327 |
int[] c = corners[retCornerPerm(i,perm)]; |
|
328 |
|
|
329 |
if( c[0]==color ) twists[i] = 0; |
|
330 |
else if( c[1]==color ) twists[i] = 1; |
|
331 |
else twists[i] = 2; |
|
288 | 332 |
} |
289 | 333 |
|
290 |
return ERROR_IMPOSSIBLE;
|
|
334 |
fillInQuats(quats,perm,twists);
|
|
291 | 335 |
} |
292 | 336 |
|
293 | 337 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
... | ... | |
297 | 341 |
int[][] corners= new int[8][3]; |
298 | 342 |
int[] centers = new int[6]; |
299 | 343 |
int[] twist = new int[8]; |
300 |
int[] perm = new int[8]; |
|
344 |
int[] freePerm = new int[4]; |
|
345 |
int[] quats = new int[8]; |
|
301 | 346 |
|
302 | 347 |
getCorners(object,corners); |
303 | 348 |
|
... | ... | |
320 | 365 |
if( !TablebaseHelpers.permutationIsEven(centers) ) return ERROR_TWO_CENTERS; |
321 | 366 |
int center_perm_num = TablebaseHelpers.computeEvenPermutationNum(centers); |
322 | 367 |
|
323 |
int result4 = retCornerPermutation(perm,corners);
|
|
368 |
int result4 = retFreeCornerPermutation(freePerm,corners);
|
|
324 | 369 |
if( result4<0 ) return result4; |
325 | 370 |
|
326 |
fillCornerTwists(twist,corners,perm); |
|
327 |
|
|
328 |
for(int i=0; i<8; i++) android.util.Log.e("D", "perm "+i+" : "+perm[i]); |
|
371 |
computeCornerQuats(quats,corners,freePerm); |
|
372 |
computeCornerTwists(twist,quats); |
|
373 |
/* |
|
374 |
for(int i=0; i<4; i++) android.util.Log.e("D", "perm "+i+" : "+freePerm[i]); |
|
375 |
for(int i=0; i<8; i++) android.util.Log.e("D", "quat "+i+" : "+quats[i]); |
|
329 | 376 |
for(int i=0; i<8; i++) android.util.Log.e("D", "twist "+i+" : "+twist[i]); |
377 |
*/ |
|
378 |
int total = twist[1]+twist[2]+twist[4]+twist[7]; |
|
379 |
if( (total%3)!=0 ) return ERROR_CORNER_TWISTED; |
|
380 |
int totalTwist = twist[0]+ 3*(twist[1]+ 3*(twist[2]+ 3*(twist[3]+ 3*(twist[4]+ 3*(twist[5]+ 3*twist[6]))))); |
|
330 | 381 |
|
331 |
int totalTwist = 0; |
|
332 |
for(int i=0; i<8; i++) totalTwist += twist[i]; |
|
333 |
|
|
334 |
android.util.Log.e("D", "total twist "+totalTwist); |
|
335 |
|
|
336 |
if( (totalTwist%3)!=0 ) return ERROR_CORNER_TWISTED; |
|
337 |
|
|
338 |
int total = twist[0]+ 3*(twist[1]+ 3*(twist[2]+ 3*(twist[3]+ 3*(twist[4]+ 3*(twist[5]+ 3*twist[6]))))); |
|
339 |
|
|
340 |
int corner1 = positionOfFirstCorner(perm,twist); |
|
341 |
if( corner1<0 ) return ERROR_TWO_CORNERS; |
|
342 |
|
|
343 |
android.util.Log.e("D", "corner1: "+corner1+" center perm: "+center_perm_num+" twist: "+total); |
|
382 |
int locationOfFree0 = computeLocation(quats[1]); |
|
344 | 383 |
|
345 |
return corner1 + 4*(center_perm_num + 360*total);
|
|
384 |
return center_perm_num+ 360*(totalTwist + 2187*locationOfFree0);
|
|
346 | 385 |
} |
347 | 386 |
|
348 | 387 |
/////////////////////////////////////////////////////////////////////////////////////////////////// |
Also available in: Unified diff
Progess with Skewb solver.