commit dfae472bc383a46fd6ba3013e2679d451d9e1dfb Author: Leszek Koltunski Date: Mon Jul 11 14:12:29 2022 +0200 Rename solver files. diff --git a/src/main/java/org/distorted/solvers/SolverMain.java b/src/main/java/org/distorted/solvers/SolverMain.java index a583d501..0cd48b92 100644 --- a/src/main/java/org/distorted/solvers/SolverMain.java +++ b/src/main/java/org/distorted/solvers/SolverMain.java @@ -27,7 +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; +import org.distorted.solvers.cube3.SolverSearch; /////////////////////////////////////////////////////////////////////////////////////////////////// @@ -73,9 +73,9 @@ public class SolverMain implements Runnable { String result; - RubikSolverSearch.prepare(mRes); + SolverSearch.prepare(mRes); String objectPosition = prepareCube3position(); - result = RubikSolverSearch.solution(objectPosition, 24, 20); + result = SolverSearch.solution(objectPosition, 24, 20); if (result.contains("Error")) { diff --git a/src/main/java/org/distorted/solvers/cube3/RubikSolverColor.java b/src/main/java/org/distorted/solvers/cube3/RubikSolverColor.java deleted file mode 100644 index 9d6ecd3c..00000000 --- a/src/main/java/org/distorted/solvers/cube3/RubikSolverColor.java +++ /dev/null @@ -1,65 +0,0 @@ -/////////////////////////////////////////////////////////////////////////////////////////////////// -// 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 deleted file mode 100644 index a518bd1a..00000000 --- a/src/main/java/org/distorted/solvers/cube3/RubikSolverCoordCube.java +++ /dev/null @@ -1,260 +0,0 @@ -/////////////////////////////////////////////////////////////////////////////////////////////////// -// 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 deleted file mode 100644 index eb6f1980..00000000 --- a/src/main/java/org/distorted/solvers/cube3/RubikSolverCorner.java +++ /dev/null @@ -1,35 +0,0 @@ -/////////////////////////////////////////////////////////////////////////////////////////////////// -// 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 deleted file mode 100644 index 3e716dcb..00000000 --- a/src/main/java/org/distorted/solvers/cube3/RubikSolverCubieCube.java +++ /dev/null @@ -1,518 +0,0 @@ -/////////////////////////////////////////////////////////////////////////////////////////////////// -// 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 deleted file mode 100644 index 5e782b68..00000000 --- a/src/main/java/org/distorted/solvers/cube3/RubikSolverEdge.java +++ /dev/null @@ -1,38 +0,0 @@ -/////////////////////////////////////////////////////////////////////////////////////////////////// -// 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 deleted file mode 100644 index 7b73fbd1..00000000 --- a/src/main/java/org/distorted/solvers/cube3/RubikSolverFaceCube.java +++ /dev/null @@ -1,149 +0,0 @@ -/////////////////////////////////////////////////////////////////////////////////////////////////// -// 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 deleted file mode 100644 index ea9f52aa..00000000 --- a/src/main/java/org/distorted/solvers/cube3/RubikSolverSearch.java +++ /dev/null @@ -1,400 +0,0 @@ -/////////////////////////////////////////////////////////////////////////////////////////////////// -// 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/SolverColor.java b/src/main/java/org/distorted/solvers/cube3/SolverColor.java new file mode 100644 index 00000000..44a69964 --- /dev/null +++ b/src/main/java/org/distorted/solvers/cube3/SolverColor.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 SolverColor + { + 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/SolverCoordCube.java b/src/main/java/org/distorted/solvers/cube3/SolverCoordCube.java new file mode 100644 index 00000000..4fe2d630 --- /dev/null +++ b/src/main/java/org/distorted/solvers/cube3/SolverCoordCube.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 SolverCoordCube +{ + 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 + + SolverCoordCube(SolverCubieCube 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/SolverCorner.java b/src/main/java/org/distorted/solvers/cube3/SolverCorner.java new file mode 100644 index 00000000..ddfa0d8b --- /dev/null +++ b/src/main/java/org/distorted/solvers/cube3/SolverCorner.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 SolverCorner + { + 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/SolverCubieCube.java b/src/main/java/org/distorted/solvers/cube3/SolverCubieCube.java new file mode 100644 index 00000000..e260bad4 --- /dev/null +++ b/src/main/java/org/distorted/solvers/cube3/SolverCubieCube.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 SolverCubieCube + { + 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 = { SolverCorner.URF, SolverCorner.UFL, SolverCorner.ULB, SolverCorner.UBR, SolverCorner.DFR, SolverCorner.DLF, SolverCorner.DBL, SolverCorner.DRB }; + + // corner orientation + byte[] co = { 0, 0, 0, 0, 0, 0, 0, 0 }; + + // edge permutation + int[] ep = { SolverEdge.UR, SolverEdge.UF, SolverEdge.UL, SolverEdge.UB, SolverEdge.DR, SolverEdge.DF, SolverEdge.DL, SolverEdge.DB, SolverEdge.FR, SolverEdge.FL, SolverEdge.BL, SolverEdge.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 = { SolverCorner.UBR, SolverCorner.URF, SolverCorner.UFL, SolverCorner.ULB, SolverCorner.DFR, SolverCorner.DLF, SolverCorner.DBL, SolverCorner.DRB }; + private static final byte[] coU = { 0, 0, 0, 0, 0, 0, 0, 0 }; + private static final int[] epU = { SolverEdge.UB, SolverEdge.UR, SolverEdge.UF, SolverEdge.UL, SolverEdge.DR, SolverEdge.DF, SolverEdge.DL, SolverEdge.DB, SolverEdge.FR, SolverEdge.FL, SolverEdge.BL, SolverEdge.BR }; + private static final byte[] eoU = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; + + private static final int[] cpR = { SolverCorner.DFR, SolverCorner.UFL, SolverCorner.ULB, SolverCorner.URF, SolverCorner.DRB, SolverCorner.DLF, SolverCorner.DBL, SolverCorner.UBR }; + private static final byte[] coR = { 2, 0, 0, 1, 1, 0, 0, 2 }; + private static final int[] epR = { SolverEdge.FR, SolverEdge.UF, SolverEdge.UL, SolverEdge.UB, SolverEdge.BR, SolverEdge.DF, SolverEdge.DL, SolverEdge.DB, SolverEdge.DR, SolverEdge.FL, SolverEdge.BL, SolverEdge.UR }; + private static final byte[] eoR = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; + + private static final int[] cpF = { SolverCorner.UFL, SolverCorner.DLF, SolverCorner.ULB, SolverCorner.UBR, SolverCorner.URF, SolverCorner.DFR, SolverCorner.DBL, SolverCorner.DRB }; + private static final byte[] coF = { 1, 2, 0, 0, 2, 1, 0, 0 }; + private static final int[] epF = { SolverEdge.UR, SolverEdge.FL, SolverEdge.UL, SolverEdge.UB, SolverEdge.DR, SolverEdge.FR, SolverEdge.DL, SolverEdge.DB, SolverEdge.UF, SolverEdge.DF, SolverEdge.BL, SolverEdge.BR }; + private static final byte[] eoF = { 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0 }; + + private static final int[] cpD = { SolverCorner.URF, SolverCorner.UFL, SolverCorner.ULB, SolverCorner.UBR, SolverCorner.DLF, SolverCorner.DBL, SolverCorner.DRB, SolverCorner.DFR }; + private static final byte[] coD = { 0, 0, 0, 0, 0, 0, 0, 0 }; + private static final int[] epD = { SolverEdge.UR, SolverEdge.UF, SolverEdge.UL, SolverEdge.UB, SolverEdge.DF, SolverEdge.DL, SolverEdge.DB, SolverEdge.DR, SolverEdge.FR, SolverEdge.FL, SolverEdge.BL, SolverEdge.BR }; + private static final byte[] eoD = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; + + private static final int[] cpL = { SolverCorner.URF, SolverCorner.ULB, SolverCorner.DBL, SolverCorner.UBR, SolverCorner.DFR, SolverCorner.UFL, SolverCorner.DLF, SolverCorner.DRB }; + private static final byte[] coL = { 0, 1, 2, 0, 0, 2, 1, 0 }; + private static final int[] epL = { SolverEdge.UR, SolverEdge.UF, SolverEdge.BL, SolverEdge.UB, SolverEdge.DR, SolverEdge.DF, SolverEdge.FL, SolverEdge.DB, SolverEdge.FR, SolverEdge.UL, SolverEdge.DL, SolverEdge.BR }; + private static final byte[] eoL = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }; + + private static final int[] cpB = { SolverCorner.URF, SolverCorner.UFL, SolverCorner.UBR, SolverCorner.DRB, SolverCorner.DFR, SolverCorner.DLF, SolverCorner.ULB, SolverCorner.DBL }; + private static final byte[] coB = { 0, 0, 1, 2, 0, 0, 2, 1 }; + private static final int[] epB = { SolverEdge.UR, SolverEdge.UF, SolverEdge.UL, SolverEdge.BR, SolverEdge.DR, SolverEdge.DF, SolverEdge.DL, SolverEdge.BL, SolverEdge.FR, SolverEdge.FL, SolverEdge.UB, SolverEdge.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 SolverCubieCube[] moveCube = new SolverCubieCube[6]; + + static + { + moveCube[0] = new SolverCubieCube(); + moveCube[0].cp = cpU; + moveCube[0].co = coU; + moveCube[0].ep = epU; + moveCube[0].eo = eoU; + + moveCube[1] = new SolverCubieCube(); + moveCube[1].cp = cpR; + moveCube[1].co = coR; + moveCube[1].ep = epR; + moveCube[1].eo = eoR; + + moveCube[2] = new SolverCubieCube(); + moveCube[2].cp = cpF; + moveCube[2].co = coF; + moveCube[2].ep = epF; + moveCube[2].eo = eoF; + + moveCube[3] = new SolverCubieCube(); + moveCube[3].cp = cpD; + moveCube[3].co = coD; + moveCube[3].ep = epD; + moveCube[3].eo = eoD; + + moveCube[4] = new SolverCubieCube(); + moveCube[4].cp = cpL; + moveCube[4].co = coL; + moveCube[4].ep = epL; + moveCube[4].eo = eoL; + + moveCube[5] = new SolverCubieCube(); + 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; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + SolverCubieCube() + { + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// 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 + + SolverFaceCube toFaceCube() + { + SolverFaceCube fcRet = new SolverFaceCube(); + + for(int c = SolverCorner.URF; c<= SolverCorner.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[SolverFaceCube.cornerFacelet[c][(n + ori) % 3]] = SolverFaceCube.cornerColor[j][n]; + } + + for(int e = SolverEdge.UR; e<= SolverEdge.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[SolverFaceCube.edgeFacelet[e][(n + ori) % 2]] = SolverFaceCube.edgeColor[j][n]; + } + + return fcRet; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// return the twist of the 8 corners. 0 <= twist < 3^7 + + short getTwist() + { + short ret = 0; + + for(int i = SolverCorner.URF; i< SolverCorner.DRB; i++) + ret = (short) (3*ret+co[i]); + + return ret; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + void setTwist(short twist) + { + int twistParity = 0; + + for (int i = SolverCorner.DRB-1; i>= SolverCorner.URF; i--) + { + twistParity += co[i] = (byte) (twist%3); + twist /= 3; + } + co[SolverCorner.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 = SolverEdge.UR; i< SolverEdge.BR; i++) + ret = (short) (2 * ret + eo[i]); + + return ret; + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + void setFlip(short flip) + { + int flipParity = 0; + + for (int i = SolverEdge.BR-1; i>= SolverEdge.UR; i--) + { + flipParity += eo[i] = (byte) (flip % 2); + flip /= 2; + } + eo[SolverEdge.BR] = (byte) ((2 - flipParity % 2) % 2); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Parity of the corner permutation + + short cornerParity() + { + int s = 0; + + for (int i = SolverCorner.DRB; i>= SolverCorner.URF+1; i--) + for (int j = i - 1; j >= SolverCorner.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 = SolverEdge.BR; i >= SolverEdge.UR+1; i--) + for (int j = i - 1; j >= SolverEdge.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 = SolverEdge.BR; j >= SolverEdge.UR; j--) + if (SolverEdge.FR <= ep[j] && ep[j] <= SolverEdge.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 = SolverCorner.URF; j<= SolverCorner.DRB; j++) + if( cp[j] <= SolverCorner.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 = SolverEdge.UR; j<= SolverEdge.BR; j++) + if (ep[j] <= SolverEdge.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 = SolverEdge.UR; j<= SolverEdge.BR; j++) + if (ep[j] <= SolverEdge.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 = SolverEdge.UR; j<= SolverEdge.BR; j++) + if (SolverEdge.UB <= ep[j] && ep[j] <= SolverEdge.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] != SolverEdge.UB + j) + { + rotateLeft(tmpEdge3,j); + k++; + } + b = (j+1)*b+k; + } + + return (short) (6*a+b); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + void setURFtoDLB(int idx) + { + int[] perm = { SolverCorner.URF, SolverCorner.UFL, SolverCorner.ULB, SolverCorner.UBR, SolverCorner.DFR, SolverCorner.DLF, SolverCorner.DBL, SolverCorner.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 = { SolverEdge.UR, SolverEdge.UF, SolverEdge.UL, SolverEdge.UB, SolverEdge.DR, SolverEdge.DF, SolverEdge.DL, SolverEdge.DB, SolverEdge.FR, SolverEdge.FL, SolverEdge.BL, SolverEdge.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 = SolverEdge.UR; e <= SolverEdge.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 = SolverCorner.URF; c<= SolverCorner.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/SolverEdge.java b/src/main/java/org/distorted/solvers/cube3/SolverEdge.java new file mode 100644 index 00000000..3dacf784 --- /dev/null +++ b/src/main/java/org/distorted/solvers/cube3/SolverEdge.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 SolverEdge + { + 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/SolverFaceCube.java b/src/main/java/org/distorted/solvers/cube3/SolverFaceCube.java new file mode 100644 index 00000000..c2c0c157 --- /dev/null +++ b/src/main/java/org/distorted/solvers/cube3/SolverFaceCube.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 SolverFaceCube +{ + 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 = + { { SolverFacelet.U9, SolverFacelet.R1, SolverFacelet.F3 }, { SolverFacelet.U7, SolverFacelet.F1, SolverFacelet.L3 }, + { SolverFacelet.U1, SolverFacelet.L1, SolverFacelet.B3 }, { SolverFacelet.U3, SolverFacelet.B1, SolverFacelet.R3 }, + { SolverFacelet.D3, SolverFacelet.F9, SolverFacelet.R7 }, { SolverFacelet.D1, SolverFacelet.L9, SolverFacelet.F7 }, + { SolverFacelet.D7, SolverFacelet.B9, SolverFacelet.L7 }, { SolverFacelet.D9, SolverFacelet.R9, SolverFacelet.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 = + { { SolverFacelet.U6, SolverFacelet.R2 }, { SolverFacelet.U8, SolverFacelet.F2 }, { SolverFacelet.U4, SolverFacelet.L2 }, + { SolverFacelet.U2, SolverFacelet.B2 }, { SolverFacelet.D6, SolverFacelet.R8 }, { SolverFacelet.D2, SolverFacelet.F8 }, + { SolverFacelet.D4, SolverFacelet.L8 }, { SolverFacelet.D8, SolverFacelet.B8 }, { SolverFacelet.F6, SolverFacelet.R4 }, + { SolverFacelet.F4, SolverFacelet.L6 }, { SolverFacelet.B6, SolverFacelet.L4 }, { SolverFacelet.B4, SolverFacelet.R6 } }; + + // Map the corner positions to facelet colors. + final static int[][] cornerColor = + { { SolverColor.U, SolverColor.R, SolverColor.F }, { SolverColor.U, SolverColor.F, SolverColor.L }, + { SolverColor.U, SolverColor.L, SolverColor.B }, { SolverColor.U, SolverColor.B, SolverColor.R }, + { SolverColor.D, SolverColor.F, SolverColor.R }, { SolverColor.D, SolverColor.L, SolverColor.F }, + { SolverColor.D, SolverColor.B, SolverColor.L }, { SolverColor.D, SolverColor.R, SolverColor.B } }; + + // Map the edge positions to facelet colors. + final static int[][] edgeColor = + { { SolverColor.U, SolverColor.R }, { SolverColor.U, SolverColor.F }, { SolverColor.U, SolverColor.L }, + { SolverColor.U, SolverColor.B }, { SolverColor.D, SolverColor.R }, { SolverColor.D, SolverColor.F }, + { SolverColor.D, SolverColor.L }, { SolverColor.D, SolverColor.B }, { SolverColor.F, SolverColor.R }, + { SolverColor.F, SolverColor.L }, { SolverColor.B, SolverColor.L }, { SolverColor.B, SolverColor.R } }; + +/////////////////////////////////////////////////////////////////////////////////////////////////// + + SolverFaceCube() + { + String s = "UUUUUUUUURRRRRRRRRFFFFFFFFFDDDDDDDDDLLLLLLLLLBBBBBBBBB"; + + for( int i=0; i<54; i++) + f[i] = SolverColor.toInt(s.substring(i, i + 1)); + } + +/////////////////////////////////////////////////////////////////////////////////////////////////// +// Construct a facelet cube from a string + + SolverFaceCube(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 SolverFacelet + { + 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/SolverSearch.java b/src/main/java/org/distorted/solvers/cube3/SolverSearch.java new file mode 100644 index 00000000..12a30973 --- /dev/null +++ b/src/main/java/org/distorted/solvers/cube3/SolverSearch.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 SolverSearch +{ + 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] = SolverCoordCube.getFlipMove(flip[n],mv); + twist[n+1] = SolverCoordCube.getTwistMove(twist[n],mv); + slice[n+1] = SolverCoordCube.getFRtoBR_Move(slice[n] * 24,mv) / 24; + minDistPhase1[n+1] = Math.max(SolverCoordCube.getPruning(SolverCoordCube.Slice_Flip_Prun, SolverCoordCube.N_SLICE1 * flip[n+1] + + slice[n+1]), SolverCoordCube.getPruning(SolverCoordCube.Slice_Twist_Prun, SolverCoordCube.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] = SolverCoordCube.getURFtoDLF_Move(URFtoDLF[n],mv); + FRtoBR [n+1] = SolverCoordCube.getFRtoBR_Move(FRtoBR[n],mv); + parity [n+1] = SolverCoordCube.parityMove[parity[n]][mv]; + URtoDF [n+1] = SolverCoordCube.getURtoDF_Move(URtoDF[n],mv); + + minDistPhase2[n+1] = Math.max(SolverCoordCube.getPruning(SolverCoordCube.Slice_URtoDF_Parity_Prun, (SolverCoordCube.N_SLICE2 + * URtoDF[n+1] + FRtoBR[n+1]) + * 2 + parity[n+1]), SolverCoordCube.getPruning(SolverCoordCube.Slice_URFtoDLF_Parity_Prun, (SolverCoordCube.N_SLICE2 + * URFtoDLF[n+1] + FRtoBR[n+1]) + * 2 + parity[n+1])); + } + while (minDistPhase2[n + 1] != 0); + + return depthPhase1 + depthPhase2; + } +}