rubikscube
college code for finding optimal rubiks cube solutions in java
git clone https://9o.is/git/rubikscube.git
commit a08bdf9ae30e30217242f31d4405c3d9959a81aa parent e9f5d3c87ced5bfa904f92eac6fe0945235f0955 Author: Jul <jul@9o.is> Date: Thu, 25 Oct 2012 04:28:25 -0400 Made alot of changes, but hasn't been tested yet. Diffstat:
| M | src/PatternTable.java | | | 12 | +++++++----- |
| D | src/RubiksAttainableState.java | | | 48 | ------------------------------------------------ |
| M | src/RubiksColor.java | | | 26 | +++++++++++++++++++++++--- |
| A | src/RubiksCornerState.java | | | 72 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | src/RubiksCube.java | | | 434 | ++++++++++++++++++++++++++++++++++++++++++++++++++++--------------------------- |
| A | src/RubiksHalf2EdgeState.java | | | 69 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | src/RubiksHalfEdgeState.java | | | 69 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | src/RubiksPatternTable.java | | | 26 | ++++++++++++-------------- |
| D | src/RubiksRotation.java | | | 31 | ------------------------------- |
| M | src/RubiksState.java | | | 75 | +++++++++++++++++++++++---------------------------------------------------- |
| A | src/RubiksSubState.java | | | 64 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | src/RubiksTest.java | | | 55 | +++++++++++++++++++++++++++++++++++++++++++++++++------ |
12 files changed, 675 insertions(+), 306 deletions(-)
diff --git a/src/PatternTable.java b/src/PatternTable.java @@ -18,19 +18,20 @@ public class PatternTable { } /** - * Updates the pattern table with a new RubiksAttainableState's + * Updates the pattern table with a new RubiksSubState's * key and value. - * @param attainable The RubiksAttainableState to store. + * @param state The RubiksSubState to store. */ - public void updateTable(RubiksAttainableState attainable) { + public void updateTable(RubiksSubState state) { try { BufferedWriter out = new BufferedWriter(new FileWriter(file,true)); - out.write(attainable.getKey()+":"+ - Short.toString(attainable.getHeuristic())+"\n"); + out.write(state.getState()+":"+ + Short.toString(state.getHeuristic())+"\n"); out.close(); } catch (IOException e) { System.err.println("Error: " + e.getMessage()); + e.printStackTrace(); } } @@ -45,6 +46,7 @@ public class PatternTable { out.close(); } catch (IOException e) { System.err.println("Error: " + e.getMessage()); + e.printStackTrace(); } } diff --git a/src/RubiksAttainableState.java b/src/RubiksAttainableState.java @@ -1,48 +0,0 @@ -/** - * Holds part of the state of the rubik's cube like the corners - * or just the edges with a heuristic that measures the amount of - * moves away from the goal state. - * - * RubiksState and RubiksAttainableState are very similar, but the - * difference is that RubiksState has more memory consumption with - * three strings (excluding a heuristic); not very feasible for - * generating very large pattern tables. - */ -public class RubiksAttainableState { - - /* The key is the state of this RubiksAttainableState. */ - private String key; - - /* The heuristic of this RubiksAttainableState. */ - private byte heuristic; - - /** - * An RubiksAttainableState has a state as a key and a heuristic. - * @param key the state - * @param heuristic the heuristic (moves from the goal state). - */ - public RubiksAttainableState(String key, short heuristic) { - this.key = key; - this.heuristic = (byte) heuristic; - } - - public RubiksAttainableState(String key, int heuristic) { - this(key, (short) heuristic); - } - - /** - * Retrieve state. - * @return The key of RubiksAttainableState. - */ - public String getKey() { - return key; - } - - /** - * Retrieve heuristic. - * @return The heuristic of RubiksAttainableState. - */ - public short getHeuristic() { - return heuristic; - } -} diff --git a/src/RubiksColor.java b/src/RubiksColor.java @@ -1,3 +1,8 @@ +import java.util.Arrays; +import java.util.Collections; +import java.util.List; +import java.util.Random; + /** * Different kinds of colors in a Rubik's cube. */ @@ -7,8 +12,7 @@ public enum RubiksColor { BLUE ("B"), YELLOW ("Y"), ORANGE ("O"), - WHITE ("W"), - INVALID("~"); + WHITE ("W"); /* The color in string format. */ private final String string; @@ -24,15 +28,31 @@ public enum RubiksColor { * @return The correct RubiksColor of the string string. */ public static RubiksColor find(String string) { + string = string.toUpperCase(); if(string.equals("R")) return RED; else if(string.equals("G")) return GREEN; else if(string.equals("B")) return BLUE; else if(string.equals("Y")) return YELLOW; else if(string.equals("O")) return ORANGE; else if(string.equals("W")) return WHITE; - else return INVALID; + else return null; } + /** + * Picks a random rotation. + * @return The random rotation. + */ + public static RubiksColor randomColor() { + return VALUES.get(new Random().nextInt(SIZE)); + } + + /* Cached list of all possible values. */ + private static final List<RubiksColor> VALUES = + Collections.unmodifiableList(Arrays.asList(values())); + + /* Cached size of all possible values. */ + private static final int SIZE = VALUES.size(); + public String toString() { return this.string; } diff --git a/src/RubiksCornerState.java b/src/RubiksCornerState.java @@ -0,0 +1,72 @@ +import java.util.LinkedList; +import java.util.List; + +/** + * Holds part of the corner state of the rubik's cube with a + * heuristic that measures the amount of moves away from + * the goal state. + */ +public class RubiksCornerState extends RubiksSubState { + + private final String[][] COMBINATIONS = { + {"RGW", "GWR", "WRG"}, + {"RBW", "BWR", "WRB"}, + {"YGR", "GRY", "RYG"}, + {"YBR", "BRY", "RYB"}, + {"OGY", "GYO", "YOG"}, + {"OBY", "BYO", "YOB"}, + {"WGO", "GOW", "OWG"}, + {"WBO", "BOW", "OWB"}}; + + public RubiksCornerState(String state, int heuristic) throws Exception { + super(state, heuristic); + if(!isValid(state)) + throw new Exception(); + } + + public RubiksCornerState(String state) throws Exception { + super(state); + if(!isValid(state)) + throw new Exception(); + } + + + @Override + protected boolean isValid(String str) { + if(str.length() == 24) { + List<Integer> cornersChecked = new LinkedList<Integer>(); + for(int i=0; i<str.length(); i+=3) { + String corner = str.substring(i,i+3).toUpperCase(); + int check = isValidCorner(corner); + if(check == -1) return false; + else { + for(int cornerUsed : cornersChecked) { + if(cornerUsed == check) return false; + } + cornersChecked.add(check); + } + } + return true; + } + return false; + } + + @Override + //TODO + protected int hashState() { + return 0; + } + + /* + * Returns which corner out of all combinations is the string + * or -1 if it didn't match any. + */ + private int isValidCorner(String corner) { + for(int i=0; i<COMBINATIONS.length; i++) + for(int j=0; j<COMBINATIONS[i].length; j++) { + if(COMBINATIONS[i][j].equals(corner)) + return i; + } + return -1; + } +} diff --git a/src/RubiksCube.java b/src/RubiksCube.java @@ -1,3 +1,6 @@ +import java.io.BufferedReader; +import java.io.FileReader; +import java.io.IOException; import java.util.Random; /** @@ -52,60 +55,117 @@ public class RubiksCube { } /** + * Create a rubik's cube from a file. + * @param file The name of the file. + */ + public RubiksCube(FileReader file) { + try { + String result = ""; + BufferedReader in = new BufferedReader(file); + String str; + while ((str = in.readLine()) != null) { + result += str.trim(); + } + in.close(); + cube = new RubiksColor[CUBE_SIDES][CUBE_SIZE][CUBE_SIZE]; + setState(result); + } catch (IOException e) { + e.printStackTrace(); + } + } + + /** * Sets the state of this rubik's cube to a new given state. * @param state The new state to set for this rubik's cube. */ public void setState(RubiksState state) { - final int CORNERS = 4; //corners per side - RubiksColor[] cornerColors = - new RubiksColor[CUBE_SIDES*CORNERS]; - - int i=0; - for(char ch : state.getCorners().toCharArray()) { - cornerColors[i] = - RubiksColor.find(Character.toString(ch)); i++; - } - for(i=0; i<CUBE_SIDES; i++) - for(int j=0; j<CORNERS; j++) { - if(j==0) - cube[i][0][0] = cornerColors[i*CORNERS + j]; - else if(j==1) - cube[i][0][2] = cornerColors[i*CORNERS + j]; - else if(j==2) - cube[i][2][0] = cornerColors[i*CORNERS + j]; - else if(j==3) - cube[i][2][2] = cornerColors[i*CORNERS + j]; - } - - final int HALF_EDGES = 2; //half edges per side - RubiksColor[] halfEdgesColors = - new RubiksColor[CUBE_SIDES*HALF_EDGES]; - - i=0; - for(char ch : state.getHalfEdges().toCharArray()) { - halfEdgesColors[i] = - RubiksColor.find(Character.toString(ch)); i++; - } - for(i=0; i<CUBE_SIDES; i++) - for(int j=0; j<HALF_EDGES; j++) { - if(j==0) - cube[i][0][1] = halfEdgesColors[i*HALF_EDGES + j]; - else if(j==1) - cube[i][1][0] = halfEdgesColors[i*HALF_EDGES + j]; - } + String corners = state.getCorners().toString(); + // corner 1 + cube[0][0][0] = RubiksColor.find(corners.substring(0,1)); + cube[1][0][0] = RubiksColor.find(corners.substring(1,2)); + cube[5][2][0] = RubiksColor.find(corners.substring(2,3)); + // corner 2 + cube[0][0][2] = RubiksColor.find(corners.substring(3,4)); + cube[3][0][2] = RubiksColor.find(corners.substring(4,5)); + cube[5][2][2] = RubiksColor.find(corners.substring(5,6)); + // corner 3 + cube[2][0][0] = RubiksColor.find(corners.substring(6,7)); + cube[1][0][2] = RubiksColor.find(corners.substring(7,8)); + cube[0][2][0] = RubiksColor.find(corners.substring(8,9)); + // corner 4 + cube[2][0][2] = RubiksColor.find(corners.substring(9,10)); + cube[3][0][0] = RubiksColor.find(corners.substring(10,11)); + cube[0][2][2] = RubiksColor.find(corners.substring(11,12)); + // corner 5 + cube[4][0][0] = RubiksColor.find(corners.substring(12,13)); + cube[1][2][2] = RubiksColor.find(corners.substring(13,14)); + cube[2][2][0] = RubiksColor.find(corners.substring(14,15)); + // corner 6 + cube[4][0][2] = RubiksColor.find(corners.substring(15,16)); + cube[3][2][0] = RubiksColor.find(corners.substring(16,17)); + cube[2][2][2] = RubiksColor.find(corners.substring(17,18)); + // corner 7 + cube[5][0][0] = RubiksColor.find(corners.substring(18,19)); + cube[1][2][0] = RubiksColor.find(corners.substring(19,20)); + cube[4][2][0] = RubiksColor.find(corners.substring(20,21)); + // corner 8 + cube[5][0][2] = RubiksColor.find(corners.substring(21,22)); + cube[3][2][2] = RubiksColor.find(corners.substring(22,23)); + cube[4][2][2] = RubiksColor.find(corners.substring(23,24)); + + String halfEdges = state.getHalfEdges().toString(); + // edge 1 + cube[0][1][0] = RubiksColor.find(halfEdges.substring(0,1)); + cube[1][0][1] = RubiksColor.find(halfEdges.substring(1,2)); + // edge 2 + cube[0][0][1] = RubiksColor.find(halfEdges.substring(2,3)); + cube[5][2][1] = RubiksColor.find(halfEdges.substring(3,4)); + // edge 3 + cube[0][1][2] = RubiksColor.find(halfEdges.substring(4,5)); + cube[3][0][1] = RubiksColor.find(halfEdges.substring(5,6)); + // edge 4 + cube[0][2][1] = RubiksColor.find(halfEdges.substring(6,7)); + cube[2][0][1] = RubiksColor.find(halfEdges.substring(7,8)); + // edge 5 + cube[2][1][0] = RubiksColor.find(halfEdges.substring(8,9)); + cube[1][1][2] = RubiksColor.find(halfEdges.substring(9,10)); + // edge 6 + cube[2][1][2] = RubiksColor.find(halfEdges.substring(10,11)); + cube[3][1][0] = RubiksColor.find(halfEdges.substring(11,12)); + + String half2Edges = state.getHalf2Edges().toString(); + // edge 7 + cube[2][2][1] = RubiksColor.find(half2Edges.substring(0,1)); + cube[4][0][1] = RubiksColor.find(half2Edges.substring(1,2)); + // edge 8 + cube[4][1][0] = RubiksColor.find(half2Edges.substring(2,3)); + cube[1][2][1] = RubiksColor.find(half2Edges.substring(3,4)); + // edge 9 + cube[4][1][2] = RubiksColor.find(half2Edges.substring(4,5)); + cube[3][2][1] = RubiksColor.find(half2Edges.substring(5,6)); + // edge 10 + cube[4][2][1] = RubiksColor.find(half2Edges.substring(6,7)); + cube[5][0][1] = RubiksColor.find(half2Edges.substring(7,8)); + // edge 11 + cube[5][1][0] = RubiksColor.find(half2Edges.substring(8,9)); + cube[1][1][0] = RubiksColor.find(half2Edges.substring(9,10)); + // edge 12 + cube[5][1][2] = RubiksColor.find(half2Edges.substring(10,11)); + cube[3][1][2] = RubiksColor.find(half2Edges.substring(11,12)); + } - i=0; - for(char ch : state.getHalf2Edges().toCharArray()) { - halfEdgesColors[i] = - RubiksColor.find(Character.toString(ch)); i++; - } - for(i=0; i<CUBE_SIDES; i++) - for(int j=0; j<HALF_EDGES; j++) { - if(j==0) - cube[i][1][2] = halfEdgesColors[i*HALF_EDGES + j]; - else if(j==1) - cube[i][2][1] = halfEdgesColors[i*HALF_EDGES + j]; - } + /** + * Sets the state of this rubik's cube to a new given state. + * @param state The new state to set for this rubik's cube. + */ + public void setState(String state) { + int side,row,column, count=0; + for (side=0; side<CUBE_SIDES; side++) + for(row=0; row<CUBE_SIZE; row++) + for (column=0; column<CUBE_SIZE; column++) { + String input = state.substring(count, ++count); + cube[side][row][column] = RubiksColor.find(input); + } } /** @@ -136,8 +196,8 @@ public class RubiksCube { */ public void initRandomState() { for(int i=0; i<100; i++) { - rotate(new Random().nextInt(1), - RubiksRotation.randomRotation()); + rotate(new Random().nextInt(2), + RubiksColor.randomColor()); } } @@ -146,22 +206,102 @@ public class RubiksCube { * @return state of the current cube. */ public RubiksState getState() { - RubiksState state = new RubiksState(); - int side,row,column; - for(side=0; side<CUBE_SIDES; side++) - for(row=0; row<CUBE_SIZE; row++) - for (column=0; column<CUBE_SIZE; column++ ) { - if((row==0 || row==2) && (column==0 || column==2)) - state.setCorners(state.getCorners() + - cube[side][row][column]); - else if((row==0 || row==2) && column==1) - state.setHalfEdges(state.getHalfEdges() + - cube[side][row][column]); - else if(row==1 && (column==0 || column==2)) - state.setHalf2Edges(state.getHalf2Edges() + - cube[side][row][column]); - } - return state; + try { + return new RubiksState( + getCornerState(), + getHalfEdgeState(), + getHalf2EdgeState() + ); + } catch (Exception e) { + //this should never happen because the state should be + // checked in the first place at all times, + // but the 3d array made the cube an overkill. + e.printStackTrace(); + return null; + } + } + + /* Gets the state of the corner cubies. */ + private RubiksCornerState getCornerState() throws Exception { + return new RubiksCornerState( + // corner 1 + cube[0][0][0].toString() + + cube[1][0][0].toString() + + cube[5][2][0].toString() + + // corner 2 + cube[0][0][2].toString() + + cube[3][0][2].toString() + + cube[5][2][2].toString() + + // corner 3 + cube[2][0][0].toString() + + cube[1][0][2].toString() + + cube[0][2][0].toString() + + // corner 4 + cube[2][0][2].toString() + + cube[3][0][0].toString() + + cube[0][2][2].toString() + + // corner 5 + cube[4][0][0].toString() + + cube[1][2][2].toString() + + cube[2][2][0].toString() + + // corner 6 + cube[4][0][2].toString() + + cube[3][2][0].toString() + + cube[2][2][2].toString() + + // corner 7 + cube[5][0][0].toString() + + cube[1][2][0].toString() + + cube[4][2][0].toString() + + // corner 8 + cube[5][0][2].toString() + + cube[3][2][2].toString() + + cube[4][2][2].toString()); + } + + /* Gets the state of the first half of the edge cubies. */ + private RubiksHalfEdgeState getHalfEdgeState() throws Exception { + return new RubiksHalfEdgeState( + // edge 1 + cube[0][1][0].toString() + + cube[1][0][1].toString() + + // edge 2 + cube[0][0][1].toString() + + cube[5][2][1].toString() + + // edge 3 + cube[0][1][2].toString() + + cube[3][0][1].toString() + + // edge 4 + cube[0][2][1].toString() + + cube[2][0][1].toString() + + // edge 5 + cube[2][1][0].toString() + + cube[1][1][2].toString() + + // edge 6 + cube[2][1][2].toString() + + cube[3][1][0].toString()); + } + + /* Gets the state of the second half of the edge cubies. */ + private RubiksHalf2EdgeState getHalf2EdgeState() throws Exception { + return new RubiksHalf2EdgeState( + // edge 7 + cube[2][2][1].toString() + + cube[4][0][1].toString() + + // edge 8 + cube[4][1][0].toString() + + cube[1][2][1].toString() + + // edge 9 + cube[4][1][2].toString() + + cube[3][2][1].toString() + + // edge 10 + cube[4][2][1].toString() + + cube[5][0][1].toString() + + // edge 11 + cube[5][1][0].toString() + + cube[1][1][0].toString() + + // edge 12 + cube[5][1][2].toString() + + cube[3][1][2].toString()); } /** @@ -170,37 +310,27 @@ public class RubiksCube { */ public RubiksState[] getNeighborStates() { RubiksState[] states = new RubiksState[18]; //18 total states - for(int i=0; i<CUBE_SIZE-1; i++) { - //vertical - rotate(i,RubiksRotation.VERTICAL_CLOCKWISE); - states[0+i] = getState(); - rotate(i,RubiksRotation.VERTICAL_CLOCKWISE); - states[2+i] = getState(); - rotate(i,RubiksRotation.VERTICAL_CLOCKWISE); - states[4+i] = getState(); - - //original state - rotate(i,RubiksRotation.VERTICAL_CLOCKWISE); - - rotate(i,RubiksRotation.SIDE_VERTICAL_CLOCKWISE); - states[6+i] = getState(); - rotate(i,RubiksRotation.SIDE_VERTICAL_CLOCKWISE); - states[8+i] = getState(); - rotate(i,RubiksRotation.SIDE_VERTICAL_CLOCKWISE); - states[10+i] = getState(); - - //original state - rotate(i,RubiksRotation.SIDE_VERTICAL_CLOCKWISE); - - rotate(i,RubiksRotation.HORIZONTAL_CLOCKWISE); - states[12+i] = getState(); - rotate(i,RubiksRotation.HORIZONTAL_CLOCKWISE); - states[14+i] = getState(); - rotate(i,RubiksRotation.HORIZONTAL_CLOCKWISE); - states[16+i] = getState(); - - //original state - rotate(i,RubiksRotation.HORIZONTAL_CLOCKWISE); + RubiksState original = getState(); + + for(int i=0; i<3; i++) { // 3 is amount of rotations + rotate(i, RubiksColor.RED); + states[i*6] = getState(); + setState(original); + rotate(i, RubiksColor.GREEN); + states[i*6+1] = getState(); + setState(original); + rotate(i, RubiksColor.YELLOW); + states[i*6+2] = getState(); + setState(original); + rotate(i, RubiksColor.BLUE); + states[i*6+3] = getState(); + setState(original); + rotate(i, RubiksColor.ORANGE); + states[i*6+4] = getState(); + setState(original); + rotate(i, RubiksColor.WHITE); + states[i*6+5] = getState(); + setState(original); } return states; } @@ -264,45 +394,65 @@ public class RubiksCube { /** * Rotates a piece of the cube to change its state. * A maximum of 18 child states are available. - * @param piece Piece to rotate (0-1 if cube size is 3) - * @param rotation Type of rotation + * @param rotations Amount of 90 degrees clockwise rotation (1-3). + * @param face Type of rotation */ - public void rotate(int piece, RubiksRotation rotation) { + public void rotate(int rotations, RubiksColor face) { try { - checkValidPiece(piece); - piece = fixPieceValue(piece); - - switch (rotation) { - case VERTICAL_CLOCKWISE: - rotatePieceVerticalClockwise(piece); - break; - case VERTICAL_COUNTERCLOCKWISE: - rotatePieceVerticalCounterClockwise(piece); - break; - case VERTICAL_180: - rotatePieceVertical180(piece); - break; - case SIDE_VERTICAL_CLOCKWISE: - rotateSidePieceVerticalClockwise(piece); - break; - case SIDE_VERTICAL_COUNTERCLOCKWISE: - rotateSidePieceVerticalCounterClockwise(piece); - break; - case SIDE_VERTICAL_180: - rotateSidePieceVertical180(piece); - break; - case HORIZONTAL_CLOCKWISE: - rotatePieceHorizontalClockwise(piece); - break; - case HORIZONTAL_COUNTERCLOCKWISE: - rotatePieceHorizontalCounterClockwise(piece); - break; - case HORIZONTAL_180: - rotatePieceHorizontal180(piece); - break; - default: - break; - } + checkValidRotation(rotations); + + switch (face) { + case RED: + if(rotations==1) + rotatePieceHorizontalClockwise(0); + else if(rotations==2) + rotatePieceHorizontal180(0); + else if(rotations==3) + rotatePieceHorizontalCounterClockwise(0); + break; + case GREEN: + if(rotations==1) + rotatePieceVerticalClockwise(0); + else if(rotations==2) + rotatePieceVertical180(0); + else if(rotations==3) + rotatePieceVerticalCounterClockwise(0); + break; + case YELLOW: + if(rotations==1) + rotatePieceVerticalClockwise(1); + else if(rotations==2) + rotatePieceVertical180(1); + else if(rotations==3) + rotatePieceVerticalCounterClockwise(1); + break; + case BLUE: + if(rotations==1) + rotatePieceVerticalCounterClockwise(1); + else if(rotations==2) + rotatePieceVertical180(1); + else if(rotations==3) + rotatePieceVerticalClockwise(1); + break; + case ORANGE: + if(rotations==1) + rotatePieceHorizontalClockwise(1); + else if(rotations==2) + rotatePieceHorizontal180(1); + else if(rotations==3) + rotatePieceHorizontalCounterClockwise(1); + break; + case WHITE: + if(rotations==1) + rotatePieceVerticalClockwise(0); + else if(rotations==2) + rotatePieceVertical180(0); + else if(rotations==3) + rotatePieceVerticalCounterClockwise(0); + break; + default: + break; + } } catch (Exception e) { e.printStackTrace(); } @@ -641,22 +791,12 @@ public class RubiksCube { * Checks if piece is in range 0 to 1, only outer pieces can be rotated. * @param piece The piece number. */ - private void checkValidPiece(int piece) throws Exception { - if(piece > 1 || piece < 0) + private void checkValidRotation(int piece) throws Exception { + if(piece > 2 || piece < 0) throw new Exception(); } /* - * Since middle piece cannot be moved, the piece value has to be change - * when necessary so it can fit the cube 3-d array. - * @param piece The piece number. - * @return The correct piece value. - */ - private int fixPieceValue(int piece) { - if(piece==1) return 2; else return 0; - } - - /* * Since cube display is a flatten cube, some rotations require the * piece value to switch. * @param piece The piece to switch values. diff --git a/src/RubiksHalf2EdgeState.java b/src/RubiksHalf2EdgeState.java @@ -0,0 +1,69 @@ +import java.util.LinkedList; +import java.util.List; + +/** + * Holds part of the edge state of the rubik's cube with a + * heuristic that measures the amount of moves away from + * the goal state. + */ +public class RubiksHalf2EdgeState extends RubiksSubState { + private final String[][] COMBINATIONS = { + {"YO", "OY"}, + {"OG", "GO"}, + {"OB", "BO"}, + {"OW", "WO"}, + {"WG", "GW"}, + {"WB", "BW"}}; + + public RubiksHalf2EdgeState(String state, int heuristic) throws Exception { + super(state, heuristic); + if(!isValid(state)) + throw new Exception(); + } + + public RubiksHalf2EdgeState(String state) throws Exception { + super(state); + if(!isValid(state)) + throw new Exception(); + } + + @Override + protected boolean isValid(String str) { + if(str.length() == 12) { + List<Integer> edgesChecked = new LinkedList<Integer>(); + for(int i=0; i<str.length(); i+=2) { + String edge = + str.substring(i,i+2).toUpperCase(); + int check = isValidEdge(edge); + if(check == -1) return false; + else { + for(int edgesUsed : edgesChecked) { + if(edgesUsed == check) return false; + } + edgesChecked.add(check); + } + } + return true; + } + return false; + } + + @Override + //TODO + protected int hashState() { + return 0; + } + + /* + * Returns which edge out of all combinations is the string + * or -1 if it didn't match any. + */ + private int isValidEdge(String edge) { + for(int i=0; i<COMBINATIONS.length; i++) + for(int j=0; j<COMBINATIONS[i].length; j++) { + if(COMBINATIONS[i][j].equals(edge)) + return i; + } + return -1; + } +} diff --git a/src/RubiksHalfEdgeState.java b/src/RubiksHalfEdgeState.java @@ -0,0 +1,69 @@ +import java.util.LinkedList; +import java.util.List; + +/** + * Holds part of the edge state of the rubik's cube with a + * heuristic that measures the amount of moves away from + * the goal state. + */ +public class RubiksHalfEdgeState extends RubiksSubState { + private final String[][] COMBINATIONS = { + {"RG", "GR"}, + {"RW", "WR"}, + {"RB", "BR"}, + {"RY", "YR"}, + {"YG", "GY"}, + {"YB", "BY"}}; + + public RubiksHalfEdgeState(String state, int heuristic) throws Exception { + super(state, heuristic); + if(!isValid(state)) + throw new Exception(); + } + + public RubiksHalfEdgeState(String state) throws Exception { + super(state); + if(!isValid(state)) + throw new Exception(); + } + + @Override + protected boolean isValid(String str) { + if(str.length() == 12) { + List<Integer> edgesChecked = new LinkedList<Integer>(); + for(int i=0; i<str.length(); i+=2) { + String edge = + str.substring(i,i+2).toUpperCase(); + int check = isValidEdge(edge); + if(check == -1) return false; + else { + for(int edgesUsed : edgesChecked) { + if(edgesUsed == check) return false; + } + edgesChecked.add(check); + } + } + return true; + } + return false; + } + + @Override + //TODO + protected int hashState() { + return 0; + } + + /* + * Returns which edge out of all combinations is the string + * or -1 if it didn't match any. + */ + private int isValidEdge(String edge) { + for(int i=0; i<COMBINATIONS.length; i++) + for(int j=0; j<COMBINATIONS[i].length; j++) { + if(COMBINATIONS[i][j].equals(edge)) + return i; + } + return -1; + } +} diff --git a/src/RubiksPatternTable.java b/src/RubiksPatternTable.java @@ -11,22 +11,22 @@ public class RubiksPatternTable { * All attainable corner states of a rubik's cube. * There are 8! * 3^7 = 88,179,840 possible combination. */ - private int[] corners = - new int[88179840]; + private byte[] corners = + new byte[88179840]; /* * Half of all attainable edge states of a rubik's cube. * There are 12!/6! * 2^6 = 42,577,920 possible combinations. */ - private int[] halfEdges = - new int[42577920]; + private byte[] halfEdges = + new byte[42577920]; /* * Second half of all attainable edge states of a rubik's cube. * There are 12!/6! * 2^6 = 42,577,920 possible combinations. */ - private int[] half2Edges = - new int[42577920]; + private byte[] half2Edges = + new byte[42577920]; /* * All attainable corner states of a rubik's cube, @@ -76,7 +76,7 @@ public class RubiksPatternTable { } // TODO test - private void generateTables() { + /*private void generateTables() { // start at the goal state and add it to queue RubiksAttainableState rootAttainableState = new RubiksAttainableState( @@ -89,7 +89,6 @@ public class RubiksPatternTable { // traverse the queue and handle appropriately RubiksAttainableState current; - int count = 0; while(!travq.isEmpty()) { try { // poll the queue and convert it to state and cube @@ -113,7 +112,7 @@ public class RubiksPatternTable { new RubiksAttainableState( state.getCorners(), current.getHeuristic()); - //corners[count] = cornerstate; + //corners[HASH] = cornerstate.getheuristic; cornersTable.updateTable(cornerstate); System.out.println(cornerstate.getKey()+":"+cornerstate.getHeuristic()); @@ -133,12 +132,11 @@ public class RubiksPatternTable { half2Edges[count] = half2edgestate; half2EdgesTable.updateTable(half2edgestate);*/ - count++; - } catch (Exception e) { + /* } catch (Exception e) { e.printStackTrace(); } } - } + } */ @@ -166,7 +164,7 @@ public class RubiksPatternTable { } // TODO test - public void saveState(RubiksState state, short depth) { + /*public void saveState(RubiksState state, short depth) { //corners RubiksAttainableState attainable = new RubiksAttainableState(state.getCorners(), depth); @@ -184,7 +182,7 @@ public class RubiksPatternTable { new RubiksAttainableState(state.getHalf2Edges(), depth); //half2Edges[half2Edges.length-1] = attainable2; half2EdgesTable.updateTable(attainable2); - } + } */ /** * Retrieve pattern table of all corner states. diff --git a/src/RubiksRotation.java b/src/RubiksRotation.java @@ -1,31 +0,0 @@ -import java.util.*; - -/** - * Different possible rotation directions in Rubik's cube. - */ -public enum RubiksRotation { - VERTICAL_CLOCKWISE, - VERTICAL_COUNTERCLOCKWISE, - VERTICAL_180, - SIDE_VERTICAL_CLOCKWISE, - SIDE_VERTICAL_COUNTERCLOCKWISE, - SIDE_VERTICAL_180, - HORIZONTAL_CLOCKWISE, - HORIZONTAL_COUNTERCLOCKWISE, - HORIZONTAL_180; - - /** - * Picks a random rotation. - * @return The random rotation. - */ - public static RubiksRotation randomRotation() { - return VALUES.get(new Random().nextInt(SIZE)); - } - - /* Cached list of all possible values. */ - private static final List<RubiksRotation> VALUES = - Collections.unmodifiableList(Arrays.asList(values())); - - /* Cached size of all possible values. */ - private static final int SIZE = VALUES.size(); -} diff --git a/src/RubiksState.java b/src/RubiksState.java @@ -3,78 +3,56 @@ */ public class RubiksState { - /** - * If RubiksCube is 3x3, RubiksState total - * state size should be 48. - */ - public final byte SIZE = 48; - /* State of the corners. */ - private String corners; + private RubiksCornerState corners; /* State of half of the edges. */ - private String halfEdges; + private RubiksHalfEdgeState halfEdges; /* State of half of the other edges. */ - private String half2Edges; + private RubiksHalf2EdgeState half2Edges; /** * Initiates this empty state. */ - public RubiksState() { - corners = ""; - halfEdges = ""; - half2Edges = ""; - } - - /** - * Initiates this state with given attainable state. Assumes that - * the RubiksAttainableState's key the whole state of one cube so - * it should meet size requirement, if not, exception is thrown. - * @param attainableState The RubiksAttainableState - */ - public RubiksState(RubiksAttainableState attainableState) throws Exception { - if(attainableState.getKey().length() != SIZE) - throw new Exception(); - else { - String key = attainableState.getKey(); - if(!isValid(key)) throw new Exception(); - - this.corners = key.substring(0,23); - this.halfEdges = key.substring(24,35); - this.half2Edges = key.substring(36,47); - } + public RubiksState( + RubiksCornerState corners, + RubiksHalfEdgeState halfEdges, + RubiksHalf2EdgeState half2Edges) { + this.corners = corners; + this.halfEdges = halfEdges; + this.half2Edges = half2Edges; } /** * Set the state for this corners' state. * @param corners New state for corners. */ - public void setCorners(String corners) { - this.corners = corners; + public void setCorners(String corners) throws Exception { + this.corners = new RubiksCornerState(corners); } /** * Set the state for this half of the edges' state. * @param halfEdges New state for half of the edges. */ - public void setHalfEdges(String halfEdges) { - this.halfEdges = halfEdges; + public void setHalfEdges(String halfEdges) throws Exception { + this.halfEdges = new RubiksHalfEdgeState(halfEdges); } /** * Set the state for this second half of the edges' state. * @param half2Edges New state for second half of the edges. */ - public void setHalf2Edges(String half2Edges) { - this.half2Edges = half2Edges; + public void setHalf2Edges(String half2Edges) throws Exception { + this.half2Edges = new RubiksHalf2EdgeState(half2Edges); } /** * Retrieves the state of the corners. * @return State of the corners. */ - public String getCorners() { + public RubiksCornerState getCorners() { return corners; } @@ -82,7 +60,7 @@ public class RubiksState { * Retrieves the state of first half of the edges. * @return State of first half of the edges. */ - public String getHalfEdges() { + public RubiksHalfEdgeState getHalfEdges() { return halfEdges; } @@ -90,7 +68,7 @@ public class RubiksState { * Retrieves the state of second half of the edges. * @return State of second half of the edges. */ - public String getHalf2Edges() { + public RubiksHalf2EdgeState getHalf2Edges() { return half2Edges; } @@ -99,16 +77,9 @@ public class RubiksState { * @return The entire state of a cube. */ public String getState() { - return getCorners() + getHalfEdges() + getHalf2Edges(); - } - - /* Checks that a string is a valid Rubik's State. */ - private boolean isValid(String state) { - for(char ch : state.toCharArray()) { - RubiksColor color = - RubiksColor.find(Character.toString(ch)); - if(color.equals(RubiksColor.INVALID)) return false; - } - return true; + return + getCorners().toString() + + getHalfEdges().toString() + + getHalf2Edges().toString(); } } diff --git a/src/RubiksSubState.java b/src/RubiksSubState.java @@ -0,0 +1,64 @@ +/** + * Holds part of the state of the rubik's cube with a heuristic that + * measures the amount of moves away from the goal state. + */ +public abstract class RubiksSubState { + + /* The state is the key of this RubiksSubState. */ + protected String state; + + /* The heuristic of this RubiksSubState. */ + protected byte heuristic = -1; + + /** + * An RubiksSubState has a state as a key and a heuristic. + * @param state the state + * @param heuristic the heuristic (moves from the goal state). + */ + protected RubiksSubState(String state, short heuristic) { + this.state = state; + this.heuristic = (byte) heuristic; + } + + protected RubiksSubState(String state, int heuristic) { + this(state, (short) heuristic); + } + + protected RubiksSubState(String state) { + this.state = state; + } + + /** + * Retrieve state. + * @return The state of RubiksSubState. + */ + public String getState() { + return state; + } + + /** + * Retrieve heuristic. + * @return The heuristic of RubiksSubState. + */ + public short getHeuristic() { + return heuristic; + } + + @Override + public String toString() { + return state; + } + + /** + * Checks if the state is valid. + * @param str The string to check. + * @return If the state validates. + */ + protected abstract boolean isValid(String str); + + /** + * Hashes the state into a numerical value. + * @return The hashed state. + */ + protected abstract int hashState(); +} diff --git a/src/RubiksTest.java b/src/RubiksTest.java @@ -24,12 +24,55 @@ class RubiksTest //RubiksPatternTable patternTable = new RubiksPatternTable(); - int[] corners = - new int[88179840]; - int[] halfEdges = - new int[42577920]; - int[] half2Edges = - new int[42577920]; + byte[] corners = + new byte[88179840]; + byte[] halfEdges = + new byte[42577920]; + byte[] half2Edges = + new byte[42577920]; + + String[][] COMBINATIONS = { + {"RGW", "GWR", "WRG"}, + {"RBW", "BWR", "WRB"}, + {"YGR", "GRY", "RYG"}, + {"YBR", "BRY", "RYB"}, + {"OGY", "GYO", "YOG"}, + {"OBY", "BYO", "YOB"}, + {"WGO", "GOW", "OWG"}, + {"WBO", "BOW", "OWB"}}; + System.out.println(COMBINATIONS.length); + + String A="RGW"; + String B="RBW"; + String C="YGR"; + String D="YBR"; + String E="OGY"; + String F="OBY"; + String G="WGO"; + String H="WBO"; + + String I = "GR"; + String J = "WR"; + String K = "BR"; + String L = "YR"; + String M = "GY"; + String N = "BY"; + + String O = "YO"; + String P = "OG"; + String Q = "OB"; + String R = "OW"; + String S = "WG"; + String T = "WB"; + + try { + RubiksSubState cornerState = new RubiksCornerState(A+B+C+D+E+F+H+G,0); + RubiksSubState edgeState = new RubiksHalfEdgeState(I+J+K+L+N+M,0); + RubiksSubState edge2State = new RubiksHalf2EdgeState(O+P+Q+R+S+T,0); + } catch (Exception e) { + e.printStackTrace(); + } + // test if setState works /*RubiksCube randomCube = new RubiksCube(true);