Trying to solve a rubiks cube in Java

Question

I have developed a class so far that can represent a rubiks cube using a treemap (best way?) each color is mapped to a key 0 - 53. the keys always stay the same and are represented by a 2D view of the cube. I made a rotate90 method that will take a color and rotate that colors face (the middle cubies never move) 90 degrees clockwise. So my question is, how do I implement a good search (maybe A*?) to get this cube to go in the right direction to its goalState(which I initialized as well in the code as a global so I can compare it to the current state). Any feedback or hints in the right direction would be great. Thanks!

Here is the code without the rotate 90 method and a checkInput method that just checks if the file text is okay. The input is just a text file that represents the 2D cube and looks like this. The solve method right now is just me messing around and not really getting anywhere.

   GGW
   RRG
   RRG
OWWGGOYYR
OGOYYYRBR
YYYRBGRWW
   BOY
   BOB
   BOB
   OGO
   WWB
   WWB

package rubik;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.NavigableMap;
import java.util.TreeMap;

public class RubikCube {
final static String FILE_NAME = "rubikTest.txt";
public TreeMap<Integer, Character> goalState;


//swaps two colors given a cube
public static void swapColorValue(int color1, int color2, TreeMap<Integer, Character> rubik){
    char tempColor = rubik.get(color1);
    rubik.put(color1,rubik.get(color2));
    rubik.put(color2, tempColor);
}

//initialize the goal map
public void goalInit(TreeMap<Integer, Character> rubik){
    //initialize the goal state map each rubik.get(magicNumber) is the static center cubie
    TreeMap<Integer, Character> goalMap = new TreeMap<Integer,Character>();
    for(int i =0;i<=8;i++){
    goalMap.put(i,rubik.get(4));
    }
    //the left side
    goalMap.put(9, rubik.get(19));
    goalMap.put(10, rubik.get(19));
    goalMap.put(11, rubik.get(19));
    goalMap.put(18, rubik.get(19));
    goalMap.put(19, rubik.get(19));
    goalMap.put(20, rubik.get(19));
    goalMap.put(27, rubik.get(19));
    goalMap.put(28, rubik.get(19));
    goalMap.put(29, rubik.get(19));
    //the middle
    goalMap.put(12, rubik.get(22));
    goalMap.put(13, rubik.get(22));
    goalMap.put(14, rubik.get(22));
    goalMap.put(21, rubik.get(22));
    goalMap.put(22, rubik.get(22));
    goalMap.put(23, rubik.get(22));
    goalMap.put(30, rubik.get(22));
    goalMap.put(31, rubik.get(22));
    goalMap.put(32, rubik.get(22));
    //right side
    goalMap.put(15, rubik.get(25));
    goalMap.put(16, rubik.get(25));
    goalMap.put(17, rubik.get(25));
    goalMap.put(24, rubik.get(25));
    goalMap.put(25, rubik.get(25));
    goalMap.put(26, rubik.get(25));
    goalMap.put(33, rubik.get(25));
    goalMap.put(34, rubik.get(25));
    goalMap.put(35, rubik.get(25));
    //bottom
    for(int i = 36;i<=44;i++){
        goalMap.put(i, rubik.get(40));
    }
    //back
    for(int i = 45;i<=53;i++){
        goalMap.put(i, rubik.get(49));
    }
    //give it to the global variable
    goalState = (TreeMap<Integer, Character>) goalMap.clone();

}

//Maps a Integer key to a color given a file.
public static NavigableMap<Integer, Character> setup(String file) throws IOException{
    TreeMap<Integer, Character> rubik = new TreeMap<Integer, Character>();
    BufferedReader br = new BufferedReader(new FileReader(file));
    try {
        StringBuilder sb = new StringBuilder();
        String line = br.readLine();
        //add each line (without white spaces) to the stringbuilder
        while (line != null) {
            sb.append(line.trim());
            line = br.readLine();
        }
        //convert the stringbuilder(which has all the input from the file) to a char array
        char [] colors = sb.toString().toCharArray();
        //put the key,color into the Treemap.
        for(int i =0; i < colors.length;i++){
            rubik.put(i, colors[i]);
        }
    } finally {
        br.close();
    }
    //type Tree map
    return rubik;

    }

public int solve(TreeMap<Integer, Character> rubik){
    int j = 1;
    int check = 0;
    int redMatches=0;
    char [] colors = {'r','g','y','b','o','w'};

    for(int i = 0; i < 100;i++ ){
        if(j==6) j = 1;
        redMatches = 0;
        rotate90(colors[j],rubik);
        if(rubik.get(check)==goalState.get(check)){
            System.out.print("rubik match at: "+i+" with: "+rubik.get(i)+"match at goalState: "+i+" with: "+goalState.get(i));
            redMatches++;
        }

        j++;
    }


    return redMatches;
}

public static void main (String[] args){
    try {
        //check if file input is good
        //System.out.print(new RubikCube().checkInput(FILE_NAME));
        //Map the rubik cube(key,Color)
        RubikCube cubeInst = new RubikCube();
        //make sure to set up the mapping before calling rotate and goalInit    
        TreeMap<Integer, Character> cube = (TreeMap<Integer, Character>) (setup(FILE_NAME));
        cubeInst.goalInit(cube);
        //System.out.print(cubeInst.goalState);
        //rotate90('y',cube);
        //rotate90('y',cube);
        //System.out.print(cube);
        System.out.print(cubeInst.solve(cube));
    } catch (IOException e) {
        e.printStackTrace();
    }
}

}

Answer 1

I've never written code to solve a Rubik's cube but if you are using a heuristic graph traversal algorithm like A*, I can think of few good heuristics to tell how far away from the goal you are:

1. Number of misplaced cubbies.

2. Summation of how far away each cubbie is from the goal state, possibly using Manhattan distance to tell how far away it is.

The problem is that I don't think you can just use a color for each cubbie state. You might need to represent the cube as a datastructure positions from some arbitrary angle. So for example "top left corner" is the top left corner piece in the goal state (which is also the corner cubbie on the left side and back side...) Then you will know if your "top left corner" cubbie is out of place.