Magic Cube

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

// 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 <http://www.gnu.org/licenses/>.                           //

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

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<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(Resources res)

	  {

	  SolverCoordCube.initialize(res,0);

    SolverCoordCube.initialize(res,1);

		SolverCoordCube.initialize(res,2);

		SolverCoordCube.initialize(res,3);

		SolverCoordCube.initialize(res,4);

		SolverCoordCube.initialize(res,5);

		SolverCoordCube.initialize(res,6);

		SolverCoordCube.initialize(res,7);

		SolverCoordCube.initialize(res,8);

		SolverCoordCube.initialize(res,9);

		SolverCoordCube.initialize(res,10);

		SolverCoordCube.initialize(res,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)

							  {

								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;

	  }

}