commit 358be4033f9bce9f5a94cf327ed5ba8bfdfbf7dc Author: Leszek Koltunski Date: Mon Jul 11 14:07:05 2022 +0200 Optimize the solver. diff --git a/src/main/java/org/distorted/solvers/SolverMain.java b/src/main/java/org/distorted/solvers/SolverMain.java index d6772d69..a583d501 100644 --- a/src/main/java/org/distorted/solvers/SolverMain.java +++ b/src/main/java/org/distorted/solvers/SolverMain.java @@ -27,6 +27,7 @@ import org.distorted.objectlib.main.TwistyObject; import org.distorted.main.R; import org.distorted.screens.ScreenList; import org.distorted.screens.RubikScreenSolver; +import org.distorted.solvers.cube3.RubikSolverSearch; /////////////////////////////////////////////////////////////////////////////////////////////////// @@ -72,13 +73,9 @@ public class SolverMain implements Runnable { String result; - if( !org.distorted.solvers.cube3.Search.prepare(mRes) ) - result= "Error 9"; - else - { - String objectPosition = prepareCube3position(); - result = org.distorted.solvers.cube3.Search.solution(objectPosition, 24, 20); - } + RubikSolverSearch.prepare(mRes); + String objectPosition = prepareCube3position(); + result = RubikSolverSearch.solution(objectPosition, 24, 20); if (result.contains("Error")) { @@ -207,13 +204,6 @@ public class SolverMain implements Runnable return objectString.toString(); } -/////////////////////////////////////////////////////////////////////////////////////////////////// - - private void interruptCube3() - { - org.distorted.solvers.cube3.Search.interrupt(); - } - /////////////////////////////////////////////////////////////////////////////////////////////////// public void start() diff --git a/src/main/java/org/distorted/solvers/cube3/Color.java b/src/main/java/org/distorted/solvers/cube3/Color.java deleted file mode 100644 index 91f5c139..00000000 --- a/src/main/java/org/distorted/solvers/cube3/Color.java +++ /dev/null @@ -1,41 +0,0 @@ -package org.distorted.solvers.cube3; - -//++++++++++++++++++++++++++++++ Names the colors of the cube facelets ++++++++++++++++++++++++++++++++++++++++++++++++ - -class Color - { - public static final int U=0; - public static final int R=1; - public static final int F=2; - public static final int D=3; - public static final int L=4; - public static final int B=5; - - public static String toString(int i) - { - switch(i) - { - case U: return "U"; - case R: return "R"; - case F: return "F"; - case D: return "D"; - case L: return "L"; - case B: return "B"; - default: return "?"; - } - } - - public static int toInt(String s) - { - switch(s.charAt(0)) - { - case 'U': return U; - case 'R': return R; - case 'F': return F; - case 'D': return D; - case 'L': return L; - case 'B': return B; - default: return -1; - } - } - } \ No newline at end of file diff --git a/src/main/java/org/distorted/solvers/cube3/CoordCube.java b/src/main/java/org/distorted/solvers/cube3/CoordCube.java deleted file mode 100644 index 1869f3ce..00000000 --- a/src/main/java/org/distorted/solvers/cube3/CoordCube.java +++ /dev/null @@ -1,507 +0,0 @@ -package org.distorted.solvers.cube3; - -import android.content.res.Resources; -import java.io.InputStream; - -//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -// Representation of the cube on the coordinate level -class CoordCube { - - static final short N_TWIST = 2187;// 3^7 possible corner orientations - static final short N_FLIP = 2048;// 2^11 possible edge flips - static final short N_SLICE1 = 495;// 12 choose 4 possible positions of FR,FL,BL,BR edges - static final short N_SLICE2 = 24;// 4! permutations of FR,FL,BL,BR edges in phase2 - static final short N_PARITY = 2; // 2 possible corner parities - static final short N_URFtoDLF = 20160;// 8!/(8-6)! permutation of URF,UFL,ULB,UBR,DFR,DLF corners - static final short N_FRtoBR = 11880; // 12!/(12-4)! permutation of FR,FL,BL,BR edges - static final short N_URtoUL = 1320; // 12!/(12-3)! permutation of UR,UF,UL edges - static final short N_UBtoDF = 1320; // 12!/(12-3)! permutation of UB,DR,DF edges - static final short N_URtoDF = 20160; // 8!/(8-6)! permutation of UR,UF,UL,UB,DR,DF edges in phase2 - - static final int N_URFtoDLB = 40320;// 8! permutations of the corners - static final int N_URtoBR = 479001600;// 8! permutations of the corners - - static final short N_MOVE = 18; - - // All coordinates are 0 for a solved cube except for UBtoDF, which is 114 - short twist; - short flip; - short parity; - short FRtoBR; - short URFtoDLF; - short URtoUL; - short UBtoDF; - int URtoDF; - - private static boolean[] init = new boolean[12]; - - static - { - for(int i=0; i<12; i++ ) init[i] = false; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Generate a CoordCube from a CubieCube - CoordCube(CubieCube c) { - twist = c.getTwist(); - flip = c.getFlip(); - parity = c.cornerParity(); - FRtoBR = c.getFRtoBR(); - URFtoDLF = c.getURFtoDLF(); - URtoUL = c.getURtoUL(); - UBtoDF = c.getUBtoDF(); - URtoDF = c.getURtoDF();// only needed in phase2 - } - - // A move on the coordinate level - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - void move(int m) { - twist = getTwistMove(twist,m); - flip = getFlipMove(flip,m); - parity = parityMove[parity][m]; - FRtoBR = getFRtoBR_Move(FRtoBR,m); - URFtoDLF = getURFtoDLF_Move(URFtoDLF,m); - URtoUL = getURtoUL_Move(URtoUL,m); - UBtoDF = getUBtoDF_Move(UBtoDF,m); - if (URtoUL < 336 && UBtoDF < 336)// updated only if UR,UF,UL,UB,DR,DF - // are not in UD-slice - URtoDF = getMergeURtoULandUBtoDF(URtoUL,UBtoDF); - } - - // ******************************************Phase 1 move tables***************************************************** - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Move table for the twists of the corners - // twist < 2187 in phase 2. - // twist = 0 in phase 2. - private static byte[] twistMove = new byte[2*N_TWIST*N_MOVE]; - - public static boolean initialize1(Resources res) - { - if( !init[0] ) - { - try - { - InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table1); - is.read( twistMove, 0, 2*N_TWIST*N_MOVE); - } - catch(Exception ioe) - { - System.out.println("error reading table1"); - return false; - } - - init[0]=true; - } - - return true; - } - - public static short getTwistMove(int a,int b) - { - short upperS = twistMove[2*(a*N_MOVE+b)]; - short lowerS = twistMove[2*(a*N_MOVE+b)+1]; - - if( upperS<0 ) upperS+=256; - if( lowerS<0 ) lowerS+=256; - - return (short)( (upperS<<8) + lowerS ); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Move table for the flips of the edges - // flip < 2048 in phase 1 - // flip = 0 in phase 2. - private static byte[] flipMove = new byte[2*N_FLIP*N_MOVE]; - - public static boolean initialize2(Resources res) - { - if( !init[1] ) - { - try - { - InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table2); - is.read( flipMove, 0, 2*N_FLIP*N_MOVE); - } - catch(Exception ioe) - { - System.out.println("error reading table2"); - return false; - } - - init[1]=true; - } - - return true; - } - - public static short getFlipMove(int a,int b) - { - short upperS = flipMove[2*(a*N_MOVE+b)]; - short lowerS = flipMove[2*(a*N_MOVE+b)+1]; - - if( upperS<0 ) upperS+=256; - if( lowerS<0 ) lowerS+=256; - - return (short)( (upperS<<8) + lowerS ); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Parity of the corner permutation. This is the same as the parity for the edge permutation of a valid cube. - // parity has values 0 and 1 - static short[][] parityMove = { { 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 }, - { 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0 } }; - - // ***********************************Phase 1 and 2 movetable******************************************************** - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Move table for the four UD-slice edges FR, FL, Bl and BR - // FRtoBRMove < 11880 in phase 1 - // FRtoBRMove < 24 in phase 2 - // FRtoBRMove = 0 for solved cube - private static byte[] FRtoBR_Move = new byte[2*N_FRtoBR*N_MOVE]; - - public static boolean initialize3(Resources res) - { - if( !init[2] ) - { - try - { - InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table3); - is.read( FRtoBR_Move, 0, 2*N_FRtoBR*N_MOVE); - } - catch(Exception ioe) - { - System.out.println("error reading table3"); - return true; - } - - init[2]=true; - } - - return false; - } - - public static short getFRtoBR_Move(int a,int b) - { - short upperS = FRtoBR_Move[2*(a*N_MOVE+b)]; - short lowerS = FRtoBR_Move[2*(a*N_MOVE+b)+1]; - - if( upperS<0 ) upperS+=256; - if( lowerS<0 ) lowerS+=256; - - return (short)( (upperS<<8) + lowerS ); - } - - // *******************************************Phase 1 and 2 movetable************************************************ - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Move table for permutation of six corners. The positions of the DBL and DRB corners are determined by the parity. - // URFtoDLF < 20160 in phase 1 - // URFtoDLF < 20160 in phase 2 - // URFtoDLF = 0 for solved cube. - private static byte[] URFtoDLF_Move = new byte[2*N_URFtoDLF*N_MOVE]; - - public static boolean initialize4(Resources res) - { - if( !init[3] ) - { - try - { - InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table4); - is.read( URFtoDLF_Move, 0, 2*N_URFtoDLF*N_MOVE); - } - catch(Exception ioe) - { - System.out.println("error reading table4"); - return false; - } - - init[3]=true; - } - - return true; - } - - public static short getURFtoDLF_Move(int a,int b) - { - short upperS = URFtoDLF_Move[2*(a*N_MOVE+b)]; - short lowerS = URFtoDLF_Move[2*(a*N_MOVE+b)+1]; - - if( upperS<0 ) upperS+=256; - if( lowerS<0 ) lowerS+=256; - - return (short)( (upperS<<8) + lowerS ); - } - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Move table for the permutation of six U-face and D-face edges in phase2. The positions of the DL and DB edges are - // determined by the parity. - // URtoDF < 665280 in phase 1 - // URtoDF < 20160 in phase 2 - // URtoDF = 0 for solved cube. - private static byte[] URtoDF_Move = new byte[2*N_URtoDF*N_MOVE]; - - public static boolean initialize5(Resources res) - { - if( !init[4] ) - { - try - { - InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table5); - is.read( URtoDF_Move, 0, 2*N_URtoDF*N_MOVE); - } - catch(Exception ioe) - { - System.out.println("error reading table5"); - return false; - } - - init[4]=true; - } - - return true; - } - - public static short getURtoDF_Move(int a,int b) - { - short upperS = URtoDF_Move[2*(a*N_MOVE+b)]; - short lowerS = URtoDF_Move[2*(a*N_MOVE+b)+1]; - - if( upperS<0 ) upperS+=256; - if( lowerS<0 ) lowerS+=256; - - return (short)( (upperS<<8) + lowerS ); - } - // **************************helper move tables to compute URtoDF for the beginning of phase2************************ - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Move table for the three edges UR,UF and UL in phase1. - private static byte[] URtoUL_Move = new byte[2*N_URtoUL*N_MOVE]; - - public static boolean initialize6(Resources res) - { - if( !init[5] ) - { - try - { - InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table6); - is.read( URtoUL_Move, 0, 2*N_URtoUL*N_MOVE); - } - catch(Exception ioe) - { - System.out.println("error reading table6"); - return false; - } - - init[5]=true; - } - - return true; - } - - public static short getURtoUL_Move(int a,int b) - { - short upperS = URtoUL_Move[2*(a*N_MOVE+b)]; - short lowerS = URtoUL_Move[2*(a*N_MOVE+b)+1]; - - if( upperS<0 ) upperS+=256; - if( lowerS<0 ) lowerS+=256; - - return (short)( (upperS<<8) + lowerS ); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Move table for the three edges UB,DR and DF in phase1. - private static byte[] UBtoDF_Move = new byte[2*N_UBtoDF*N_MOVE]; - - public static boolean initialize7(Resources res) - { - if( !init[6] ) - { - try - { - InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table7); - is.read( UBtoDF_Move, 0, 2*N_UBtoDF*N_MOVE); - } - catch(Exception ioe) - { - System.out.println("error reading table7"); - return false; - } - - init[6]=true; - } - - return true; - } - - public static short getUBtoDF_Move(int a,int b) - { - short upperS = UBtoDF_Move[2*(a*N_MOVE+b)]; - short lowerS = UBtoDF_Move[2*(a*N_MOVE+b)+1]; - - if( upperS<0 ) upperS+=256; - if( lowerS<0 ) lowerS+=256; - - return (short)( (upperS<<8) + lowerS ); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Table to merge the coordinates of the UR,UF,UL and UB,DR,DF edges at the beginning of phase2 - private static byte[] MergeURtoULandUBtoDF = new byte[2*336*336]; - - public static boolean initialize8(Resources res) - { - if( !init[7] ) - { - try - { - InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table8); - is.read( MergeURtoULandUBtoDF, 0, 2*336*336); - } - catch(Exception ioe) - { - System.out.println("error reading table8"); - return false; - } - - init[7]=true; - } - - return true; - } - - public static short getMergeURtoULandUBtoDF(int a,int b) - { - short upperS = MergeURtoULandUBtoDF[2*(a*336+b)]; - short lowerS = MergeURtoULandUBtoDF[2*(a*336+b)+1]; - - if( upperS<0 ) upperS+=256; - if( lowerS<0 ) lowerS+=256; - - return (short)( (upperS<<8) + lowerS ); - } - // ****************************************Pruning tables for the search********************************************* - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Pruning table for the permutation of the corners and the UD-slice edges in phase2. - // The pruning table entries give a lower estimation for the number of moves to reach the solved cube. - public static byte[] Slice_URFtoDLF_Parity_Prun = new byte[N_SLICE2 * N_URFtoDLF * N_PARITY / 2]; - - public static boolean initialize9(Resources res) - { - if( !init[8] ) - { - try - { - InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table9); - is.read( Slice_URFtoDLF_Parity_Prun, 0, N_SLICE2 * N_URFtoDLF * N_PARITY / 2); - } - catch(Exception ioe) - { - System.out.println("error reading table9"); - return false; - } - - init[8]=true; - } - - return true; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Pruning table for the permutation of the edges in phase2. - // The pruning table entries give a lower estimation for the number of moves to reach the solved cube. - public static byte[] Slice_URtoDF_Parity_Prun = new byte[N_SLICE2 * N_URtoDF * N_PARITY / 2]; - - public static boolean initialize10(Resources res) - { - if( !init[9] ) - { - try - { - InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table10); - is.read( Slice_URtoDF_Parity_Prun, 0, N_SLICE2 * N_URtoDF * N_PARITY / 2); - } - catch(Exception ioe) - { - System.out.println("error reading table10"); - return false; - } - - init[9]=true; - } - - return true; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Pruning table for the twist of the corners and the position (not permutation) of the UD-slice edges in phase1 - // The pruning table entries give a lower estimation for the number of moves to reach the H-subgroup. - public static byte[] Slice_Twist_Prun = new byte[N_SLICE1 * N_TWIST / 2 + 1]; - - public static boolean initialize11(Resources res) - { - if( !init[10] ) - { - try - { - InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table11); - is.read( Slice_Twist_Prun, 0, N_SLICE1 * N_TWIST / 2 + 1); - } - catch(Exception ioe) - { - System.out.println("error reading table11"); - return false; - } - - init[10]=true; - } - - return true; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Pruning table for the flip of the edges and the position (not permutation) of the UD-slice edges in phase1 - // The pruning table entries give a lower estimation for the number of moves to reach the H-subgroup. - public static byte[] Slice_Flip_Prun = new byte[N_SLICE1 * N_FLIP / 2]; - - public static boolean initialize12(Resources res) - { - if( !init[11] ) - { - try - { - InputStream is = res.openRawResource(org.distorted.main.R.raw.cube3solver_table12); - is.read( Slice_Flip_Prun, 0, N_SLICE1 * N_FLIP / 2); - } - catch(Exception ioe) - { - System.out.println("error reading table12"); - return false; - } - - init[11]=true; - } - - return true; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Set pruning value in table. Two values are stored in one byte. - static void setPruning(byte[] table, int index, byte value) { - if ((index & 1) == 0) - table[index / 2] &= 0xf0 | value; - else - table[index / 2] &= 0x0f | (value << 4); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Extract pruning value - static byte getPruning(byte[] table, int index) { - if ((index & 1) == 0) - return (byte) (table[index / 2] & 0x0f); - else - return (byte) ((table[index / 2] & 0xf0) >>> 4); - } -} diff --git a/src/main/java/org/distorted/solvers/cube3/Corner.java b/src/main/java/org/distorted/solvers/cube3/Corner.java deleted file mode 100644 index 7f943759..00000000 --- a/src/main/java/org/distorted/solvers/cube3/Corner.java +++ /dev/null @@ -1,16 +0,0 @@ -package org.distorted.solvers.cube3; - -//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -//The names of the corner positions of the cube. Corner URF e.g., has an U(p), a R(ight) and a F(ront) facelet - -class Corner - { - public static final int URF =0; - public static final int UFL =1; - public static final int ULB =2; - public static final int UBR =3; - public static final int DFR =4; - public static final int DLF =5; - public static final int DBL =6; - public static final int DRB =7; - } \ No newline at end of file diff --git a/src/main/java/org/distorted/solvers/cube3/CubieCube.java b/src/main/java/org/distorted/solvers/cube3/CubieCube.java deleted file mode 100644 index d3f4d067..00000000 --- a/src/main/java/org/distorted/solvers/cube3/CubieCube.java +++ /dev/null @@ -1,836 +0,0 @@ -package org.distorted.solvers.cube3; - -//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -//Cube on the cubie level -class CubieCube - { - private static int[][] cnk = new int[12][7]; - - private static byte[] tmpByte12 = new byte[12]; - private static byte[] tmpByte8 = new byte[8]; - - private static int[] tmpEdge12 = new int[12]; - private static int[] tmpEdge6 = new int[6]; - private static int[] tmpEdge4 = new int[4]; - private static int[] tmpEdge3 = new int[3]; - - private static int[] tmpCorner6 = new int[6]; - private static int[] tmpCorner8 = new int[8]; - - // initialize to Id-Cube - - // corner permutation - int[] cp = { Corner.URF, Corner.UFL, Corner.ULB, Corner.UBR, Corner.DFR, Corner.DLF, Corner.DBL, Corner.DRB }; - - // corner orientation - byte[] co = { 0, 0, 0, 0, 0, 0, 0, 0 }; - - // edge permutation - int[] ep = { Edge.UR, Edge.UF, Edge.UL, Edge.UB, Edge.DR, Edge.DF, Edge.DL, Edge.DB, Edge.FR, Edge.FL, Edge.BL, Edge.BR }; - - // edge orientation - byte[] eo = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; - - // ************************************** Moves on the cubie level *************************************************** - - private static int[] cpU = { Corner.UBR, Corner.URF, Corner.UFL, Corner.ULB, Corner.DFR, Corner.DLF, Corner.DBL, Corner.DRB }; - private static byte[] coU = { 0, 0, 0, 0, 0, 0, 0, 0 }; - private static int[] epU = { Edge.UB, Edge.UR, Edge.UF, Edge.UL, Edge.DR, Edge.DF, Edge.DL, Edge.DB, Edge.FR, Edge.FL, Edge.BL, Edge.BR }; - private static byte[] eoU = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; - - private static int[] cpR = { Corner.DFR, Corner.UFL, Corner.ULB, Corner.URF, Corner.DRB, Corner.DLF, Corner.DBL, Corner.UBR }; - private static byte[] coR = { 2, 0, 0, 1, 1, 0, 0, 2 }; - private static int[] epR = { Edge.FR, Edge.UF, Edge.UL, Edge.UB, Edge.BR, Edge.DF, Edge.DL, Edge.DB, Edge.DR, Edge.FL, Edge.BL, Edge.UR }; - private static byte[] eoR = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; - - private static int[] cpF = { Corner.UFL, Corner.DLF, Corner.ULB, Corner.UBR, Corner.URF, Corner.DFR, Corner.DBL, Corner.DRB }; - private static byte[] coF = { 1, 2, 0, 0, 2, 1, 0, 0 }; - private static int[] epF = { Edge.UR, Edge.FL, Edge.UL, Edge.UB, Edge.DR, Edge.FR, Edge.DL, Edge.DB, Edge.UF, Edge.DF, Edge.BL, Edge.BR }; - private static byte[] eoF = { 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0 }; - - private static int[] cpD = { Corner.URF, Corner.UFL, Corner.ULB, Corner.UBR, Corner.DLF, Corner.DBL, Corner.DRB, Corner.DFR }; - private static byte[] coD = { 0, 0, 0, 0, 0, 0, 0, 0 }; - private static int[] epD = { Edge.UR, Edge.UF, Edge.UL, Edge.UB, Edge.DF, Edge.DL, Edge.DB, Edge.DR, Edge.FR, Edge.FL, Edge.BL, Edge.BR }; - private static byte[] eoD = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; - - private static int[] cpL = { Corner.URF, Corner.ULB, Corner.DBL, Corner.UBR, Corner.DFR, Corner.UFL, Corner.DLF, Corner.DRB }; - private static byte[] coL = { 0, 1, 2, 0, 0, 2, 1, 0 }; - private static int[] epL = { Edge.UR, Edge.UF, Edge.BL, Edge.UB, Edge.DR, Edge.DF, Edge.FL, Edge.DB, Edge.FR, Edge.UL, Edge.DL, Edge.BR }; - private static byte[] eoL = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; - - private static int[] cpB = { Corner.URF, Corner.UFL, Corner.UBR, Corner.DRB, Corner.DFR, Corner.DLF, Corner.ULB, Corner.DBL }; - private static byte[] coB = { 0, 0, 1, 2, 0, 0, 2, 1 }; - private static int[] epB = { Edge.UR, Edge.UF, Edge.UL, Edge.BR, Edge.DR, Edge.DF, Edge.DL, Edge.BL, Edge.FR, Edge.FL, Edge.UB, Edge.DB }; - private static byte[] eoB = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1 }; - - // this CubieCube array represents the 6 basic cube moves - static CubieCube[] moveCube = new CubieCube[6]; - - static - { - moveCube[0] = new CubieCube(); - moveCube[0].cp = cpU; - moveCube[0].co = coU; - moveCube[0].ep = epU; - moveCube[0].eo = eoU; - - moveCube[1] = new CubieCube(); - moveCube[1].cp = cpR; - moveCube[1].co = coR; - moveCube[1].ep = epR; - moveCube[1].eo = eoR; - - moveCube[2] = new CubieCube(); - moveCube[2].cp = cpF; - moveCube[2].co = coF; - moveCube[2].ep = epF; - moveCube[2].eo = eoF; - - moveCube[3] = new CubieCube(); - moveCube[3].cp = cpD; - moveCube[3].co = coD; - moveCube[3].ep = epD; - moveCube[3].eo = eoD; - - moveCube[4] = new CubieCube(); - moveCube[4].cp = cpL; - moveCube[4].co = coL; - moveCube[4].ep = epL; - moveCube[4].eo = eoL; - - moveCube[5] = new CubieCube(); - moveCube[5].cp = cpB; - moveCube[5].co = coB; - moveCube[5].ep = epB; - moveCube[5].eo = eoB; - } - - static - { - for(int n=0; n<12; n++) - for(int k=0; k<7; k++) - cnk[n][k] = -1; - } - - CubieCube() { }; - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - CubieCube(int[] cp, byte[] co, int[] ep, byte[] eo) - { - this(); - - for (int i = 0; i < 8; i++) - { - this.cp[i] = cp[i]; - this.co[i] = co[i]; - } - for (int i = 0; i < 12; i++) - { - this.ep[i] = ep[i]; - this.eo[i] = eo[i]; - } - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // n choose k - static int Cnk(int n, int k) - { - if( cnk[n][k]<0 ) - { - int i, j, s; - - if (n < k) { cnk[n][k]=0; return 0; } - if (k > n / 2) k = n - k; - - for (s = 1, i = n, j = 1; i != n - k; i--, j++) - { - s *= i; - s /= j; - } - cnk[n][k]= s; - } - - return cnk[n][k]; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - static void rotateLeft(int[] arr, int l, int r) - // Left rotation of all array elements between l and r - { - int tmp = arr[l]; - for (int i = l; i < r; i++) arr[i] = arr[i + 1]; - arr[r] = tmp; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - static void rotateRight(int[] arr, int l, int r) - // Right rotation of all array elements between l and r - { - int tmp = arr[r]; - for (int i = r; i > l; i--) arr[i] = arr[i - 1]; - arr[l] = tmp; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // return cube in facelet representation - FaceCube toFaceCube() - { - FaceCube fcRet = new FaceCube(); - - for ( int c=Corner.URF; c<=Corner.DRB; c++) - { - int j = cp[c]; // cornercubie with index j is at cornerposition with index i - byte ori = co[c];// Orientation of this cubie - - for (int n = 0; n < 3; n++) - fcRet.f[FaceCube.cornerFacelet[c][(n + ori) % 3]] = FaceCube.cornerColor[j][n]; - } - - for ( int e=Edge.UR; e<=Edge.BR; e++) - { - int j = ep[e]; // edgecubie with index j is at edgeposition with index i - byte ori = eo[e];// Orientation of this cubie - - for (int n = 0; n < 2; n++) - fcRet.f[FaceCube.edgeFacelet[e][(n + ori) % 2]] = FaceCube.edgeColor[j][n]; - } - - return fcRet; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Multiply this CubieCube with another cubiecube b, restricted to the corners.
- // Because we also describe reflections of the whole cube by permutations, we get a complication with the corners. The - // orientations of mirrored corners are described by the numbers 3, 4 and 5. The composition of the orientations - // cannot - // be computed by addition modulo three in the cyclic group C3 any more. Instead the rules below give an addition in - // the dihedral group D3 with 6 elements.
- // - // NOTE: Because we do not use symmetry reductions and hence no mirrored cubes in this simple implementation of the - // Two-Phase-Algorithm, some code is not necessary here. - // - void cornerMultiply(CubieCube b) - { - for ( int corn=Corner.URF; corn<=Corner.DRB; corn++) - { - tmpCorner8[corn] = cp[b.cp[corn]]; - byte oriA = co[b.cp[corn]]; - byte oriB = b.co[corn]; - byte ori = 0; - - if (oriA < 3 && oriB < 3) // if both cubes are regular cubes... - { - ori = (byte) (oriA + oriB); // just do an addition modulo 3 here - if (ori >= 3) ori -= 3; // the composition is a regular cube - - // +++++++++++++++++++++not used in this implementation +++++++++++++++++++++++++++++++++++ - } - else if (oriA < 3 && oriB >= 3) // if cube b is in a mirrored state... - { - ori = (byte) (oriA + oriB); - if (ori >= 6) ori -= 3; // the composition is a mirrored cube - } - else if (oriA >= 3 && oriB < 3) // if cube a is an a mirrored state... - { - ori = (byte) (oriA - oriB); - if (ori < 3) ori += 3; // the composition is a mirrored cube - } - else if (oriA >= 3 && oriB >= 3) // if both cubes are in mirrored states... - { - ori = (byte) (oriA - oriB); - if (ori < 0) ori += 3; // the composition is a regular cube - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - } - - tmpByte8[corn] = ori; - } - - for ( int c=Corner.URF; c<=Corner.DRB; c++) - { - cp[c] = tmpCorner8[c]; - co[c] = tmpByte8[c]; - } - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Multiply this CubieCube with another cubiecube b, restricted to the edges. - void edgeMultiply(CubieCube b) - { - for ( int edge=Edge.UR; edge<=Edge.BR; edge++) - { - tmpEdge12[edge] = ep[b.ep[edge]]; - tmpByte12[edge] = (byte) ((b.eo[edge] + eo[b.ep[edge]]) % 2); - } - - for ( int e=Edge.UR; e<=Edge.BR; e++) - { - ep[e] = tmpEdge12[e]; - eo[e] = tmpByte12[e]; - } - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Multiply this CubieCube with another CubieCube b. - void multiply(CubieCube b) - { - cornerMultiply(b); - //edgeMultiply(b); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Compute the inverse CubieCube - void invCubieCube(CubieCube c) - { - for ( int edge=Edge.UR; edge<=Edge.BR; edge++) c.ep[ep[edge]] = edge; - for ( int edge=Edge.UR; edge<=Edge.BR; edge++) c.eo[edge] = eo[c.ep[edge]]; - - for ( int corn=Corner.URF; corn<=Corner.DRB; corn++) c.cp[cp[corn]] = corn; - for ( int corn=Corner.URF; corn<=Corner.DRB; corn++) - { - byte ori = co[c.cp[corn]]; - if (ori >= 3)// Just for completeness. We do not invert mirrored cubes in the program. - c.co[corn] = ori; - else - {// the standard case - c.co[corn] = (byte) -ori; - if (c.co[corn] < 0) c.co[corn] += 3; - } - } - } - - // ********************************************* Get and set coordinates ********************************************* - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // return the twist of the 8 corners. 0 <= twist < 3^7 - short getTwist() - { - short ret = 0; - - for ( int i=Corner.URF; i=Corner.URF; i--) - { - twistParity += co[i] = (byte) (twist % 3); - twist /= 3; - } - co[Corner.DRB] = (byte) ((3 - twistParity % 3) % 3); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // return the flip of the 12 edges. 0<= flip < 2^11 - short getFlip() - { - short ret = 0; - - for ( int i=Edge.UR; i=Edge.UR; i--) - { - flipParity += eo[i] = (byte) (flip % 2); - flip /= 2; - } - eo[Edge.BR] = (byte) ((2 - flipParity % 2) % 2); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Parity of the corner permutation - short cornerParity() - { - int s = 0; - - for (int i=Corner.DRB; i>=Corner.URF+1; i--) - for (int j = i - 1; j >= Corner.URF; j--) - if (cp[j] > cp[i]) s++; - - return (short) (s % 2); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Parity of the edges permutation. Parity of corners and edges are the same if the cube is solvable. - short edgeParity() - { - int s = 0; - - for (int i = Edge.BR; i >= Edge.UR+1; i--) - for (int j = i - 1; j >= Edge.UR; j--) - if (ep[j] > ep[i]) s++; - - return (short) (s % 2); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // permutation of the UD-slice edges FR,FL,BL and BR - short getFRtoBR() - { - int a = 0, x = 0; - - // compute the index a < (12 choose 4) and the permutation array perm. - for (int j = Edge.BR; j >= Edge.UR; j--) - if (Edge.FR <= ep[j] && ep[j] <= Edge.BR) - { - a += Cnk(11 - j, x + 1); - tmpEdge4[3 - x++] = ep[j]; - } - - int b = 0; - for (int j = 3; j > 0; j--)// compute the index b < 4! for the permutation in perm - { - int k = 0; - while (tmpEdge4[j] != j + 8) - { - rotateLeft(tmpEdge4, 0, j); - k++; - } - b = (j + 1) * b + k; - } - - return (short) (24 * a + b); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - void setFRtoBR(short idx) - { - int x; - int[] sliceEdge = { Edge.FR, Edge.FL, Edge.BL, Edge.BR }; - int[] otherEdge = { Edge.UR, Edge.UF, Edge.UL, Edge.UB, Edge.DR, Edge.DF, Edge.DL, Edge.DB }; - int b = idx % 24; // Permutation - int a = idx / 24; // Combination - - for ( int e=Edge.UR; e<=Edge.BR; e++) ep[e] = Edge.DB;// Use UR to invalidate all edges - - for (int j = 1, k; j < 4; j++)// generate permutation from index b - { - k = b % (j + 1); - b /= j + 1; - while (k-- > 0) rotateRight(sliceEdge, 0, j); - } - - x = 3;// generate combination and set slice edges - - for (int j = Edge.UR; j <= Edge.BR; j++) - if (a - Cnk(11 - j, x + 1) >= 0) - { - ep[j] = sliceEdge[3 - x]; - a -= Cnk(11 - j, x-- + 1); - } - - x = 0; // set the remaining edges UR..DB - - for (int j = Edge.UR; j <= Edge.BR; j++) - if (ep[j] == Edge.DB) - ep[j] = otherEdge[x++]; - - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Permutation of all corners except DBL and DRB - short getURFtoDLF() - { - int a = 0, x = 0; - - // compute the index a < (8 choose 6) and the corner permutation. - for (int j = Corner.URF; j <= Corner.DRB; j++) - if (cp[j] <= Corner.DLF) - { - a += Cnk(j, x + 1); - tmpCorner6[x++] = cp[j]; - } - - int b = 0; - - for (int j = 5; j > 0; j--)// compute the index b < 6! for the permutation in corner6 - { - int k = 0; - - while (tmpCorner6[j] != j) - { - rotateLeft(tmpCorner6, 0, j); - k++; - } - b = (j + 1) * b + k; - } - - return (short) (720 * a + b); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - void setURFtoDLF(short idx) - { - int x; - - int[] corner6 = { Corner.URF, Corner.UFL, Corner.ULB, Corner.UBR, Corner.DFR, Corner.DLF }; - int[] otherCorner = { Corner.DBL, Corner.DRB }; - int b = idx % 720; // Permutation - int a = idx / 720; // Combination - - for ( int c=Corner.URF; c<=Corner.DRB; c++) cp[c] = Corner.DRB;// Use DRB to invalidate all corners - - for (int j = 1, k; j < 6; j++)// generate permutation from index b - { - k = b % (j + 1); - b /= j + 1; - while (k-- > 0) rotateRight(corner6, 0, j); - } - - x = 5;// generate combination and set corners - - for (int j = Corner.DRB; j >= 0; j--) - if (a - Cnk(j, x + 1) >= 0) - { - cp[j] = corner6[x]; - a -= Cnk(j, x-- + 1); - } - - x = 0; - - for (int j = Corner.URF; j <= Corner.DRB; j++) - if (cp[j] == Corner.DRB) - cp[j] = otherCorner[x++]; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Permutation of the six edges UR,UF,UL,UB,DR,DF. - int getURtoDF() - { - int a = 0, x = 0; - // compute the index a < (12 choose 6) and the edge permutation. - - for (int j = Edge.UR; j <= Edge.BR; j++) - if (ep[j] <= Edge.DF) - { - a += Cnk(j, x + 1); - tmpEdge6[x++] = ep[j]; - } - - int b = 0; - - for (int j = 5; j > 0; j--)// compute the index b < 6! for the permutation in edge6 - { - int k = 0; - - while (tmpEdge6[j] != j) - { - rotateLeft(tmpEdge6, 0, j); - k++; - } - b = (j + 1) * b + k; - } - return 720 * a + b; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - void setURtoDF(int idx) - { - int x; - int[] edge6 = { Edge.UR, Edge.UF, Edge.UL, Edge.UB, Edge.DR, Edge.DF }; - int[] otherEdge = { Edge.DL, Edge.DB, Edge.FR, Edge.FL, Edge.BL, Edge.BR }; - int b = idx % 720; // Permutation - int a = idx / 720; // Combination - - for ( int e=Edge.UR; e<=Edge.BR; e++) ep[e] = Edge.BR;// Use BR to invalidate all edges - - for (int j = 1, k; j < 6; j++)// generate permutation from index b - { - k = b % (j + 1); - b /= j + 1; - while (k-- > 0) rotateRight(edge6, 0, j); - } - - x = 5;// generate combination and set edges - - for (int j = Edge.BR; j >= 0; j--) - if (a - Cnk(j, x + 1) >= 0) - { - ep[j] = edge6[x]; - a -= Cnk(j, x-- + 1); - } - - x = 0; // set the remaining edges DL..BR - - for (int j = Edge.UR; j <= Edge.BR; j++) - if (ep[j] == Edge.BR) - ep[j] = otherEdge[x++]; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Permutation of the six edges UR,UF,UL,UB,DR,DF - public static int getURtoDF(short idx1, short idx2) - { - CubieCube a = new CubieCube(); - CubieCube b = new CubieCube(); - a.setURtoUL(idx1); - b.setUBtoDF(idx2); - - for (int i = 0; i < 8; i++) - { - if (a.ep[i] != Edge.BR) - if (b.ep[i] != Edge.BR)// collision - return -1; - else - b.ep[i] = a.ep[i]; - } - - return b.getURtoDF(); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Permutation of the three edges UR,UF,UL - short getURtoUL() - { - int a = 0, x = 0; - // compute the index a < (12 choose 3) and the edge permutation. - for (int j = Edge.UR; j <= Edge.BR; j++) - if (ep[j] <= Edge.UL) - { - a += Cnk(j, x + 1); - tmpEdge3[x++] = ep[j]; - } - - int b = 0; - - for (int j = 2; j > 0; j--)// compute the index b < 3! for the permutation in edge3 - { - int k = 0; - while (tmpEdge3[j] != j) - { - rotateLeft(tmpEdge3, 0, j); - k++; - } - b = (j + 1) * b + k; - } - - return (short) (6 * a + b); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - void setURtoUL(short idx) - { - int x; - int[] edge3 = { Edge.UR, Edge.UF, Edge.UL }; - int b = idx % 6; // Permutation - int a = idx / 6; // Combination - - for (int e = Edge.UR; e <= Edge.BR; e++) ep[e] = Edge.BR;// Use BR to invalidate all edges - - for (int j = 1, k; j < 3; j++)// generate permutation from index b - { - k = b % (j + 1); - b /= j + 1; - - while (k-- > 0) rotateRight(edge3, 0, j); - } - - x = 2;// generate combination and set edges - - for (int j = Edge.BR; j >= 0; j--) - if (a - Cnk(j, x + 1) >= 0) - { - ep[j] = edge3[x]; - a -= Cnk(j, x-- + 1); - } - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Permutation of the three edges UB,DR,DF - short getUBtoDF() - { - int a = 0, x = 0; - // compute the index a < (12 choose 3) and the edge permutation. - - for (int j = Edge.UR; j <= Edge.BR; j++) - if (Edge.UB <= ep[j] && ep[j] <= Edge.DF) - { - a += Cnk(j, x + 1); - tmpEdge3[x++] = ep[j]; - } - - int b = 0; - - for (int j = 2; j > 0; j--)// compute the index b < 3! for the permutation in edge3 - { - int k = 0; - - while (tmpEdge3[j] != Edge.UB + j) - { - rotateLeft(tmpEdge3, 0, j); - k++; - } - b = (j + 1) * b + k; - } - - return (short) (6 * a + b); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - void setUBtoDF(short idx) - { - int x; - int[] edge3 = { Edge.UB, Edge.DR, Edge.DF }; - int b = idx % 6; // Permutation - int a = idx / 6; // Combination - - for (int e = Edge.UR; e <= Edge.BR; e++) ep[e] = Edge.BR;// Use BR to invalidate all edges - - for (int j = 1, k; j < 3; j++)// generate permutation from index b - { - k = b % (j + 1); - b /= j + 1; - - while (k-- > 0) rotateRight(edge3, 0, j); - } - - x = 2;// generate combination and set edges - - for (int j = Edge.BR; j >= 0; j--) - if (a - Cnk(j, x + 1) >= 0) - { - ep[j] = edge3[x]; - a -= Cnk(j, x-- + 1); - } - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - int getURFtoDLB() - { - int b = 0; - - for (int i = 0; i < 8; i++) tmpCorner8[i] = cp[i]; - - for (int j = 7; j > 0; j--)// compute the index b < 8! for the permutation in perm - { - int k = 0; - while (tmpCorner8[j] != j) - { - rotateLeft(tmpCorner8, 0, j); - k++; - } - b = (j + 1) * b + k; - } - - return b; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - void setURFtoDLB(int idx) - { - int[] perm = { Corner.URF, Corner.UFL, Corner.ULB, Corner.UBR, Corner.DFR, Corner.DLF, Corner.DBL, Corner.DRB }; - int k; - - for (int j = 1; j < 8; j++) - { - k = idx % (j + 1); - idx /= j + 1; - while (k-- > 0) rotateRight(perm, 0, j); - } - - int x = 7;// set corners - - for (int j = 7; j >= 0; j--) cp[j] = perm[x--]; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - int getURtoBR() - { - int b = 0; - - for (int i = 0; i < 12; i++) tmpEdge12[i] = ep[i]; - - for (int j = 11; j > 0; j--)// compute the index b < 12! for the permutation in perm - { - int k = 0; - - while (tmpEdge12[j] != j) - { - rotateLeft(tmpEdge12, 0, j); - k++; - } - b = (j + 1) * b + k; - } - - return b; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - void setURtoBR(int idx) - { - int[] perm = { Edge.UR, Edge.UF, Edge.UL, Edge.UB, Edge.DR, Edge.DF, Edge.DL, Edge.DB, Edge.FR, Edge.FL, Edge.BL, Edge.BR }; - int k; - - for (int j = 1; j < 12; j++) - { - k = idx % (j + 1); - idx /= j + 1; - - while (k-- > 0) rotateRight(perm, 0, j); - } - - int x = 11;// set edges - - for (int j = 11; j >= 0; j--) ep[j] = perm[x--]; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Check a cubiecube for solvability. Return the error code. - // 0: Cube is solvable - // -2: Not all 12 edges exist exactly once - // -3: Flip error: One edge has to be flipped - // -4: Not all corners exist exactly once - // -5: Twist error: One corner has to be twisted - // -6: Parity error: Two corners ore two edges have to be exchanged - int verify() - { - int sum = 0; - int[] edgeCount = new int[12]; - - for (int e = Edge.UR; e <= Edge.BR; e++) edgeCount[ep[e]]++; - - for (int i = 0; i < 12; i++) - if (edgeCount[i] != 1) - return -2; - - for (int i = 0; i < 12; i++) - sum += eo[i]; - - if (sum % 2 != 0) - return -3; - - int[] cornerCount = new int[8]; - - for ( int c=Corner.URF; c<=Corner.DRB; c++) cornerCount[cp[c]]++; - - for (int i = 0; i < 8; i++) - if (cornerCount[i] != 1) - return -4;// missing corners - - sum = 0; - - for (int i = 0; i < 8; i++) - sum += co[i]; - - if (sum % 3 != 0) - return -5;// twisted corner - - if ((edgeParity() ^ cornerParity()) != 0) - return -6;// parity error - - return 0;// cube ok - } -} \ No newline at end of file diff --git a/src/main/java/org/distorted/solvers/cube3/Edge.java b/src/main/java/org/distorted/solvers/cube3/Edge.java deleted file mode 100644 index 355ff6eb..00000000 --- a/src/main/java/org/distorted/solvers/cube3/Edge.java +++ /dev/null @@ -1,20 +0,0 @@ -package org.distorted.solvers.cube3; - -//+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -//Then names of the edge positions of the cube. Edge UR e.g., has an U(p) and R(ight) facelet. - -class Edge - { - public static final int UR=0; - public static final int UF=1; - public static final int UL=2; - public static final int UB=3; - public static final int DR=4; - public static final int DF=5; - public static final int DL=6; - public static final int DB=7; - public static final int FR=8; - public static final int FL=9; - public static final int BL=10; - public static final int BR=11; - } \ No newline at end of file diff --git a/src/main/java/org/distorted/solvers/cube3/FaceCube.java b/src/main/java/org/distorted/solvers/cube3/FaceCube.java deleted file mode 100644 index 032fa5f5..00000000 --- a/src/main/java/org/distorted/solvers/cube3/FaceCube.java +++ /dev/null @@ -1,129 +0,0 @@ -package org.distorted.solvers.cube3; - -//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -//Cube on the facelet level -class FaceCube { - public int[] f = new int[54]; - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Map the corner positions to facelet positions. cornerFacelet[URF.ordinal()][0] e.g. gives the position of the - // facelet in the URF corner position, which defines the orientation.
- // cornerFacelet[URF.ordinal()][1] and cornerFacelet[URF.ordinal()][2] give the position of the other two facelets - // of the URF corner (clockwise). - final static int[][] cornerFacelet = - { { Facelet.U9, Facelet.R1, Facelet.F3 }, { Facelet.U7, Facelet.F1, Facelet.L3 }, - { Facelet.U1, Facelet.L1, Facelet.B3 }, { Facelet.U3, Facelet.B1, Facelet.R3 }, - { Facelet.D3, Facelet.F9, Facelet.R7 }, { Facelet.D1, Facelet.L9, Facelet.F7 }, - { Facelet.D7, Facelet.B9, Facelet.L7 }, { Facelet.D9, Facelet.R9, Facelet.B7 } }; - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Map the edge positions to facelet positions. edgeFacelet[UR.ordinal()][0] e.g. gives the position of the facelet in - // the UR edge position, which defines the orientation.
- // edgeFacelet[UR.ordinal()][1] gives the position of the other facelet - final static int[][] edgeFacelet = - { { Facelet.U6, Facelet.R2 }, { Facelet.U8, Facelet.F2 }, { Facelet.U4, Facelet.L2 }, - { Facelet.U2, Facelet.B2 }, { Facelet.D6, Facelet.R8 }, { Facelet.D2, Facelet.F8 }, - { Facelet.D4, Facelet.L8 }, { Facelet.D8, Facelet.B8 }, { Facelet.F6, Facelet.R4 }, - { Facelet.F4, Facelet.L6 }, { Facelet.B6, Facelet.L4 }, { Facelet.B4, Facelet.R6 } }; - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Map the corner positions to facelet colors. - final static int[][] cornerColor = - { { Color.U, Color.R, Color.F }, { Color.U, Color.F, Color.L }, - { Color.U, Color.L, Color.B }, { Color.U, Color.B, Color.R }, - { Color.D, Color.F, Color.R }, { Color.D, Color.L, Color.F }, - { Color.D, Color.B, Color.L }, { Color.D, Color.R, Color.B } }; - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Map the edge positions to facelet colors. - final static int[][] edgeColor = - { { Color.U, Color.R }, { Color.U, Color.F }, { Color.U, Color.L }, - { Color.U, Color.B }, { Color.D, Color.R }, { Color.D, Color.F }, - { Color.D, Color.L }, { Color.D, Color.B }, { Color.F, Color.R }, - { Color.F, Color.L }, { Color.B, Color.L }, { Color.B, Color.R } }; - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - FaceCube() - { - String s = "UUUUUUUUURRRRRRRRRFFFFFFFFFDDDDDDDDDLLLLLLLLLBBBBBBBBB"; - - for (int i = 0; i < 54; i++) - f[i] = Color.toInt(s.substring(i, i + 1)); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Construct a facelet cube from a string - FaceCube(String cubeString) - { - for (int i = 0; i < cubeString.length(); i++) - f[i] = Color.toInt(cubeString.substring(i, i + 1)); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Gives string representation of a facelet cube - String to_String() - { - String s = ""; - - for (int i = 0; i < 54; i++) - s += Color.toString(f[i]); - - return s; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Gives CubieCube representation of a faceletcube - CubieCube toCubieCube() - { - byte ori; - CubieCube ccRet = new CubieCube(); - - for (int i = 0; i < 8; i++) ccRet.cp[i] = Corner.URF; // invalidate corners - for (int i = 0; i < 12; i++) ccRet.ep[i] = Edge.UR; // and edges - - int col1, col2; - - for ( int i=Corner.URF; i<=Corner.DRB; i++) - { - // get the colors of the cubie at corner i, starting with U/D - for (ori = 0; ori < 3; ori++) - if (f[cornerFacelet[i][ori]] == Color.U || f[cornerFacelet[i][ori]] == Color.D) - break; - - col1 = f[cornerFacelet[i][(ori + 1) % 3]]; - col2 = f[cornerFacelet[i][(ori + 2) % 3]]; - - for ( int j=Corner.URF; j<=Corner.DRB; j++) - { - if (col1 == cornerColor[j][1] && col2 == cornerColor[j][2]) - { - // in cornerposition i we have cornercubie j - ccRet.cp[i] = j; - ccRet.co[i] = (byte) (ori % 3); - break; - } - } - } - - for ( int i=Edge.UR; i<=Edge.BR; i++) - { - for ( int j=Edge.UR; j<=Edge.BR; j++) - { - if (f[edgeFacelet[i][0]] == edgeColor[j][0] && f[edgeFacelet[i][1]] == edgeColor[j][1]) - { - ccRet.ep[i] = j; - ccRet.eo[i] = 0; - break; - } - if (f[edgeFacelet[i][0]] == edgeColor[j][1] && f[edgeFacelet[i][1]] == edgeColor[j][0]) - { - ccRet.ep[i] = j; - ccRet.eo[i] = 1; - break; - } - } - } - - return ccRet; - }; -} diff --git a/src/main/java/org/distorted/solvers/cube3/Facelet.java b/src/main/java/org/distorted/solvers/cube3/Facelet.java deleted file mode 100644 index 154907e0..00000000 --- a/src/main/java/org/distorted/solvers/cube3/Facelet.java +++ /dev/null @@ -1,96 +0,0 @@ -package org.distorted.solvers.cube3; - -/** - * 
- * The names of the facelet positions of the cube
- *             |************|
- *             |*U1**U2**U3*|
- *             |************|
- *             |*U4**U5**U6*|
- *             |************|
- *             |*U7**U8**U9*|
- *             |************|
- * ************|************|************|************|
- * *L1**L2**L3*|*F1**F2**F3*|*R1**R2**F3*|*B1**B2**B3*|
- * ************|************|************|************|
- * *L4**L5**L6*|*F4**F5**F6*|*R4**R5**R6*|*B4**B5**B6*|
- * ************|************|************|************|
- * *L7**L8**L9*|*F7**F8**F9*|*R7**R8**R9*|*B7**B8**B9*|
- * ************|************|************|************|
- *             |************|
- *             |*D1**D2**D3*|
- *             |************|
- *             |*D4**D5**D6*|
- *             |************|
- *             |*D7**D8**D9*|
- *             |************|
- *
- * - *A cube definition string "UBL..." means for example: In position U1 we have the U-color, in position U2 we have the - * B-color, in position U3 we have the L color etc. according to the order U1, U2, U3, U4, U5, U6, U7, U8, U9, R1, R2, - * R3, R4, R5, R6, R7, R8, R9, F1, F2, F3, F4, F5, F6, F7, F8, F9, D1, D2, D3, D4, D5, D6, D7, D8, D9, L1, L2, L3, L4, - * L5, L6, L7, L8, L9, B1, B2, B3, B4, B5, B6, B7, B8, B9 of the enum constants. - */ - -class Facelet - { - public static int U1 = 0; - public static int U2 = 1; - public static int U3 = 2; - public static int U4 = 3; - public static int U5 = 4; - public static int U6 = 5; - public static int U7 = 6; - public static int U8 = 7; - public static int U9 = 8; - - public static int R1 = 9; - public static int R2 = 10; - public static int R3 = 11; - public static int R4 = 12; - public static int R5 = 13; - public static int R6 = 14; - public static int R7 = 15; - public static int R8 = 16; - public static int R9 = 17; - - public static int F1 = 18; - public static int F2 = 19; - public static int F3 = 20; - public static int F4 = 21; - public static int F5 = 22; - public static int F6 = 23; - public static int F7 = 24; - public static int F8 = 25; - public static int F9 = 26; - - public static int D1 = 27; - public static int D2 = 28; - public static int D3 = 29; - public static int D4 = 30; - public static int D5 = 31; - public static int D6 = 32; - public static int D7 = 33; - public static int D8 = 34; - public static int D9 = 35; - - public static int L1 = 36; - public static int L2 = 37; - public static int L3 = 38; - public static int L4 = 39; - public static int L5 = 40; - public static int L6 = 41; - public static int L7 = 42; - public static int L8 = 43; - public static int L9 = 44; - - public static int B1 = 45; - public static int B2 = 46; - public static int B3 = 47; - public static int B4 = 48; - public static int B5 = 49; - public static int B6 = 50; - public static int B7 = 51; - public static int B8 = 52; - public static int B9 = 53; - } \ No newline at end of file diff --git a/src/main/java/org/distorted/solvers/cube3/RubikSolverColor.java b/src/main/java/org/distorted/solvers/cube3/RubikSolverColor.java new file mode 100644 index 00000000..9d6ecd3c --- /dev/null +++ b/src/main/java/org/distorted/solvers/cube3/RubikSolverColor.java @@ -0,0 +1,65 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Copyright 2008 Leszek Koltunski // +// // +// This file is part of Magic Cube. // +// // +// Magic Cube is free software: you can redistribute it and/or modify // +// it under the terms of the GNU General Public License as published by // +// the Free Software Foundation, either version 2 of the License, or // +// (at your option) any later version. // +// // +// Magic Cube is distributed in the hope that it will be useful, // +// but WITHOUT ANY WARRANTY; without even the implied warranty of // +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // +// GNU General Public License for more details. // +// // +// You should have received a copy of the GNU General Public License // +// along with Magic Cube. If not, see . // +/////////////////////////////////////////////////////////////////////////////////////////////////// + +package org.distorted.solvers.cube3; + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Names the colors of the cube facelets + +class RubikSolverColor + { + public static final int U=0; + public static final int R=1; + public static final int F=2; + public static final int D=3; + public static final int L=4; + public static final int B=5; + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + public static String toString(int i) + { + switch(i) + { + case U: return "U"; + case R: return "R"; + case F: return "F"; + case D: return "D"; + case L: return "L"; + case B: return "B"; + default: return "?"; + } + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + public static int toInt(String s) + { + switch(s.charAt(0)) + { + case 'U': return U; + case 'R': return R; + case 'F': return F; + case 'D': return D; + case 'L': return L; + case 'B': return B; + default: return -1; + } + } + } \ No newline at end of file diff --git a/src/main/java/org/distorted/solvers/cube3/RubikSolverCoordCube.java b/src/main/java/org/distorted/solvers/cube3/RubikSolverCoordCube.java new file mode 100644 index 00000000..a518bd1a --- /dev/null +++ b/src/main/java/org/distorted/solvers/cube3/RubikSolverCoordCube.java @@ -0,0 +1,260 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Copyright 2008 Leszek Koltunski // +// // +// This file is part of Magic Cube. // +// // +// Magic Cube is free software: you can redistribute it and/or modify // +// it under the terms of the GNU General Public License as published by // +// the Free Software Foundation, either version 2 of the License, or // +// (at your option) any later version. // +// // +// Magic Cube is distributed in the hope that it will be useful, // +// but WITHOUT ANY WARRANTY; without even the implied warranty of // +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // +// GNU General Public License for more details. // +// // +// You should have received a copy of the GNU General Public License // +// along with Magic Cube. If not, see . // +/////////////////////////////////////////////////////////////////////////////////////////////////// + +package org.distorted.solvers.cube3; + +import java.io.InputStream; +import android.content.res.Resources; + +/////////////////////////////////////////////////////////////////////////////////////////////////// + +class RubikSolverCoordCube +{ + static final short N_TWIST = 2187; // 3^7 possible corner orientations + static final short N_FLIP = 2048; // 2^11 possible edge flips + static final short N_SLICE1 = 495; // 12 choose 4 possible positions of FR,FL,BL,BR edges + static final short N_SLICE2 = 24; // 4! permutations of FR,FL,BL,BR edges in phase2 + static final short N_PARITY = 2; // 2 possible corner parities + static final short N_URFtoDLF = 20160; // 8!/(8-6)! permutation of URF,UFL,ULB,UBR,DFR,DLF corners + static final short N_FRtoBR = 11880; // 12!/(12-4)! permutation of FR,FL,BL,BR edges + static final short N_URtoUL = 1320; // 12!/(12-3)! permutation of UR,UF,UL edges + static final short N_UBtoDF = 1320; // 12!/(12-3)! permutation of UB,DR,DF edges + static final short N_URtoDF = 20160; // 8!/(8-6)! permutation of UR,UF,UL,UB,DR,DF edges in phase2 + static final int N_URFtoDLB = 40320; // 8! permutations of the corners + static final int N_URtoBR = 479001600;// 8! permutations of the corners + static final short N_MOVE = 18; + + // All coordinates are 0 for a solved cube except for UBtoDF, which is 114 + short twist; + short flip; + short parity; + short FRtoBR; + short URFtoDLF; + short URtoUL; + short UBtoDF; + int URtoDF; + + private static final boolean[] init = new boolean[12]; + + static + { + for(int i=0; i<12; i++ ) init[i] = false; + } + + // Phase 1 move tables + // Move table for the twists of the corners. twist < 2187 in phase 2; twist = 0 in phase 2. + private static final byte[] twistMove = new byte[2*N_TWIST*N_MOVE]; + + // Move table for the flips of the edges. flip < 2048 in phase 1; flip = 0 in phase 2. + private static final byte[] flipMove = new byte[2*N_FLIP*N_MOVE]; + + // Parity of the corner permutation. This is the same as the parity for the edge permutation of a valid cube. + // parity has values 0 and 1 + static short[][] parityMove = { + { 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1 }, + { 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0 } + }; + + // Phase 1 and 2 movetable + // Move table for the four UD-slice edges FR, FL, Bl and BR + // FRtoBRMove < 11880 in phase 1; FRtoBRMove < 24 in phase 2; FRtoBRMove = 0 for solved cube + private static final byte[] FRtoBR_Move = new byte[2*N_FRtoBR*N_MOVE]; + + // Phase 1 and 2 movetable + // Move table for permutation of six corners. The positions of the DBL and DRB corners are determined by the parity. + // URFtoDLF < 20160 in phase 1; URFtoDLF < 20160 in phase 2; URFtoDLF = 0 for solved cube. + private static final byte[] URFtoDLF_Move = new byte[2*N_URFtoDLF*N_MOVE]; + + // Move table for the permutation of six U-face and D-face edges in phase2. The positions of the DL and DB edges are + // determined by the parity. + // URtoDF < 665280 in phase 1; URtoDF < 20160 in phase 2; URtoDF = 0 for solved cube. + private static final byte[] URtoDF_Move = new byte[2*N_URtoDF*N_MOVE]; + + // Helper move tables to compute URtoDF for the beginning of phase2 + // Move table for the three edges UR,UF and UL in phase1. + private static final byte[] URtoUL_Move = new byte[2*N_URtoUL*N_MOVE]; + + // Move table for the three edges UB,DR and DF in phase1. + private static final byte[] UBtoDF_Move = new byte[2*N_UBtoDF*N_MOVE]; + + // Table to merge the coordinates of the UR,UF,UL and UB,DR,DF edges at the beginning of phase2 + private static final byte[] MergeURtoULandUBtoDF = new byte[2*336*336]; + + // Pruning tables for the search + // Pruning table for the permutation of the corners and the UD-slice edges in phase2. + // The pruning table entries give a lower estimation for the number of moves to reach the solved cube. + public static byte[] Slice_URFtoDLF_Parity_Prun = new byte[N_SLICE2*N_URFtoDLF*N_PARITY / 2]; + + // Pruning table for the permutation of the edges in phase2. + // The pruning table entries give a lower estimation for the number of moves to reach the solved cube. + public static byte[] Slice_URtoDF_Parity_Prun = new byte[N_SLICE2*N_URtoDF*N_PARITY / 2]; + + // Pruning table for the twist of the corners and the position (not permutation) of the UD-slice edges in phase1 + // The pruning table entries give a lower estimation for the number of moves to reach the H-subgroup. + public static byte[] Slice_Twist_Prun = new byte[N_SLICE1*N_TWIST / 2 + 1]; + + // Pruning table for the flip of the edges and the position (not permutation) of the UD-slice edges in phase1 + // The pruning table entries give a lower estimation for the number of moves to reach the H-subgroup. + public static byte[] Slice_Flip_Prun = new byte[N_SLICE1*N_FLIP / 2]; + + private static final int[] resourceTable = new int[] + { + org.distorted.main.R.raw.cube3solver_table1, + org.distorted.main.R.raw.cube3solver_table2, + org.distorted.main.R.raw.cube3solver_table3, + org.distorted.main.R.raw.cube3solver_table4, + org.distorted.main.R.raw.cube3solver_table5, + org.distorted.main.R.raw.cube3solver_table6, + org.distorted.main.R.raw.cube3solver_table7, + org.distorted.main.R.raw.cube3solver_table8, + org.distorted.main.R.raw.cube3solver_table9, + org.distorted.main.R.raw.cube3solver_table10, + org.distorted.main.R.raw.cube3solver_table11, + org.distorted.main.R.raw.cube3solver_table12 + }; + + private static final byte[][] tableOfTables = new byte[][] + { + twistMove, + flipMove, + FRtoBR_Move, + URFtoDLF_Move, + URtoDF_Move, + URtoUL_Move, + UBtoDF_Move, + MergeURtoULandUBtoDF, + Slice_URFtoDLF_Parity_Prun, + Slice_URtoDF_Parity_Prun, + Slice_Twist_Prun, + Slice_Flip_Prun + }; + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Generate a CoordCube from a CubieCube + + RubikSolverCoordCube(RubikSolverCubieCube c) + { + twist = c.getTwist(); + flip = c.getFlip(); + parity = c.cornerParity(); + FRtoBR = c.getFRtoBR(); + URFtoDLF = c.getURFtoDLF(); + URtoUL = c.getURtoUL(); + UBtoDF = c.getUBtoDF(); + URtoDF = c.getURtoDF();// only needed in phase2 + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + static byte getPruning(byte[] table, int index) + { + byte ret = table[index/2]; + return (byte) ( ((index&1)==0) ? (ret&0x0f) : ((ret&0xf0)>>>4) ); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + public static short getTwistMove(int a,int b) + { + return getTable(a,b,twistMove,N_MOVE); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + public static short getFlipMove(int a,int b) + { + return getTable(a,b,flipMove,N_MOVE); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + public static short getFRtoBR_Move(int a,int b) + { + return getTable(a,b,FRtoBR_Move,N_MOVE); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + public static short getURFtoDLF_Move(int a,int b) + { + return getTable(a,b,URFtoDLF_Move,N_MOVE); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + public static short getURtoDF_Move(int a,int b) + { + return getTable(a,b,URtoDF_Move,N_MOVE); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + public static short getURtoUL_Move(int a,int b) + { + return getTable(a,b,URtoUL_Move,N_MOVE); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + public static short getUBtoDF_Move(int a,int b) + { + return getTable(a,b,UBtoDF_Move,N_MOVE); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + public static short getMergeURtoULandUBtoDF(int a,int b) + { + return getTable(a,b,MergeURtoULandUBtoDF,336); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + private static short getTable(int a,int b, byte[] table, int size) + { + short upperS = table[2*(a*size+b)]; + short lowerS = table[2*(a*size+b)+1]; + + if( upperS<0 ) upperS+=256; + if( lowerS<0 ) lowerS+=256; + + return (short)( (upperS<<8) + lowerS ); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + public static void initialize(Resources res, int index) + { + if( !init[index] ) + { + try + { + byte[] table = tableOfTables[index]; + InputStream is = res.openRawResource(resourceTable[index]); + is.read( table, 0, table.length); + } + catch(Exception ioe) + { + System.out.println("error reading table"+index); + } + + init[index]=true; + } + } +} diff --git a/src/main/java/org/distorted/solvers/cube3/RubikSolverCorner.java b/src/main/java/org/distorted/solvers/cube3/RubikSolverCorner.java new file mode 100644 index 00000000..eb6f1980 --- /dev/null +++ b/src/main/java/org/distorted/solvers/cube3/RubikSolverCorner.java @@ -0,0 +1,35 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Copyright 2008 Leszek Koltunski // +// // +// This file is part of Magic Cube. // +// // +// Magic Cube is free software: you can redistribute it and/or modify // +// it under the terms of the GNU General Public License as published by // +// the Free Software Foundation, either version 2 of the License, or // +// (at your option) any later version. // +// // +// Magic Cube is distributed in the hope that it will be useful, // +// but WITHOUT ANY WARRANTY; without even the implied warranty of // +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // +// GNU General Public License for more details. // +// // +// You should have received a copy of the GNU General Public License // +// along with Magic Cube. If not, see . // +/////////////////////////////////////////////////////////////////////////////////////////////////// + +package org.distorted.solvers.cube3; + +/////////////////////////////////////////////////////////////////////////////////////////////////// +//The names of the corner positions of the cube. Corner URF e.g., has an U(p), a R(ight) and a F(ront) facelet + +class RubikSolverCorner + { + public static final int URF =0; + public static final int UFL =1; + public static final int ULB =2; + public static final int UBR =3; + public static final int DFR =4; + public static final int DLF =5; + public static final int DBL =6; + public static final int DRB =7; + } \ No newline at end of file diff --git a/src/main/java/org/distorted/solvers/cube3/RubikSolverCubieCube.java b/src/main/java/org/distorted/solvers/cube3/RubikSolverCubieCube.java new file mode 100644 index 00000000..3e716dcb --- /dev/null +++ b/src/main/java/org/distorted/solvers/cube3/RubikSolverCubieCube.java @@ -0,0 +1,518 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Copyright 2008 Leszek Koltunski // +// // +// This file is part of Magic Cube. // +// // +// Magic Cube is free software: you can redistribute it and/or modify // +// it under the terms of the GNU General Public License as published by // +// the Free Software Foundation, either version 2 of the License, or // +// (at your option) any later version. // +// // +// Magic Cube is distributed in the hope that it will be useful, // +// but WITHOUT ANY WARRANTY; without even the implied warranty of // +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // +// GNU General Public License for more details. // +// // +// You should have received a copy of the GNU General Public License // +// along with Magic Cube. If not, see . // +/////////////////////////////////////////////////////////////////////////////////////////////////// + +package org.distorted.solvers.cube3; + +/////////////////////////////////////////////////////////////////////////////////////////////////// + +class RubikSolverCubieCube + { + private static final int[][] cnk = new int[12][7]; + private static final int[] tmpEdge6 = new int[6]; + private static final int[] tmpEdge4 = new int[4]; + private static final int[] tmpEdge3 = new int[3]; + private static final int[] tmpCorner6= new int[6]; + + // corner permutation + int[] cp = { RubikSolverCorner.URF, RubikSolverCorner.UFL, RubikSolverCorner.ULB, RubikSolverCorner.UBR, RubikSolverCorner.DFR, RubikSolverCorner.DLF, RubikSolverCorner.DBL, RubikSolverCorner.DRB }; + + // corner orientation + byte[] co = { 0, 0, 0, 0, 0, 0, 0, 0 }; + + // edge permutation + int[] ep = { RubikSolverEdge.UR, RubikSolverEdge.UF, RubikSolverEdge.UL, RubikSolverEdge.UB, RubikSolverEdge.DR, RubikSolverEdge.DF, RubikSolverEdge.DL, RubikSolverEdge.DB, RubikSolverEdge.FR, RubikSolverEdge.FL, RubikSolverEdge.BL, RubikSolverEdge.BR }; + + // edge orientation + byte[] eo = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; + + // Moves on the cubie level + private static final int[] cpU = { RubikSolverCorner.UBR, RubikSolverCorner.URF, RubikSolverCorner.UFL, RubikSolverCorner.ULB, RubikSolverCorner.DFR, RubikSolverCorner.DLF, RubikSolverCorner.DBL, RubikSolverCorner.DRB }; + private static final byte[] coU = { 0, 0, 0, 0, 0, 0, 0, 0 }; + private static final int[] epU = { RubikSolverEdge.UB, RubikSolverEdge.UR, RubikSolverEdge.UF, RubikSolverEdge.UL, RubikSolverEdge.DR, RubikSolverEdge.DF, RubikSolverEdge.DL, RubikSolverEdge.DB, RubikSolverEdge.FR, RubikSolverEdge.FL, RubikSolverEdge.BL, RubikSolverEdge.BR }; + private static final byte[] eoU = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; + + private static final int[] cpR = { RubikSolverCorner.DFR, RubikSolverCorner.UFL, RubikSolverCorner.ULB, RubikSolverCorner.URF, RubikSolverCorner.DRB, RubikSolverCorner.DLF, RubikSolverCorner.DBL, RubikSolverCorner.UBR }; + private static final byte[] coR = { 2, 0, 0, 1, 1, 0, 0, 2 }; + private static final int[] epR = { RubikSolverEdge.FR, RubikSolverEdge.UF, RubikSolverEdge.UL, RubikSolverEdge.UB, RubikSolverEdge.BR, RubikSolverEdge.DF, RubikSolverEdge.DL, RubikSolverEdge.DB, RubikSolverEdge.DR, RubikSolverEdge.FL, RubikSolverEdge.BL, RubikSolverEdge.UR }; + private static final byte[] eoR = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; + + private static final int[] cpF = { RubikSolverCorner.UFL, RubikSolverCorner.DLF, RubikSolverCorner.ULB, RubikSolverCorner.UBR, RubikSolverCorner.URF, RubikSolverCorner.DFR, RubikSolverCorner.DBL, RubikSolverCorner.DRB }; + private static final byte[] coF = { 1, 2, 0, 0, 2, 1, 0, 0 }; + private static final int[] epF = { RubikSolverEdge.UR, RubikSolverEdge.FL, RubikSolverEdge.UL, RubikSolverEdge.UB, RubikSolverEdge.DR, RubikSolverEdge.FR, RubikSolverEdge.DL, RubikSolverEdge.DB, RubikSolverEdge.UF, RubikSolverEdge.DF, RubikSolverEdge.BL, RubikSolverEdge.BR }; + private static final byte[] eoF = { 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0 }; + + private static final int[] cpD = { RubikSolverCorner.URF, RubikSolverCorner.UFL, RubikSolverCorner.ULB, RubikSolverCorner.UBR, RubikSolverCorner.DLF, RubikSolverCorner.DBL, RubikSolverCorner.DRB, RubikSolverCorner.DFR }; + private static final byte[] coD = { 0, 0, 0, 0, 0, 0, 0, 0 }; + private static final int[] epD = { RubikSolverEdge.UR, RubikSolverEdge.UF, RubikSolverEdge.UL, RubikSolverEdge.UB, RubikSolverEdge.DF, RubikSolverEdge.DL, RubikSolverEdge.DB, RubikSolverEdge.DR, RubikSolverEdge.FR, RubikSolverEdge.FL, RubikSolverEdge.BL, RubikSolverEdge.BR }; + private static final byte[] eoD = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; + + private static final int[] cpL = { RubikSolverCorner.URF, RubikSolverCorner.ULB, RubikSolverCorner.DBL, RubikSolverCorner.UBR, RubikSolverCorner.DFR, RubikSolverCorner.UFL, RubikSolverCorner.DLF, RubikSolverCorner.DRB }; + private static final byte[] coL = { 0, 1, 2, 0, 0, 2, 1, 0 }; + private static final int[] epL = { RubikSolverEdge.UR, RubikSolverEdge.UF, RubikSolverEdge.BL, RubikSolverEdge.UB, RubikSolverEdge.DR, RubikSolverEdge.DF, RubikSolverEdge.FL, RubikSolverEdge.DB, RubikSolverEdge.FR, RubikSolverEdge.UL, RubikSolverEdge.DL, RubikSolverEdge.BR }; + private static final byte[] eoL = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; + + private static final int[] cpB = { RubikSolverCorner.URF, RubikSolverCorner.UFL, RubikSolverCorner.UBR, RubikSolverCorner.DRB, RubikSolverCorner.DFR, RubikSolverCorner.DLF, RubikSolverCorner.ULB, RubikSolverCorner.DBL }; + private static final byte[] coB = { 0, 0, 1, 2, 0, 0, 2, 1 }; + private static final int[] epB = { RubikSolverEdge.UR, RubikSolverEdge.UF, RubikSolverEdge.UL, RubikSolverEdge.BR, RubikSolverEdge.DR, RubikSolverEdge.DF, RubikSolverEdge.DL, RubikSolverEdge.BL, RubikSolverEdge.FR, RubikSolverEdge.FL, RubikSolverEdge.UB, RubikSolverEdge.DB }; + private static final byte[] eoB = { 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1 }; + + // this CubieCube array represents the 6 basic cube moves + static RubikSolverCubieCube[] moveCube = new RubikSolverCubieCube[6]; + + static + { + moveCube[0] = new RubikSolverCubieCube(); + moveCube[0].cp = cpU; + moveCube[0].co = coU; + moveCube[0].ep = epU; + moveCube[0].eo = eoU; + + moveCube[1] = new RubikSolverCubieCube(); + moveCube[1].cp = cpR; + moveCube[1].co = coR; + moveCube[1].ep = epR; + moveCube[1].eo = eoR; + + moveCube[2] = new RubikSolverCubieCube(); + moveCube[2].cp = cpF; + moveCube[2].co = coF; + moveCube[2].ep = epF; + moveCube[2].eo = eoF; + + moveCube[3] = new RubikSolverCubieCube(); + moveCube[3].cp = cpD; + moveCube[3].co = coD; + moveCube[3].ep = epD; + moveCube[3].eo = eoD; + + moveCube[4] = new RubikSolverCubieCube(); + moveCube[4].cp = cpL; + moveCube[4].co = coL; + moveCube[4].ep = epL; + moveCube[4].eo = eoL; + + moveCube[5] = new RubikSolverCubieCube(); + moveCube[5].cp = cpB; + moveCube[5].co = coB; + moveCube[5].ep = epB; + moveCube[5].eo = eoB; + } + + static + { + for(int n=0; n<12; n++) + for(int k=0; k<7; k++) + cnk[n][k] = -1; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + RubikSolverCubieCube() + { + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// n choose k + + static int Cnk(int n, int k) + { + if( cnk[n][k]<0 ) + { + int i, j, s; + + if (k > n ) { cnk[n][k]=0; return 0; } + if (k > n/2) k = n-k; + + for(s=1, i=n, j=1; i!=n-k; i--, j++) + { + s *= i; + s /= j; + } + cnk[n][k]= s; + } + + return cnk[n][k]; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Left rotation of all array elements between 0 and r + + static void rotateLeft(int[] arr, int r) + { + int tmp = arr[0]; + for (int i=0; i 0; i--) arr[i] = arr[i - 1]; + arr[0] = tmp; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// return cube in facelet representation + + RubikSolverFaceCube toFaceCube() + { + RubikSolverFaceCube fcRet = new RubikSolverFaceCube(); + + for(int c = RubikSolverCorner.URF; c<= RubikSolverCorner.DRB; c++) + { + int j = cp[c]; // corner cubie with index j is at corner position with index i + byte ori = co[c];// orientation of this cubie + + for( int n=0; n<3; n++) + fcRet.f[RubikSolverFaceCube.cornerFacelet[c][(n + ori) % 3]] = RubikSolverFaceCube.cornerColor[j][n]; + } + + for(int e = RubikSolverEdge.UR; e<= RubikSolverEdge.BR; e++) + { + int j = ep[e]; // edge cubie with index j is at edge position with index i + byte ori = eo[e];// orientation of this cubie + + for( int n=0; n<2; n++) + fcRet.f[RubikSolverFaceCube.edgeFacelet[e][(n + ori) % 2]] = RubikSolverFaceCube.edgeColor[j][n]; + } + + return fcRet; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// return the twist of the 8 corners. 0 <= twist < 3^7 + + short getTwist() + { + short ret = 0; + + for(int i = RubikSolverCorner.URF; i< RubikSolverCorner.DRB; i++) + ret = (short) (3*ret+co[i]); + + return ret; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + void setTwist(short twist) + { + int twistParity = 0; + + for (int i = RubikSolverCorner.DRB-1; i>= RubikSolverCorner.URF; i--) + { + twistParity += co[i] = (byte) (twist%3); + twist /= 3; + } + co[RubikSolverCorner.DRB] = (byte) ((3 - twistParity % 3) % 3); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// return the flip of the 12 edges. 0<= flip < 2^11 + + short getFlip() + { + short ret = 0; + + for (int i = RubikSolverEdge.UR; i< RubikSolverEdge.BR; i++) + ret = (short) (2 * ret + eo[i]); + + return ret; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + void setFlip(short flip) + { + int flipParity = 0; + + for (int i = RubikSolverEdge.BR-1; i>= RubikSolverEdge.UR; i--) + { + flipParity += eo[i] = (byte) (flip % 2); + flip /= 2; + } + eo[RubikSolverEdge.BR] = (byte) ((2 - flipParity % 2) % 2); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Parity of the corner permutation + + short cornerParity() + { + int s = 0; + + for (int i = RubikSolverCorner.DRB; i>= RubikSolverCorner.URF+1; i--) + for (int j = i - 1; j >= RubikSolverCorner.URF; j--) + if (cp[j] > cp[i]) s++; + + return (short) (s%2); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Parity of the edges permutation. Parity of corners and edges are the same if the cube is solvable. + + short edgeParity() + { + int s = 0; + + for (int i = RubikSolverEdge.BR; i >= RubikSolverEdge.UR+1; i--) + for (int j = i - 1; j >= RubikSolverEdge.UR; j--) + if (ep[j] > ep[i]) s++; + + return (short) (s%2); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// permutation of the UD-slice edges FR,FL,BL and BR + + short getFRtoBR() + { + int a = 0, x = 0; + + // compute the index a < (12 choose 4) and the permutation array perm. + for(int j = RubikSolverEdge.BR; j >= RubikSolverEdge.UR; j--) + if (RubikSolverEdge.FR <= ep[j] && ep[j] <= RubikSolverEdge.BR) + { + a += Cnk(11-j, x+1); + tmpEdge4[3-x++] = ep[j]; + } + + int b = 0; + for( int j=3; j>0; j--) // compute the index b < 4! for the permutation in perm + { + int k = 0; + while (tmpEdge4[j] != j+8) + { + rotateLeft(tmpEdge4,j); + k++; + } + b = (j+1)*b + k; + } + + return (short) (24*a+b); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Permutation of all corners except DBL and DRB + + short getURFtoDLF() + { + int a = 0, x = 0; + + // compute the index a < (8 choose 6) and the corner permutation. + for(int j = RubikSolverCorner.URF; j<= RubikSolverCorner.DRB; j++) + if( cp[j] <= RubikSolverCorner.DLF ) + { + a += Cnk(j, x+1); + tmpCorner6[x++] = cp[j]; + } + + int b = 0; + + for( int j=5; j>0; j--) // compute the index b < 6! for the permutation in corner6 + { + int k = 0; + + while (tmpCorner6[j] != j) + { + rotateLeft(tmpCorner6,j); + k++; + } + b = (j+1)*b + k; + } + + return (short) (720*a+b); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Permutation of the six edges UR,UF,UL,UB,DR,DF. + + int getURtoDF() + { + int a = 0, x = 0; + // compute the index a < (12 choose 6) and the edge permutation. + + for(int j = RubikSolverEdge.UR; j<= RubikSolverEdge.BR; j++) + if (ep[j] <= RubikSolverEdge.DF) + { + a += Cnk(j, x+1); + tmpEdge6[x++] = ep[j]; + } + + int b = 0; + + for (int j=5; j>0; j--)// compute the index b < 6! for the permutation in edge6 + { + int k = 0; + + while (tmpEdge6[j] != j) + { + rotateLeft(tmpEdge6,j); + k++; + } + b = (j+1)*b + k; + } + return 720*a+b; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Permutation of the three edges UR,UF,UL + + short getURtoUL() + { + int a=0, x=0; + + // compute the index a < (12 choose 3) and the edge permutation. + for(int j = RubikSolverEdge.UR; j<= RubikSolverEdge.BR; j++) + if (ep[j] <= RubikSolverEdge.UL) + { + a += Cnk(j, x + 1); + tmpEdge3[x++] = ep[j]; + } + + int b=0; + + for( int j=2; j>0; j--)// compute the index b < 3! for the permutation in edge3 + { + int k = 0; + while (tmpEdge3[j] != j) + { + rotateLeft(tmpEdge3,j); + k++; + } + b = (j+1)*b+k; + } + + return (short) (6*a+b); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Permutation of the three edges UB,DR,DF + + short getUBtoDF() + { + int a=0, x=0; + // compute the index a < (12 choose 3) and the edge permutation. + + for(int j = RubikSolverEdge.UR; j<= RubikSolverEdge.BR; j++) + if (RubikSolverEdge.UB <= ep[j] && ep[j] <= RubikSolverEdge.DF) + { + a += Cnk(j, x+1); + tmpEdge3[x++] = ep[j]; + } + + int b=0; + + for (int j=2; j>0; j--) // compute the index b < 3! for the permutation in edge3 + { + int k=0; + + while (tmpEdge3[j] != RubikSolverEdge.UB + j) + { + rotateLeft(tmpEdge3,j); + k++; + } + b = (j+1)*b+k; + } + + return (short) (6*a+b); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + void setURFtoDLB(int idx) + { + int[] perm = { RubikSolverCorner.URF, RubikSolverCorner.UFL, RubikSolverCorner.ULB, RubikSolverCorner.UBR, RubikSolverCorner.DFR, RubikSolverCorner.DLF, RubikSolverCorner.DBL, RubikSolverCorner.DRB }; + int k; + + for( int j=1; j<8; j++) + { + k = idx % (j+1); + idx /= j+1; + while (k-- > 0) rotateRight(perm,j); + } + + int x=7;// set corners + + for( int j=7; j>=0; j--) cp[j] = perm[x--]; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + void setURtoBR(int idx) + { + int[] perm = { RubikSolverEdge.UR, RubikSolverEdge.UF, RubikSolverEdge.UL, RubikSolverEdge.UB, RubikSolverEdge.DR, RubikSolverEdge.DF, RubikSolverEdge.DL, RubikSolverEdge.DB, RubikSolverEdge.FR, RubikSolverEdge.FL, RubikSolverEdge.BL, RubikSolverEdge.BR }; + int k; + + for( int j=1; j<12; j++) + { + k = idx % (j+1); + idx /= j+1; + + while (k-- > 0) rotateRight(perm,j); + } + + int x=11;// set edges + + for( int j=11; j>=0; j--) ep[j] = perm[x--]; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Check a cubie cube for solvability. Return the error code. +// 0: Cube is solvable +// -2: Not all 12 edges exist exactly once +// -3: Flip error: One edge has to be flipped +// -4: Not all corners exist exactly once +// -5: Twist error: One corner has to be twisted +// -6: Parity error: Two corners ore two edges have to be exchanged + + int verify() + { + int sum = 0; + int[] edgeCount = new int[12]; + + for (int e = RubikSolverEdge.UR; e <= RubikSolverEdge.BR; e++) edgeCount[ep[e]]++; + + for( int i=0; i<12; i++) + if (edgeCount[i] != 1) return -2; + + for( int i=0; i<12; i++) sum += eo[i]; + + if( (sum%2) != 0) return -3; + + int[] cornerCount = new int[8]; + + for(int c = RubikSolverCorner.URF; c<= RubikSolverCorner.DRB; c++) cornerCount[cp[c]]++; + + for (int i = 0; i < 8; i++) + if (cornerCount[i] != 1) return -4;// missing corners + + sum = 0; + + for( int i=0; i<8; i++) sum += co[i]; + + if( (sum%3) != 0) return -5;// twisted corner + + if( (edgeParity()^cornerParity()) != 0) return -6;// parity error + + return 0;// cube ok + } +} \ No newline at end of file diff --git a/src/main/java/org/distorted/solvers/cube3/RubikSolverEdge.java b/src/main/java/org/distorted/solvers/cube3/RubikSolverEdge.java new file mode 100644 index 00000000..5e782b68 --- /dev/null +++ b/src/main/java/org/distorted/solvers/cube3/RubikSolverEdge.java @@ -0,0 +1,38 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Copyright 2008 Leszek Koltunski // +// // +// This file is part of Magic Cube. // +// // +// Magic Cube is free software: you can redistribute it and/or modify // +// it under the terms of the GNU General Public License as published by // +// the Free Software Foundation, either version 2 of the License, or // +// (at your option) any later version. // +// // +// Magic Cube is distributed in the hope that it will be useful, // +// but WITHOUT ANY WARRANTY; without even the implied warranty of // +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // +// GNU General Public License for more details. // +// // +// You should have received a copy of the GNU General Public License // +// along with Magic Cube. If not, see . // +/////////////////////////////////////////////////////////////////////////////////////////////////// + +package org.distorted.solvers.cube3; + +/////////////////////////////////////////////////////////////////////////////////////////////////// + +class RubikSolverEdge + { + public static final int UR=0; + public static final int UF=1; + public static final int UL=2; + public static final int UB=3; + public static final int DR=4; + public static final int DF=5; + public static final int DL=6; + public static final int DB=7; + public static final int FR=8; + public static final int FL=9; + public static final int BL=10; + public static final int BR=11; + } \ No newline at end of file diff --git a/src/main/java/org/distorted/solvers/cube3/RubikSolverFaceCube.java b/src/main/java/org/distorted/solvers/cube3/RubikSolverFaceCube.java new file mode 100644 index 00000000..7b73fbd1 --- /dev/null +++ b/src/main/java/org/distorted/solvers/cube3/RubikSolverFaceCube.java @@ -0,0 +1,149 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Copyright 2008 Leszek Koltunski // +// // +// This file is part of Magic Cube. // +// // +// Magic Cube is free software: you can redistribute it and/or modify // +// it under the terms of the GNU General Public License as published by // +// the Free Software Foundation, either version 2 of the License, or // +// (at your option) any later version. // +// // +// Magic Cube is distributed in the hope that it will be useful, // +// but WITHOUT ANY WARRANTY; without even the implied warranty of // +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // +// GNU General Public License for more details. // +// // +// You should have received a copy of the GNU General Public License // +// along with Magic Cube. If not, see . // +/////////////////////////////////////////////////////////////////////////////////////////////////// + +package org.distorted.solvers.cube3; + +/////////////////////////////////////////////////////////////////////////////////////////////////// + +class RubikSolverFaceCube +{ + public int[] f = new int[54]; + + // Map the corner positions to facelet positions. cornerFacelet[URF.ordinal()][0] e.g. gives the position of the + // facelet in the URF corner position, which defines the orientation. + // cornerFacelet[URF.ordinal()][1] and cornerFacelet[URF.ordinal()][2] give the position of the other two facelets + // of the URF corner (clockwise). + final static int[][] cornerFacelet = + { { RubikSolverFacelet.U9, RubikSolverFacelet.R1, RubikSolverFacelet.F3 }, { RubikSolverFacelet.U7, RubikSolverFacelet.F1, RubikSolverFacelet.L3 }, + { RubikSolverFacelet.U1, RubikSolverFacelet.L1, RubikSolverFacelet.B3 }, { RubikSolverFacelet.U3, RubikSolverFacelet.B1, RubikSolverFacelet.R3 }, + { RubikSolverFacelet.D3, RubikSolverFacelet.F9, RubikSolverFacelet.R7 }, { RubikSolverFacelet.D1, RubikSolverFacelet.L9, RubikSolverFacelet.F7 }, + { RubikSolverFacelet.D7, RubikSolverFacelet.B9, RubikSolverFacelet.L7 }, { RubikSolverFacelet.D9, RubikSolverFacelet.R9, RubikSolverFacelet.B7 } }; + + // Map the edge positions to facelet positions. edgeFacelet[UR.ordinal()][0] e.g. gives the position of the facelet in + // the UR edge position, which defines the orientation. + // edgeFacelet[UR.ordinal()][1] gives the position of the other facelet + final static int[][] edgeFacelet = + { { RubikSolverFacelet.U6, RubikSolverFacelet.R2 }, { RubikSolverFacelet.U8, RubikSolverFacelet.F2 }, { RubikSolverFacelet.U4, RubikSolverFacelet.L2 }, + { RubikSolverFacelet.U2, RubikSolverFacelet.B2 }, { RubikSolverFacelet.D6, RubikSolverFacelet.R8 }, { RubikSolverFacelet.D2, RubikSolverFacelet.F8 }, + { RubikSolverFacelet.D4, RubikSolverFacelet.L8 }, { RubikSolverFacelet.D8, RubikSolverFacelet.B8 }, { RubikSolverFacelet.F6, RubikSolverFacelet.R4 }, + { RubikSolverFacelet.F4, RubikSolverFacelet.L6 }, { RubikSolverFacelet.B6, RubikSolverFacelet.L4 }, { RubikSolverFacelet.B4, RubikSolverFacelet.R6 } }; + + // Map the corner positions to facelet colors. + final static int[][] cornerColor = + { { RubikSolverColor.U, RubikSolverColor.R, RubikSolverColor.F }, { RubikSolverColor.U, RubikSolverColor.F, RubikSolverColor.L }, + { RubikSolverColor.U, RubikSolverColor.L, RubikSolverColor.B }, { RubikSolverColor.U, RubikSolverColor.B, RubikSolverColor.R }, + { RubikSolverColor.D, RubikSolverColor.F, RubikSolverColor.R }, { RubikSolverColor.D, RubikSolverColor.L, RubikSolverColor.F }, + { RubikSolverColor.D, RubikSolverColor.B, RubikSolverColor.L }, { RubikSolverColor.D, RubikSolverColor.R, RubikSolverColor.B } }; + + // Map the edge positions to facelet colors. + final static int[][] edgeColor = + { { RubikSolverColor.U, RubikSolverColor.R }, { RubikSolverColor.U, RubikSolverColor.F }, { RubikSolverColor.U, RubikSolverColor.L }, + { RubikSolverColor.U, RubikSolverColor.B }, { RubikSolverColor.D, RubikSolverColor.R }, { RubikSolverColor.D, RubikSolverColor.F }, + { RubikSolverColor.D, RubikSolverColor.L }, { RubikSolverColor.D, RubikSolverColor.B }, { RubikSolverColor.F, RubikSolverColor.R }, + { RubikSolverColor.F, RubikSolverColor.L }, { RubikSolverColor.B, RubikSolverColor.L }, { RubikSolverColor.B, RubikSolverColor.R } }; + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + RubikSolverFaceCube() + { + String s = "UUUUUUUUURRRRRRRRRFFFFFFFFFDDDDDDDDDLLLLLLLLLBBBBBBBBB"; + + for( int i=0; i<54; i++) + f[i] = RubikSolverColor.toInt(s.substring(i, i + 1)); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Construct a facelet cube from a string + + RubikSolverFaceCube(String cubeString) + { + for( int i=0; i. // +/////////////////////////////////////////////////////////////////////////////////////////////////// + +package org.distorted.solvers.cube3; + +/** + * 
+ * The names of the facelet positions of the cube
+ *             |************|
+ *             |*U1**U2**U3*|
+ *             |************|
+ *             |*U4**U5**U6*|
+ *             |************|
+ *             |*U7**U8**U9*|
+ *             |************|
+ * ************|************|************|************|
+ * *L1**L2**L3*|*F1**F2**F3*|*R1**R2**F3*|*B1**B2**B3*|
+ * ************|************|************|************|
+ * *L4**L5**L6*|*F4**F5**F6*|*R4**R5**R6*|*B4**B5**B6*|
+ * ************|************|************|************|
+ * *L7**L8**L9*|*F7**F8**F9*|*R7**R8**R9*|*B7**B8**B9*|
+ * ************|************|************|************|
+ *             |************|
+ *             |*D1**D2**D3*|
+ *             |************|
+ *             |*D4**D5**D6*|
+ *             |************|
+ *             |*D7**D8**D9*|
+ *             |************|
+ *
+ * + *A cube definition string "UBL..." means for example: In position U1 we have the U-color, in position U2 we have the + * B-color, in position U3 we have the L color etc. according to the order U1, U2, U3, U4, U5, U6, U7, U8, U9, R1, R2, + * R3, R4, R5, R6, R7, R8, R9, F1, F2, F3, F4, F5, F6, F7, F8, F9, D1, D2, D3, D4, D5, D6, D7, D8, D9, L1, L2, L3, L4, + * L5, L6, L7, L8, L9, B1, B2, B3, B4, B5, B6, B7, B8, B9 of the enum constants. + */ + +/////////////////////////////////////////////////////////////////////////////////////////////////// + +class RubikSolverFacelet + { + public static int U1 = 0; + public static int U2 = 1; + public static int U3 = 2; + public static int U4 = 3; + public static int U5 = 4; + public static int U6 = 5; + public static int U7 = 6; + public static int U8 = 7; + public static int U9 = 8; + + public static int R1 = 9; + public static int R2 = 10; + public static int R3 = 11; + public static int R4 = 12; + public static int R5 = 13; + public static int R6 = 14; + public static int R7 = 15; + public static int R8 = 16; + public static int R9 = 17; + + public static int F1 = 18; + public static int F2 = 19; + public static int F3 = 20; + public static int F4 = 21; + public static int F5 = 22; + public static int F6 = 23; + public static int F7 = 24; + public static int F8 = 25; + public static int F9 = 26; + + public static int D1 = 27; + public static int D2 = 28; + public static int D3 = 29; + public static int D4 = 30; + public static int D5 = 31; + public static int D6 = 32; + public static int D7 = 33; + public static int D8 = 34; + public static int D9 = 35; + + public static int L1 = 36; + public static int L2 = 37; + public static int L3 = 38; + public static int L4 = 39; + public static int L5 = 40; + public static int L6 = 41; + public static int L7 = 42; + public static int L8 = 43; + public static int L9 = 44; + + public static int B1 = 45; + public static int B2 = 46; + public static int B3 = 47; + public static int B4 = 48; + public static int B5 = 49; + public static int B6 = 50; + public static int B7 = 51; + public static int B8 = 52; + public static int B9 = 53; + } \ No newline at end of file diff --git a/src/main/java/org/distorted/solvers/cube3/RubikSolverSearch.java b/src/main/java/org/distorted/solvers/cube3/RubikSolverSearch.java new file mode 100644 index 00000000..ea9f52aa --- /dev/null +++ b/src/main/java/org/distorted/solvers/cube3/RubikSolverSearch.java @@ -0,0 +1,400 @@ +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Copyright 2008 Leszek Koltunski // +// // +// This file is part of Magic Cube. // +// // +// Magic Cube is free software: you can redistribute it and/or modify // +// it under the terms of the GNU General Public License as published by // +// the Free Software Foundation, either version 2 of the License, or // +// (at your option) any later version. // +// // +// Magic Cube is distributed in the hope that it will be useful, // +// but WITHOUT ANY WARRANTY; without even the implied warranty of // +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // +// GNU General Public License for more details. // +// // +// You should have received a copy of the GNU General Public License // +// along with Magic Cube. If not, see . // +/////////////////////////////////////////////////////////////////////////////////////////////////// + +package org.distorted.solvers.cube3; + +import android.content.res.Resources; + +/////////////////////////////////////////////////////////////////////////////////////////////////// + +public class RubikSolverSearch +{ + static int mNumMoves = 0; + + static int[] ax = new int[31]; // The axis of the move + static int[] po = new int[31]; // The power of the move + + static int[] flip = new int[31]; // phase1 coordinates + static int[] twist = new int[31]; + static int[] slice = new int[31]; + + static int[] parity = new int[31]; // phase2 coordinates + static int[] URFtoDLF= new int[31]; + static int[] FRtoBR = new int[31]; + static int[] URtoUL = new int[31]; + static int[] UBtoDF = new int[31]; + static int[] URtoDF = new int[31]; + + static int[] minDistPhase1 = new int[31]; // IDA * distance to goal estimations + static int[] minDistPhase2 = new int[31]; + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + static String solutionToString(int length) + { + StringBuilder s = new StringBuilder(); + + for( int i=0; i minDistPhase1[n+1]) && !busy) + { + if (ax[n]==0 || ax[n]==3)// Initialize next move + ax[++n] = 1; + else + ax[++n] = 0; + po[n] = 1; + } + else if (++po[n] > 3) + { + do + { // increment axis + if (++ax[n] > 5) + { + if (System.currentTimeMillis() - tStart > timeOut << 10) + return "Error 8"; + + if (n==0) + { + if (depthPhase1 >= maxDepth) + return "Error 7"; + else + { + depthPhase1++; + ax[n] = 0; + po[n] = 1; + busy = false; + break; + } + } + else + { + n--; + busy = true; + break; + } + } + else + { + po[n] = 1; + busy = false; + } + } + while (n != 0 && (ax[n - 1] == ax[n] || ax[n - 1] - 3 == ax[n])); + } + else + busy = false; + } + while (busy); + + // compute new coordinates and new minDistPhase1. If minDistPhase1 =0, the H subgroup is reached + mv = 3*ax[n]+po[n]-1; + flip [n+1] = RubikSolverCoordCube.getFlipMove(flip[n],mv); + twist[n+1] = RubikSolverCoordCube.getTwistMove(twist[n],mv); + slice[n+1] = RubikSolverCoordCube.getFRtoBR_Move(slice[n] * 24,mv) / 24; + minDistPhase1[n+1] = Math.max(RubikSolverCoordCube.getPruning(RubikSolverCoordCube.Slice_Flip_Prun, RubikSolverCoordCube.N_SLICE1 * flip[n+1] + + slice[n+1]), RubikSolverCoordCube.getPruning(RubikSolverCoordCube.Slice_Twist_Prun, RubikSolverCoordCube.N_SLICE1 * twist[n+1] + + slice[n+1])); + + if (minDistPhase1[n+1]==0 && n >= depthPhase1 - 5) + { + minDistPhase1[n+1] = 10;// instead of 10 any value >5 is possible + if (n==depthPhase1-1 && (s = totalDepth(depthPhase1, maxDepth)) >= 0) + { + if (s==depthPhase1 || (ax[depthPhase1-1] != ax[depthPhase1] && ax[depthPhase1-1] != ax[depthPhase1]+3)) + { + mNumMoves = s; + return solutionToString(s); + } + } + } + } + while (true); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Apply phase2 of algorithm and return the combined phase1 and phase2 depth. In phase2, only the moves +// U,D,R2,F2,L2 and B2 are allowed. + + static int totalDepth(int depthPhase1, int maxDepth) + { + int mv, d1, d2; + int maxDepthPhase2 = Math.min(10,maxDepth-depthPhase1);// Allow only max 10 moves in phase2 + for( int i=0; i maxDepthPhase2) + return -1; + + for( int i=0; i maxDepthPhase2) + return -1; + + if ((minDistPhase2[depthPhase1] = Math.max(d1, d2)) == 0)// already solved + return depthPhase1; + + // now set up search + int depthPhase2 = 1; + int n = depthPhase1; + boolean busy = false; + po[depthPhase1] = 0; + ax[depthPhase1] = 0; + minDistPhase2[n + 1] = 1; // else failure for depthPhase2=1, n=0 + // end initialization + + do + { + do + { + if ((depthPhase1 + depthPhase2 - n > minDistPhase2[n + 1]) && !busy) + { + if (ax[n] == 0 || ax[n] == 3)// Initialize next move + { + ax[++n] = 1; + po[n] = 2; + } + else + { + ax[++n] = 0; + po[n] = 1; + } + } + else if ((ax[n] == 0 || ax[n] == 3) ? (++po[n] > 3) : ((po[n] = po[n] + 2) > 3)) + { + do + { + if (++ax[n] > 5) + { + if (n == depthPhase1) + { + if (depthPhase2 >= maxDepthPhase2) + return -1; + else + { + depthPhase2++; + ax[n] = 0; + po[n] = 1; + busy = false; + break; + } + } + else + { + n--; + busy = true; + break; + } + } + else + { + if (ax[n]==0 || ax[n]==3) + po[n] = 1; + else + po[n] = 2; + busy = false; + } + } + while (n != depthPhase1 && (ax[n - 1] == ax[n] || ax[n - 1] - 3 == ax[n])); + } + else + busy = false; + } + while (busy); + + // compute new coordinates and new minDist + mv = 3*ax[n]+po[n]-1; + + URFtoDLF[n+1] = RubikSolverCoordCube.getURFtoDLF_Move(URFtoDLF[n],mv); + FRtoBR [n+1] = RubikSolverCoordCube.getFRtoBR_Move(FRtoBR[n],mv); + parity [n+1] = RubikSolverCoordCube.parityMove[parity[n]][mv]; + URtoDF [n+1] = RubikSolverCoordCube.getURtoDF_Move(URtoDF[n],mv); + + minDistPhase2[n+1] = Math.max(RubikSolverCoordCube.getPruning(RubikSolverCoordCube.Slice_URtoDF_Parity_Prun, (RubikSolverCoordCube.N_SLICE2 + * URtoDF[n+1] + FRtoBR[n+1]) + * 2 + parity[n+1]), RubikSolverCoordCube.getPruning(RubikSolverCoordCube.Slice_URFtoDLF_Parity_Prun, (RubikSolverCoordCube.N_SLICE2 + * URFtoDLF[n+1] + FRtoBR[n+1]) + * 2 + parity[n+1])); + } + while (minDistPhase2[n + 1] != 0); + + return depthPhase1 + depthPhase2; + } +} diff --git a/src/main/java/org/distorted/solvers/cube3/Search.java b/src/main/java/org/distorted/solvers/cube3/Search.java deleted file mode 100644 index 43ea5e28..00000000 --- a/src/main/java/org/distorted/solvers/cube3/Search.java +++ /dev/null @@ -1,386 +0,0 @@ -package org.distorted.solvers.cube3; - -import android.content.res.Resources; - -import android.util.Log; - -//++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ -/** - * Class Search implements the Two-Phase-Algorithm. - */ -public class Search { - - static boolean mInterrupted; - static int mNumMoves = 0; - - static int[] ax = new int[31]; // The axis of the move - static int[] po = new int[31]; // The power of the move - - static int[] flip = new int[31]; // phase1 coordinates - static int[] twist = new int[31]; - static int[] slice = new int[31]; - - static int[] parity = new int[31]; // phase2 coordinates - static int[] URFtoDLF = new int[31]; - static int[] FRtoBR = new int[31]; - static int[] URtoUL = new int[31]; - static int[] UBtoDF = new int[31]; - static int[] URtoDF = new int[31]; - - static int[] minDistPhase1 = new int[31]; // IDA* distance do goal estimations - static int[] minDistPhase2 = new int[31]; - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // retyurn number of moves in the already computed solution - public static int numMoves() - { - return mNumMoves; - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // generate the solution string from the array data - static String solutionToString(int length) - { - String s = ""; - - for (int i = 0; i < length; i++) { - switch (ax[i]) { - case 0: switch(po[i]) - { - case 1: s+=" 548"; break; - case 2: s+=" 804"; break; - case 3: s+=" 292"; break; - } - break; - case 1: switch(po[i]) - { - case 1: s+=" 516"; break; - case 2: s+=" 772"; break; - case 3: s+=" 260"; break; - } - break; - case 2: switch(po[i]) - { - case 1: s+=" 580"; break; - case 2: s+=" 836"; break; - case 3: s+=" 324"; break; - } - break; - case 3: switch(po[i]) - { - case 1: s+=" 289"; break; - case 2: s+=" 033"; break; - case 3: s+=" 545"; break; - } - break; - case 4: switch(po[i]) - { - case 1: s+=" 257"; break; - case 2: s+=" 001"; break; - case 3: s+=" 513"; break; - } - break; - case 5: switch(po[i]) - { - case 1: s+=" 321"; break; - case 2: s+=" 065"; break; - case 3: s+=" 577"; break; - } - break; - } - } - return s; - }; - - /** - * Interrupt current computation - */ - public static void interrupt() - { - mInterrupted = true; - } - - /** - * Prepare pruning tables - */ - public static boolean prepare(Resources res) - { - if( mInterrupted ) return false; - CoordCube.initialize1(res); - - if( mInterrupted ) return false; - CoordCube.initialize2(res); - - if( mInterrupted ) return false; - CoordCube.initialize3(res); - - if( mInterrupted ) return false; - CoordCube.initialize4(res); - - if( mInterrupted ) return false; - CoordCube.initialize5(res); - - if( mInterrupted ) return false; - CoordCube.initialize6(res); - - if( mInterrupted ) return false; - CoordCube.initialize7(res); - - if( mInterrupted ) return false; - CoordCube.initialize8(res); - - if( mInterrupted ) return false; - CoordCube.initialize9(res); - - if( mInterrupted ) return false; - CoordCube.initialize10(res); - - if( mInterrupted ) return false; - CoordCube.initialize11(res); - - if( mInterrupted ) return false; - CoordCube.initialize12(res); - - if( mInterrupted ) return false; - - return true; - } - /** - * Computes the solver string for a given cube. - * - * @param facelets - * is the cube definition string, see {@link Facelet} for the format. - * - * @param maxDepth - * defines the maximal allowed maneuver length. For random cubes, a maxDepth of 21 usually will return a - * solution in less than 0.5 seconds. With a maxDepth of 20 it takes a few seconds on average to find a - * solution, but it may take much longer for specific cubes. - * - *@param timeOut - * defines the maximum computing time of the method in seconds. If it does not return with a solution, it returns with - * an error code. - * @return The solution string or an error code:
- * Error 1: There is not exactly one facelet of each colour
- * Error 2: Not all 12 edges exist exactly once
- * Error 3: Flip error: One edge has to be flipped
- * Error 4: Not all corners exist exactly once
- * Error 5: Twist error: One corner has to be twisted
- * Error 6: Parity error: Two corners or two edges have to be exchanged
- * Error 7: No solution exists for the given maxDepth
- * Error 8: Timeout, no solution within given time - */ - public static String solution(String facelets, int maxDepth, long timeOut) - { - int s; - - mInterrupted = false; - - // +++++++++++++++++++++check for wrong input +++++++++++++++++++++++++++++ - int[] count = new int[6]; - try { - for (int i = 0; i < 54; i++) - count[Color.toInt(facelets.substring(i, i + 1))]++; - } catch (Exception e) {Log.d("error", "1"); - return "Error 1"; - } - for (int i = 0; i < 6; i++) - if (count[i] != 9) { Log.d("error", "2"); - return "Error 1"; } - - FaceCube fc = new FaceCube(facelets); - CubieCube cc = fc.toCubieCube(); - if ((s = cc.verify()) != 0) { Log.d("error", "3"); - return "Error " + Math.abs(s); } - - // +++++++++++++++++++++++ initialization +++++++++++++++++++++++++++++++++ - - CoordCube c = new CoordCube(cc); - - po[0] = 0; - ax[0] = 0; - flip[0] = c.flip; - twist[0] = c.twist; - parity[0] = c.parity; - slice[0] = c.FRtoBR / 24; - URFtoDLF[0] = c.URFtoDLF; - FRtoBR[0] = c.FRtoBR; - URtoUL[0] = c.URtoUL; - UBtoDF[0] = c.UBtoDF; - - minDistPhase1[1] = 1;// else failure for depth=1, n=0 - int mv = 0, n = 0; - boolean busy = false; - int depthPhase1 = 1; - - long tStart = System.currentTimeMillis(); - - // +++++++++++++++++++ Main loop ++++++++++++++++++++++++++++++++++++++++++ - do { - do { - if( mInterrupted ) return "Error 9"; - - if ((depthPhase1 - n > minDistPhase1[n + 1]) && !busy) { - - if (ax[n] == 0 || ax[n] == 3)// Initialize next move - ax[++n] = 1; - else - ax[++n] = 0; - po[n] = 1; - } else if (++po[n] > 3) { - do {// increment axis - if (++ax[n] > 5) { - - if (System.currentTimeMillis() - tStart > timeOut << 10) - return "Error 8"; - - if (n == 0) { - if (depthPhase1 >= maxDepth) - return "Error 7"; - else { - depthPhase1++; - ax[n] = 0; - po[n] = 1; - busy = false; - break; - } - } else { - n--; - busy = true; - break; - } - - } else { - po[n] = 1; - busy = false; - } - } while (n != 0 && (ax[n - 1] == ax[n] || ax[n - 1] - 3 == ax[n])); - } else - busy = false; - } while (busy); - - // +++++++++++++ compute new coordinates and new minDistPhase1 ++++++++++ - // if minDistPhase1 =0, the H subgroup is reached - mv = 3 * ax[n] + po[n] - 1; - flip[n + 1] = CoordCube.getFlipMove(flip[n],mv); - twist[n + 1] = CoordCube.getTwistMove(twist[n],mv); - slice[n + 1] = CoordCube.getFRtoBR_Move(slice[n] * 24,mv) / 24; - minDistPhase1[n + 1] = Math.max(CoordCube.getPruning(CoordCube.Slice_Flip_Prun, CoordCube.N_SLICE1 * flip[n + 1] - + slice[n + 1]), CoordCube.getPruning(CoordCube.Slice_Twist_Prun, CoordCube.N_SLICE1 * twist[n + 1] - + slice[n + 1])); - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - - if (minDistPhase1[n + 1] == 0 && n >= depthPhase1 - 5) { - minDistPhase1[n + 1] = 10;// instead of 10 any value >5 is possible - if (n == depthPhase1 - 1 && (s = totalDepth(depthPhase1, maxDepth)) >= 0) { - if (s == depthPhase1 || (ax[depthPhase1 - 1] != ax[depthPhase1] && ax[depthPhase1 - 1] != ax[depthPhase1] + 3)) - { - mNumMoves = s; - return solutionToString(s); - } - } - - } - } while (true); - } - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Apply phase2 of algorithm and return the combined phase1 and phase2 depth. In phase2, only the moves - // U,D,R2,F2,L2 and B2 are allowed. - static int totalDepth(int depthPhase1, int maxDepth) { - int mv = 0, d1 = 0, d2 = 0; - int maxDepthPhase2 = Math.min(10, maxDepth - depthPhase1);// Allow only max 10 moves in phase2 - for (int i = 0; i < depthPhase1; i++) { - mv = 3 * ax[i] + po[i] - 1; - URFtoDLF[i + 1] = CoordCube.getURFtoDLF_Move(URFtoDLF[i],mv); - FRtoBR[i + 1] = CoordCube.getFRtoBR_Move(FRtoBR[i],mv); - parity[i + 1] = CoordCube.parityMove[parity[i]][mv]; - } - - if ((d1 = CoordCube.getPruning(CoordCube.Slice_URFtoDLF_Parity_Prun, - (CoordCube.N_SLICE2 * URFtoDLF[depthPhase1] + FRtoBR[depthPhase1]) * 2 + parity[depthPhase1])) > maxDepthPhase2) - return -1; - - for (int i = 0; i < depthPhase1; i++) { - mv = 3 * ax[i] + po[i] - 1; - URtoUL[i + 1] = CoordCube.getURtoUL_Move(URtoUL[i],mv); - UBtoDF[i + 1] = CoordCube.getUBtoDF_Move(UBtoDF[i],mv); - } - URtoDF[depthPhase1] = CoordCube.getMergeURtoULandUBtoDF(URtoUL[depthPhase1],UBtoDF[depthPhase1]); - - if ((d2 = CoordCube.getPruning(CoordCube.Slice_URtoDF_Parity_Prun, - (CoordCube.N_SLICE2 * URtoDF[depthPhase1] + FRtoBR[depthPhase1]) * 2 + parity[depthPhase1])) > maxDepthPhase2) - return -1; - - if ((minDistPhase2[depthPhase1] = Math.max(d1, d2)) == 0)// already solved - return depthPhase1; - - // now set up search - - int depthPhase2 = 1; - int n = depthPhase1; - boolean busy = false; - po[depthPhase1] = 0; - ax[depthPhase1] = 0; - minDistPhase2[n + 1] = 1;// else failure for depthPhase2=1, n=0 - // +++++++++++++++++++ end initialization +++++++++++++++++++++++++++++++++ - do { - do { - if ((depthPhase1 + depthPhase2 - n > minDistPhase2[n + 1]) && !busy) { - - if (ax[n] == 0 || ax[n] == 3)// Initialize next move - { - ax[++n] = 1; - po[n] = 2; - } else { - ax[++n] = 0; - po[n] = 1; - } - } else if ((ax[n] == 0 || ax[n] == 3) ? (++po[n] > 3) : ((po[n] = po[n] + 2) > 3)) { - do {// increment axis - if (++ax[n] > 5) { - if (n == depthPhase1) { - if (depthPhase2 >= maxDepthPhase2) - return -1; - else { - depthPhase2++; - ax[n] = 0; - po[n] = 1; - busy = false; - break; - } - } else { - n--; - busy = true; - break; - } - - } else { - if (ax[n] == 0 || ax[n] == 3) - po[n] = 1; - else - po[n] = 2; - busy = false; - } - } while (n != depthPhase1 && (ax[n - 1] == ax[n] || ax[n - 1] - 3 == ax[n])); - } else - busy = false; - } while (busy); - // +++++++++++++ compute new coordinates and new minDist ++++++++++ - mv = 3 * ax[n] + po[n] - 1; - - URFtoDLF[n + 1] = CoordCube.getURFtoDLF_Move(URFtoDLF[n],mv); - FRtoBR[n + 1] = CoordCube.getFRtoBR_Move(FRtoBR[n],mv); - parity[n + 1] = CoordCube.parityMove[parity[n]][mv]; - URtoDF[n + 1] = CoordCube.getURtoDF_Move(URtoDF[n],mv); - - minDistPhase2[n + 1] = Math.max(CoordCube.getPruning(CoordCube.Slice_URtoDF_Parity_Prun, (CoordCube.N_SLICE2 - * URtoDF[n + 1] + FRtoBR[n + 1]) - * 2 + parity[n + 1]), CoordCube.getPruning(CoordCube.Slice_URFtoDLF_Parity_Prun, (CoordCube.N_SLICE2 - * URFtoDLF[n + 1] + FRtoBR[n + 1]) - * 2 + parity[n + 1])); - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - - } while (minDistPhase2[n + 1] != 0); - return depthPhase1 + depthPhase2; - } -} diff --git a/src/main/java/org/distorted/solvers/cube3/Tools.java b/src/main/java/org/distorted/solvers/cube3/Tools.java deleted file mode 100644 index 12f0c459..00000000 --- a/src/main/java/org/distorted/solvers/cube3/Tools.java +++ /dev/null @@ -1,64 +0,0 @@ -package org.distorted.solvers.cube3; - -import java.util.Random; - -public class Tools { - - // ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ - // Check if the cube string s represents a solvable cube. - // 0: Cube is solvable - // -1: There is not exactly one facelet of each colour - // -2: Not all 12 edges exist exactly once - // -3: Flip error: One edge has to be flipped - // -4: Not all corners exist exactly once - // -5: Twist error: One corner has to be twisted - // -6: Parity error: Two corners or two edges have to be exchanged - // - /** - * Check if the cube definition string s represents a solvable cube. - * - * @param s is the cube definition string , see {@link Facelet} - * @return 0: Cube is solvable
- * -1: There is not exactly one facelet of each colour
- * -2: Not all 12 edges exist exactly once
- * -3: Flip error: One edge has to be flipped
- * -4: Not all 8 corners exist exactly once
- * -5: Twist error: One corner has to be twisted
- * -6: Parity error: Two corners or two edges have to be exchanged - */ - public static int verify(String s) { - int[] count = new int[6]; - try { - for (int i = 0; i < 54; i++) - count[Color.toInt(s.substring(i, i + 1))]++; - } catch (Exception e) { - return -1; - } - - for (int i = 0; i < 6; i++) - if (count[i] != 9) - return -1; - - FaceCube fc = new FaceCube(s); - CubieCube cc = fc.toCubieCube(); - - return cc.verify(); - } - - /** - * Generates a random cube. - * @return A random cube in the string representation. Each cube of the cube space has the same probability. - */ - public static String randomCube() { - CubieCube cc = new CubieCube(); - Random gen = new Random(); - cc.setFlip((short) gen.nextInt(CoordCube.N_FLIP)); - cc.setTwist((short) gen.nextInt(CoordCube.N_TWIST)); - do { - cc.setURFtoDLB(gen.nextInt(CoordCube.N_URFtoDLB)); - cc.setURtoBR(gen.nextInt(CoordCube.N_URtoBR)); - } while ((cc.edgeParity() ^ cc.cornerParity()) != 0); - FaceCube fc = cc.toFaceCube(); - return fc.to_String(); - } -}