commit 14cf0761a98885f5f2764448501f7d53b7e3de6b Author: Leszek Koltunski Date: Tue Mar 21 15:02:34 2023 +0100 Progess with Skewb solver. diff --git a/src/main/java/org/distorted/solvers/SolverSkewb.java b/src/main/java/org/distorted/solvers/SolverSkewb.java index f841fb49..c231f098 100644 --- a/src/main/java/org/distorted/solvers/SolverSkewb.java +++ b/src/main/java/org/distorted/solvers/SolverSkewb.java @@ -43,8 +43,6 @@ public class SolverSkewb extends SolverTablebase private static final int ERROR_TWO_CENTERS = -17; private static final int ERROR_TWO_CORNERS = -18; - private static final int ERROR_IMPOSSIBLE = -19; - private TablebasesAbstract mSolver; private final int[] mFaceColors; @@ -169,125 +167,171 @@ public class SolverSkewb extends SolverTablebase /////////////////////////////////////////////////////////////////////////////////////////////////// // free corners: 1,2,4,7 - private int retCornerPermutation(int[] perm, int[][] corners) + private int retFreeCornerPermutation(int[] perm, int[][] corners) { int[] map = {1,2,4,7}; - perm[0] = 0; + perm[0] = -1; perm[1] = -1; perm[2] = -1; - perm[3] = 3; - perm[4] = -1; - perm[5] = 5; - perm[6] = 6; - perm[7] = -1; + perm[3] = -1; for(int i=0; i<4; i++) { - int index = map[i]; - int[] cor = corners[index]; + int[] cor = corners[map[i]]; - if( cornerIs(cor,2,5,0) ) perm[1] = index; - if( cornerIs(cor,3,4,0) ) perm[2] = index; - if( cornerIs(cor,1,2,4) ) perm[4] = index; - if( cornerIs(cor,1,3,5) ) perm[7] = index; + if( cornerIs(cor,2,5,0) ) perm[0] = i; + if( cornerIs(cor,3,4,0) ) perm[1] = i; + if( cornerIs(cor,1,2,4) ) perm[2] = i; + if( cornerIs(cor,1,3,5) ) perm[3] = i; } - if( perm[1]==-1 ) return ERROR_CORNER_025_MISSING; - if( perm[2]==-1 ) return ERROR_CORNER_034_MISSING; - if( perm[4]==-1 ) return ERROR_CORNER_124_MISSING; - if( perm[7]==-1 ) return ERROR_CORNER_135_MISSING; + if( perm[0]==-1 ) return ERROR_CORNER_025_MISSING; + if( perm[1]==-1 ) return ERROR_CORNER_034_MISSING; + if( perm[2]==-1 ) return ERROR_CORNER_124_MISSING; + if( perm[3]==-1 ) return ERROR_CORNER_135_MISSING; return 0; } /////////////////////////////////////////////////////////////////////////////////////////////////// - private void fillCornerTwists(int[] output, int[][] corners, int[] perm) - { - final int[] map = { 4,2,3,5,1,5,4,1 }; + // [1][] are the 3 quats the 1st 'fixed' corner will have when 'fakeTwisted' (which in case of + // the fixed corners is the same as the final twist) with respectively twist 0,1,2. - for(int i=0; i<8; i++) - { - int color = mFaceColors[map[i]]; - int[] c = corners[perm[i]]; + private final int[][] fixedQuats = { {0,1,2},{0,7,8},{0,6,5},{0,4,3} }; - if( c[0]==color ) output[i] = 0; - else if( c[1]==color ) output[i] = 1; - else output[i] = 2; - } + // [1][2][] are the 3 quats the 1st free corner, when permuted to the location of the 2nd corner, + // will have when it is 'fakeTwisted' with fakeTwist 0,1,2. + // fakeTwist is an intermediate twist which needs yet to be translated to the final twist of the + // corners (which needs to sum up to something divisible by 3). + + private final int[][][] freeQuats= + { + { {0,3,4},{9,8,1},{6,11,2},{7,10,5} }, + { {9,2,7},{0,5,6},{1,10,3},{4,11,8} }, + { {5,1,11},{2,4,10},{0,8,7},{9,3,6} }, + { {8,6,10},{3,7,11},{9,5,4},{0,2,1} } + }; + + private void fillInQuats(int[] output, int[] perm, int[] twist) + { + output[0] = fixedQuats[0][twist[0]]; + output[1] = freeQuats[0][perm[0]][twist[1]]; + output[2] = freeQuats[1][perm[1]][twist[2]]; + output[3] = fixedQuats[1][twist[3]]; + output[4] = freeQuats[2][perm[2]][twist[3]]; + output[5] = fixedQuats[2][twist[5]]; + output[6] = fixedQuats[3][twist[6]]; + output[7] = freeQuats[3][perm[3]][twist[7]]; } /////////////////////////////////////////////////////////////////////////////////////////////////// - private int computeCenterTwist(int p1, int p2) + private int computeLocation(int quat) { - if( p1==1 ) - { - switch(p2) - { - case 2: return 2; - case 4: return 1; - case 7: return 0; - } - } - if( p1==2 ) - { - switch(p2) - { - case 1: return 2; - case 4: return 0; - case 7: return 1; - } - } - if( p1==4 ) + for(int i=0; i<4; i++) { - switch(p2) - { - case 1: return 1; - case 2: return 0; - case 7: return 2; - } + int[] q = freeQuats[0][i]; + if( quat==q[0] || quat==q[1] || quat==q[2] ) return i; } - if( p1==7 ) + + android.util.Log.e("D", "error in computeLocation, quat="+quat); + return -1; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + private int retFixed(int index, int quat) + { + int[] qs = fixedQuats[index]; + + if( quat==qs[0]) return 0; + if( quat==qs[1]) return 1; + if( quat==qs[2]) return 2; + + android.util.Log.e("D", "error in retFixed, index="+index+" quat="+quat); + return -1; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + private int retFree(int index, int quat) + { + int[][] qs = freeQuats[index]; + + for(int i=0; i<4; i++) { - switch(p2) - { - case 1: return 0; - case 2: return 1; - case 4: return 2; - } + if( quat==qs[i][0]) return 0; + if( quat==qs[i][1]) return 1; + if( quat==qs[i][2]) return 2; } - return ERROR_IMPOSSIBLE; + android.util.Log.e("D", "error in retFree, index="+index+" quat="+quat); + return -1; } /////////////////////////////////////////////////////////////////////////////////////////////////// - - private int positionOfFirstCorner(int[] perm, int[] twist) +// In case of the four 'fixed' corners (0,3,5,6) which do not change their location, +// the twist is natural: 0 in the init positions and increasing 1 mod 3 on each CW turn. +// +// In case of the four 'free' corners their twist is relative to the position of the 'free' +// tetrahedron. And so, for example the twist of free corner 1 (whose 0th face is orange) is equal +// to 0 if free corner 7 is on the same face like 0th face of corner 1 (which is the case in init +// position); then once free corners 2,4,7 permute CW, twist of corner 1 increases by 1 mod 3. + + private void computeCornerTwists(int[] twists, int[] quats) { - int total_fixed_twist = twist[0]+twist[3]+twist[5]+twist[6]; + twists[0] = retFixed(0,quats[0]); + twists[3] = retFixed(1,quats[3]); + twists[5] = retFixed(2,quats[5]); + twists[6] = retFixed(3,quats[6]); + + twists[1] = retFree(0,quats[1]); + twists[2] = retFree(1,quats[2]); + twists[4] = retFree(2,quats[4]); + twists[7] = retFree(3,quats[7]); + } - int twist_42 = computeCenterTwist(perm[4],perm[2]); - int twist_21 = computeCenterTwist(perm[2],perm[1]); +/////////////////////////////////////////////////////////////////////////////////////////////////// - if( twist_42<0 || twist_21<0 ) return ERROR_IMPOSSIBLE; + private int retCornerPerm(int index, int[] perm) + { + int[] free = {1,2,4,7}; + switch(index) + { + case 0: return 0; + case 1: return free[perm[0]]; + case 2: return free[perm[1]]; + case 3: return 3; + case 4: return free[perm[2]]; + case 5: return 5; + case 6: return 6; + case 7: return free[perm[3]]; + } -android.util.Log.e("D", "twist42 "+twist_42+" twist21 "+twist_21+" total: "+total_fixed_twist); + return -1; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// - if( (twist_21-twist_42+1)%3 != 0 ) return ERROR_TWO_CORNERS; - if( (total_fixed_twist-twist_42)%3 !=0 ) return ERROR_CORNER_TWISTED; + private void computeCornerQuats(int[] quats, int[][] corners, int[] perm) + { + final int[] map = { 4,2,3,5,1,5,4,1 }; + int[] twists = new int[8]; - switch(perm[1]) + for(int i=0; i<8; i++) { - case 1: return 0; - case 2: return 1; - case 4: return 2; - case 7: return 3; + int color = mFaceColors[map[i]]; + int[] c = corners[retCornerPerm(i,perm)]; + + if( c[0]==color ) twists[i] = 0; + else if( c[1]==color ) twists[i] = 1; + else twists[i] = 2; } - return ERROR_IMPOSSIBLE; + fillInQuats(quats,perm,twists); } /////////////////////////////////////////////////////////////////////////////////////////////////// @@ -297,7 +341,8 @@ android.util.Log.e("D", "twist42 "+twist_42+" twist21 "+twist_21+" total: "+tota int[][] corners= new int[8][3]; int[] centers = new int[6]; int[] twist = new int[8]; - int[] perm = new int[8]; + int[] freePerm = new int[4]; + int[] quats = new int[8]; getCorners(object,corners); @@ -320,29 +365,23 @@ for(int i=0; i<6; i++) android.util.Log.e("D", "face "+i+" : "+mFaceColors[i]); if( !TablebaseHelpers.permutationIsEven(centers) ) return ERROR_TWO_CENTERS; int center_perm_num = TablebaseHelpers.computeEvenPermutationNum(centers); - int result4 = retCornerPermutation(perm,corners); + int result4 = retFreeCornerPermutation(freePerm,corners); if( result4<0 ) return result4; - fillCornerTwists(twist,corners,perm); - -for(int i=0; i<8; i++) android.util.Log.e("D", "perm "+i+" : "+perm[i]); + computeCornerQuats(quats,corners,freePerm); + computeCornerTwists(twist,quats); +/* +for(int i=0; i<4; i++) android.util.Log.e("D", "perm "+i+" : "+freePerm[i]); +for(int i=0; i<8; i++) android.util.Log.e("D", "quat "+i+" : "+quats[i]); for(int i=0; i<8; i++) android.util.Log.e("D", "twist "+i+" : "+twist[i]); +*/ + int total = twist[1]+twist[2]+twist[4]+twist[7]; + if( (total%3)!=0 ) return ERROR_CORNER_TWISTED; + int totalTwist = twist[0]+ 3*(twist[1]+ 3*(twist[2]+ 3*(twist[3]+ 3*(twist[4]+ 3*(twist[5]+ 3*twist[6]))))); - int totalTwist = 0; - for(int i=0; i<8; i++) totalTwist += twist[i]; - -android.util.Log.e("D", "total twist "+totalTwist); - - if( (totalTwist%3)!=0 ) return ERROR_CORNER_TWISTED; - - int total = twist[0]+ 3*(twist[1]+ 3*(twist[2]+ 3*(twist[3]+ 3*(twist[4]+ 3*(twist[5]+ 3*twist[6]))))); - - int corner1 = positionOfFirstCorner(perm,twist); - if( corner1<0 ) return ERROR_TWO_CORNERS; - -android.util.Log.e("D", "corner1: "+corner1+" center perm: "+center_perm_num+" twist: "+total); + int locationOfFree0 = computeLocation(quats[1]); - return corner1 + 4*(center_perm_num + 360*total); + return center_perm_num+ 360*(totalTwist + 2187*locationOfFree0); } ///////////////////////////////////////////////////////////////////////////////////////////////////