TwistyPuzzleLib

  ///////////////////////////////////////////

  // STRINGS

  ///////////////////////////////////////////

  String getString(int id);

  String getString(int id, String s1);

  String getString(int id, String s1, String s2);

  String getString(int id, String s1, String s2, String s3);

/*

 * Herbert Kociemba

 *

 * BSD-licensed. See https://opensource.org/licenses/BSD-3-Clause

 */

package org.distorted.objectlib.kociemba;

///////////////////////////////////////////////////////////////////////////////////////////////////

// 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;

      }  

    }

  }

/*

 * Herbert Kociemba

 *

 * BSD-licensed. See https://opensource.org/licenses/BSD-3-Clause

 */

package org.distorted.objectlib.kociemba;

import java.io.InputStream;

import org.distorted.objectlib.R;

import org.distorted.objectlib.helpers.OperatingSystemInterface;

///////////////////////////////////////////////////////////////////////////////////////////////////

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 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[]

			{

			R.raw.cube3solver_table1,

			R.raw.cube3solver_table2,

			R.raw.cube3solver_table3,

			R.raw.cube3solver_table4,

			R.raw.cube3solver_table5,

			R.raw.cube3solver_table6,

			R.raw.cube3solver_table7,

			R.raw.cube3solver_table8,

			R.raw.cube3solver_table9,

			R.raw.cube3solver_table10,

			R.raw.cube3solver_table11,

			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(OperatingSystemInterface os, int index)

		{

		if( !init[index] )

		  {

		  try

		    {

		    byte[] table = tableOfTables[index];

			  InputStream is = os.openLocalFile(resourceTable[index]);

		    is.read( table, 0, table.length);

		    }

		  catch(Exception ioe)

		    {

		    System.out.println("error reading table"+index);

		    }

		  init[index]=true;

		  }

		}

}

/*

 * Herbert Kociemba

 *

 * BSD-licensed. See https://opensource.org/licenses/BSD-3-Clause

 */

package org.distorted.objectlib.kociemba;

///////////////////////////////////////////////////////////////////////////////////////////////////

//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;

  }

/*

 * Herbert Kociemba

 *

 * BSD-licensed. See https://opensource.org/licenses/BSD-3-Clause

 */

package org.distorted.objectlib.kociemba;

///////////////////////////////////////////////////////////////////////////////////////////////////

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<r; i++) arr[i] = arr[i + 1];

    arr[r] = tmp;

    }

///////////////////////////////////////////////////////////////////////////////////////////////////

// Right rotation of all array elements between l and r

  static void rotateRight(int[] arr, int r)

    {

    int tmp = arr[r];

    for (int i = r; 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

    }

}

/*

 * Herbert Kociemba

 *

 * BSD-licensed. See https://opensource.org/licenses/BSD-3-Clause

 */

package org.distorted.objectlib.kociemba;

///////////////////////////////////////////////////////////////////////////////////////////////////

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;

  }

/*

 * Herbert Kociemba

 *

 * BSD-licensed. See https://opensource.org/licenses/BSD-3-Clause

 */

package org.distorted.objectlib.kociemba;

///////////////////////////////////////////////////////////////////////////////////////////////////

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<cubeString.length(); i++)

	    f[i] = SolverColor.toInt(cubeString.substring(i, i + 1));

	  }

///////////////////////////////////////////////////////////////////////////////////////////////////

// Gives string representation of a facelet cube

	String to_String()

    {

	  String s = "";

	  for (int i = 0; i < 54; i++)

	    s += SolverColor.toString(f[i]);

    return s;

	  }

///////////////////////////////////////////////////////////////////////////////////////////////////

// Gives CubieCube representation of a faceletcube

	SolverCubieCube toCubieCube()

    {

	  byte ori;

	  SolverCubieCube ccRet = new SolverCubieCube();

    for( int i=0; i< 8; i++) ccRet.cp[i] = SolverCorner.URF; // invalidate corners

	  for( int i=0; i<12; i++) ccRet.ep[i] = SolverEdge.UR;    // and edges

	  int col1, col2;

	  for(int i = SolverCorner.URF; i<= SolverCorner.DRB; i++)

      {

	    // get the colors of the cubie at corner i, starting with U/D

	    for (ori = 0; ori < 3; ori++)

	      if (f[cornerFacelet[i][ori]] == SolverColor.U || f[cornerFacelet[i][ori]] == SolverColor.D)

		      break;

	    col1 = f[cornerFacelet[i][(ori+1)%3]];

	    col2 = f[cornerFacelet[i][(ori+2)%3]];

	    for(int j = SolverCorner.URF; j<= SolverCorner.DRB; j++)

        {

	      if( col1==cornerColor[j][1] && col2==cornerColor[j][2])

          {

		      // in cornerposition i we have cornercubie j

		      ccRet.cp[i] = j;

		      ccRet.co[i] = (byte) (ori % 3);

		      break;

		      }

	      }

	    }

    for(int i = SolverEdge.UR; i<= SolverEdge.BR; i++)

      {

	    for(int j = SolverEdge.UR; j<= SolverEdge.BR; j++)

        {

        if( f[edgeFacelet[i][0]]==edgeColor[j][0] && f[edgeFacelet[i][1]]==edgeColor[j][1])

          {

		      ccRet.ep[i] = j;

		      ccRet.eo[i] = 0;

		      break;

		      }

        if( f[edgeFacelet[i][0]]==edgeColor[j][1] && f[edgeFacelet[i][1]]==edgeColor[j][0])

          {

		      ccRet.ep[i] = j;

		      ccRet.eo[i] = 1;

		      break;

          }

	      }

	    }

	return ccRet;

	}

}

/*

 * Herbert Kociemba

 *

 * BSD-licensed. See https://opensource.org/licenses/BSD-3-Clause

 */

package org.distorted.objectlib.kociemba;

/**

 * <pre>

 * 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*|

 *             |************|

 * </pre>

 * 

 *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;

  }

/*

 * Herbert Kociemba

 *

 * BSD-licensed. See https://opensource.org/licenses/BSD-3-Clause

 */

package org.distorted.objectlib.kociemba;

import org.distorted.objectlib.helpers.OperatingSystemInterface;

///////////////////////////////////////////////////////////////////////////////////////////////////

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<length; i++)

		  {

			switch(ax[i])

			  {

			  case 0: switch(po[i])

			            {

			            case 1: s.append(" 548"); break;

			            case 2: s.append(" 804"); break;

			            case 3: s.append(" 292"); break;

			            }

				        break;

			  case 1: switch(po[i])

	                {

	                case 1: s.append(" 516"); break;

	                case 2: s.append(" 772"); break;

	                case 3: s.append(" 260"); break;

	                }

				        break;

		  	case 2: switch(po[i])

                  {

                  case 1: s.append(" 580"); break;

                  case 2: s.append(" 836"); break;

                  case 3: s.append(" 324"); break;

                  }

				        break;

		  	case 3: switch(po[i])

                  {

                  case 1: s.append(" 289"); break;

                  case 2: s.append(" 033"); break;

                  case 3: s.append(" 545"); break;

                  }

				        break;

			  case 4: switch(po[i])

                  {

                  case 1: s.append(" 257"); break;

                  case 2: s.append(" 001"); break;

                  case 3: s.append(" 513"); break;

                  }

				        break;

			  case 5: switch(po[i])

                  {

                  case 1: s.append(" 321"); break;

                  case 2: s.append(" 065"); break;

                  case 3: s.append(" 577"); break;

                  }

				        break;

			  }

		  }

		return s.toString();

	}

///////////////////////////////////////////////////////////////////////////////////////////////////

	public static void prepare(OperatingSystemInterface os)

	  {

	  SolverCoordCube.initialize(os,0);

    SolverCoordCube.initialize(os,1);

		SolverCoordCube.initialize(os,2);

		SolverCoordCube.initialize(os,3);

		SolverCoordCube.initialize(os,4);

		SolverCoordCube.initialize(os,5);

		SolverCoordCube.initialize(os,6);

		SolverCoordCube.initialize(os,7);

		SolverCoordCube.initialize(os,8);

		SolverCoordCube.initialize(os,9);

		SolverCoordCube.initialize(os,10);

		SolverCoordCube.initialize(os,11);

	  }

///////////////////////////////////////////////////////////////////////////////////////////////////

/**

 * Computes the solver string for a given cube.

 *

 * @param facelets

 *          is the cube definition string, see {@link SolverFacelet} for the format.

 *

 * @param maxDepth

 *          defines the maximal allowed maneuver length. For random cubes, a maxDepth of 21 usually

 *          will return a solution in less than 0.5 seconds. With a maxDepth of 20 it takes a few

 *          seconds on average to find a solution, but it may take much longer for specific cubes.

 *

 *@param timeOut

 *          defines the maximum computing time of the method in seconds. If it does not return with

 *          a solution, it returns with an error code.

 * @return The solution string or an error code:

 *         Error 1: There is not exactly one facelet of each color

 *         Error 2: Not all 12 edges exist exactly once

 *         Error 3: Flip error: One edge has to be flipped

 *         Error 4: Not all corners exist exactly once

 *         Error 5: Twist error: One corner has to be twisted

 *         Error 6: Parity error: Two corners or two edges have to be exchanged

 *         Error 7: No solution exists for the given maxDepth

 *         Error 8: Timeout, no solution within given time

 */

	public static String solution(String facelets, int maxDepth, long timeOut) 

	  {

		int s;

		int[] count = new int[6];

		try

		  {

			for( int i=0; i<54; i++)

				count[SolverColor.toInt(facelets.substring(i,i+1))]++;

		  }

		catch (Exception e)

		  {

		  android.util.Log.d("error", "1");

			return "Error 1";

		  }

		for( int i=0; i<6; i++)

			if (count[i] != 9)

			  {

			  android.util.Log.d("error", "2");

				return "Error 1";

				}

		SolverFaceCube fc = new SolverFaceCube(facelets);

		SolverCubieCube cc = fc.toCubieCube();

		if ((s = cc.verify()) != 0)

		  {

		  android.util.Log.d("error", "3");

			return "Error " + Math.abs(s);

			}

		SolverCoordCube c = new SolverCoordCube(cc);

		po[0] = 0;

		ax[0] = 0;

		flip[0] = c.flip;

		twist[0] = c.twist;

		parity[0] = c.parity;

		slice[0] = c.FRtoBR / 24;

		URFtoDLF[0] = c.URFtoDLF;

		FRtoBR[0] = c.FRtoBR;

		URtoUL[0] = c.URtoUL;

		UBtoDF[0] = c.UBtoDF;

		minDistPhase1[1] = 1;// else failure for depth=1, n=0

		int mv, n=0;

		boolean busy = false;

		int depthPhase1 = 1;

		long tStart = System.currentTimeMillis();

		do

		  {

			do

			  {

				if( (depthPhase1-n > minDistPhase1[n+1]) && !busy)

				  {

					if (ax[n]==0 || ax[n]==3)// Initialize next move

						ax[++n] = 1;

					else

						ax[++n] = 0;

					po[n] = 1;

				  }

				else if (++po[n] > 3)

				  {

					do

					  { // increment axis

						if (++ax[n] > 5)

						  {

							if (System.currentTimeMillis() - tStart > timeOut << 10)

								return "Error 8";

							if (n==0)

							  {

								if (depthPhase1 >= maxDepth)

									return "Error 7";

								else

								  {

									depthPhase1++;

									ax[n] = 0;

									po[n] = 1;

									busy = false;

									break;

								  }

							  }

							else

							  {

								n--;

								busy = true;

								break;

							  }

						  }

						else

						  {

							po[n] = 1;

							busy = false;

						  }

					  }

					while (n != 0 && (ax[n - 1] == ax[n] || ax[n - 1] - 3 == ax[n]));

				  }

				else

					busy = false;

			  }

			while (busy);

			// compute new coordinates and new minDistPhase1. If minDistPhase1 =0, the H subgroup is reached

			mv = 3*ax[n]+po[n]-1;

			flip [n+1] = 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<depthPhase1; i++)

		  {

			mv = 3*ax[i]+po[i]-1;

			URFtoDLF[i+1] = SolverCoordCube.getURFtoDLF_Move(URFtoDLF[i],mv);

			FRtoBR  [i+1] = SolverCoordCube.getFRtoBR_Move(FRtoBR[i],mv);

			parity  [i+1] = SolverCoordCube.parityMove[parity[i]][mv];

		  }

		if( (d1 = SolverCoordCube.getPruning(SolverCoordCube.Slice_URFtoDLF_Parity_Prun,

				(SolverCoordCube.N_SLICE2 * URFtoDLF[depthPhase1] + FRtoBR[depthPhase1]) * 2 + parity[depthPhase1])) > maxDepthPhase2)

			return -1;

		for( int i=0; i<depthPhase1; i++)

		  {

			mv = 3 * ax[i] + po[i] - 1;

			URtoUL[i + 1] = SolverCoordCube.getURtoUL_Move(URtoUL[i],mv);

			UBtoDF[i + 1] = SolverCoordCube.getUBtoDF_Move(UBtoDF[i],mv);

		  }

		URtoDF[depthPhase1] = SolverCoordCube.getMergeURtoULandUBtoDF(URtoUL[depthPhase1],UBtoDF[depthPhase1]);

		if ((d2 = SolverCoordCube.getPruning(SolverCoordCube.Slice_URtoDF_Parity_Prun,

				(SolverCoordCube.N_SLICE2 * URtoDF[depthPhase1] + FRtoBR[depthPhase1]) * 2 + parity[depthPhase1])) > maxDepthPhase2)

			return -1;

		if ((minDistPhase2[depthPhase1] = Math.max(d1, d2)) == 0)// already solved

			return depthPhase1;

		// now set up search

		int depthPhase2 = 1;

		int n = depthPhase1;

		boolean busy = false;

		po[depthPhase1] = 0;

		ax[depthPhase1] = 0;

		minDistPhase2[n + 1] = 1; // else failure for depthPhase2=1, n=0

		// end initialization

		do

		  {

			do

			  {

				if ((depthPhase1 + depthPhase2 - n > minDistPhase2[n + 1]) && !busy)

				  {

					if (ax[n] == 0 || ax[n] == 3)// Initialize next move

					  {

						ax[++n] = 1;

						po[n] = 2;

					  }

					else

					  {

						ax[++n] = 0;

						po[n] = 1;

					  }

				  }

				else if ((ax[n] == 0 || ax[n] == 3) ? (++po[n] > 3) : ((po[n] = po[n] + 2) > 3))

				  {

					do

					  {

						if (++ax[n] > 5)

						  {

							if (n == depthPhase1)

							  {