rubikscube
college code for finding optimal rubiks cube solutions in java
git clone https://9o.is/git/rubikscube.git
commit 6d1cdce53a4ab201f63d56608b3c0fcf6d540a66 parent a08bdf9ae30e30217242f31d4405c3d9959a81aa Author: Jul <jul@9o.is> Date: Thu, 25 Oct 2012 17:05:33 -0400 Able to generate heuristic pattern table. Will test during the night. Diffstat:
| M | src/PatternTable.java | | | 6 | +++--- |
| M | src/RubiksCornerState.java | | | 55 | ++++++++++++++++++++++++++++++++++++++++++++++--------- |
| M | src/RubiksCube.java | | | 218 | ++++++++++++++++++++++++++++++++++++++++--------------------------------------- |
| M | src/RubiksHalf2EdgeState.java | | | 4 | ++-- |
| M | src/RubiksHalfEdgeState.java | | | 55 | +++++++++++++++++++++++++++++++++++++++++++++++++------ |
| M | src/RubiksPatternTable.java | | | 80 | +++++++++++++++++++++++++++++++++++++++---------------------------------------- |
| M | src/RubiksState.java | | | 104 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------- |
| M | src/RubiksSubState.java | | | 12 | +++++++++++- |
| M | src/RubiksTest.java | | | 19 | ++++++++++++++----- |
9 files changed, 369 insertions(+), 184 deletions(-)
diff --git a/src/PatternTable.java b/src/PatternTable.java @@ -22,12 +22,12 @@ public class PatternTable { * key and value. * @param state The RubiksSubState to store. */ - public void updateTable(RubiksSubState state) { + public void updateTable(int state, byte heuristic) { try { BufferedWriter out = new BufferedWriter(new FileWriter(file,true)); - out.write(state.getState()+":"+ - Short.toString(state.getHeuristic())+"\n"); + out.write(state+":"+ + Short.toString(heuristic)+"\n"); out.close(); } catch (IOException e) { System.err.println("Error: " + e.getMessage()); diff --git a/src/RubiksCornerState.java b/src/RubiksCornerState.java @@ -9,14 +9,14 @@ import java.util.List; 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"}}; + {"WRG", "RGW", "GWR"}, + {"WBR", "BRW", "RWB"}, + {"RYG", "YGR", "GRY"}, + {"RBY", "BYR", "YRB"}, + {"YOG", "OGY", "GYO"}, + {"YBO", "BOY", "OYB"}, + {"OWG", "WGO", "GOW"}, + {"OBW", "BWO", "WOB"}}; public RubiksCornerState(String state, int heuristic) throws Exception { super(state, heuristic); @@ -54,7 +54,44 @@ public class RubiksCornerState extends RubiksSubState { @Override //TODO protected int hashState() { - return 0; + int[] c = new int[8]; + int[] o = new int[7]; + int[] arraycounter = {0,1,2,3,4,5,6,7}; + + for(int i=0; i<8;i++) { + String str = state.substring(i*3,(i*3)+3); + for(int j=0; j<8;j++) { + for(int k=0; k< COMBINATIONS[j].length; k++) { + if(str.compareTo(COMBINATIONS[j][k])==0) { + for(int m=j+1; m<arraycounter.length; m++) { + arraycounter[m] = arraycounter[m] - 1; + } + c[j] = arraycounter[j]; + if(j < 7) o[j] = k; + } + } + } + } + + int f1 = + fac(7)*c[7]+ + fac(6)*c[6]+ + fac(5)*c[5]+ + fac(4)*c[4]+ + fac(3)*c[3]+ + fac(2)*c[2]+ + fac(1)*c[1]+ + fac(0)*c[0]; + int f2 = + (int)(o[6]*Math.pow(3,6) + + o[5]*Math.pow(3,5) + + o[4]*Math.pow(3,4) + + o[3]*Math.pow(3,3) + + o[2]*Math.pow(3,2) + + o[1]*Math.pow(3,1) + + o[0]*Math.pow(3,0)); + + return 2187*f1 + f2; } /* diff --git a/src/RubiksCube.java b/src/RubiksCube.java @@ -81,57 +81,57 @@ public class RubiksCube { public void setState(RubiksState state) { 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)); + cube[5][2][0] = RubiksColor.find(corners.substring(0,1)); + cube[0][0][0] = RubiksColor.find(corners.substring(1,2)); + cube[1][0][0] = RubiksColor.find(corners.substring(2,3)); // corner 2 - cube[0][0][2] = RubiksColor.find(corners.substring(3,4)); + cube[5][2][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)); + cube[0][0][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)); + cube[0][2][0] = RubiksColor.find(corners.substring(6,7)); + cube[2][0][0] = RubiksColor.find(corners.substring(7,8)); + cube[1][0][2] = RubiksColor.find(corners.substring(8,9)); // corner 4 - cube[2][0][2] = RubiksColor.find(corners.substring(9,10)); + cube[0][2][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)); + cube[2][0][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)); + cube[2][2][0] = RubiksColor.find(corners.substring(12,13)); + cube[4][0][0] = RubiksColor.find(corners.substring(13,14)); + cube[1][2][2] = RubiksColor.find(corners.substring(14,15)); // corner 6 - cube[4][0][2] = RubiksColor.find(corners.substring(15,16)); + cube[2][2][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)); + cube[4][0][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)); + cube[4][2][0] = RubiksColor.find(corners.substring(18,19)); + cube[5][0][0] = RubiksColor.find(corners.substring(19,20)); + cube[1][2][0] = RubiksColor.find(corners.substring(20,21)); // corner 8 - cube[5][0][2] = RubiksColor.find(corners.substring(21,22)); + cube[4][2][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)); + cube[5][0][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)); + cube[1][0][1] = RubiksColor.find(halfEdges.substring(0,1)); + cube[0][1][0] = 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)); + cube[5][2][1] = RubiksColor.find(halfEdges.substring(2,3)); + cube[0][0][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)); + cube[2][0][1] = RubiksColor.find(halfEdges.substring(6,7)); + cube[0][2][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)); + cube[3][1][0] = RubiksColor.find(halfEdges.substring(10,11)); + cube[2][1][2] = RubiksColor.find(halfEdges.substring(11,12)); String half2Edges = state.getHalf2Edges().toString(); // edge 7 @@ -141,14 +141,14 @@ public class RubiksCube { 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)); + cube[3][2][1] = RubiksColor.find(half2Edges.substring(4,5)); + cube[4][1][2] = 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)); + cube[1][1][0] = RubiksColor.find(half2Edges.substring(8,9)); + cube[5][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)); @@ -196,7 +196,7 @@ public class RubiksCube { */ public void initRandomState() { for(int i=0; i<100; i++) { - rotate(new Random().nextInt(2), + rotate(new Random().nextInt(2)+1, RubiksColor.randomColor()); } } @@ -215,93 +215,95 @@ public class RubiksCube { } 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. + // but the 3d array made the cube almost impossible. e.printStackTrace(); return null; } } /* Gets the state of the corner cubies. */ - private RubiksCornerState getCornerState() throws Exception { - return new RubiksCornerState( + public String getCornerState() { + return // corner 1 - cube[0][0][0].toString() + - cube[1][0][0].toString() + - cube[5][2][0].toString() + + cube[5][2][0].toString() + //w + cube[0][0][0].toString() + //r + cube[1][0][0].toString() + //g + // corner 2 - cube[0][0][2].toString() + - cube[3][0][2].toString() + - cube[5][2][2].toString() + + cube[5][2][2].toString() + //w + cube[3][0][2].toString() + //b + cube[0][0][2].toString() + //r // corner 3 - cube[2][0][0].toString() + - cube[1][0][2].toString() + - cube[0][2][0].toString() + + cube[0][2][0].toString() + //r + cube[2][0][0].toString() + //y + cube[1][0][2].toString() + //g // corner 4 - cube[2][0][2].toString() + - cube[3][0][0].toString() + - cube[0][2][2].toString() + + cube[0][2][2].toString() + //r + cube[3][0][0].toString() + //b + cube[2][0][2].toString() + //y // corner 5 - cube[4][0][0].toString() + - cube[1][2][2].toString() + - cube[2][2][0].toString() + + cube[2][2][0].toString() + //y + cube[4][0][0].toString() + //o + cube[1][2][2].toString() + //g // corner 6 - cube[4][0][2].toString() + - cube[3][2][0].toString() + - cube[2][2][2].toString() + + cube[2][2][2].toString() + //y + cube[3][2][0].toString() + //b + cube[4][0][2].toString() + //o // corner 7 - cube[5][0][0].toString() + - cube[1][2][0].toString() + - cube[4][2][0].toString() + + cube[4][2][0].toString() + //o + cube[5][0][0].toString() + //w + cube[1][2][0].toString() + //g // corner 8 - cube[5][0][2].toString() + - cube[3][2][2].toString() + - cube[4][2][2].toString()); + cube[4][2][2].toString() + //o + cube[3][2][2].toString() + //b + cube[5][0][2].toString(); //w + } /* Gets the state of the first half of the edge cubies. */ - private RubiksHalfEdgeState getHalfEdgeState() throws Exception { - return new RubiksHalfEdgeState( + public String getHalfEdgeState() { + return // edge 1 - cube[0][1][0].toString() + - cube[1][0][1].toString() + + cube[1][0][1].toString() + //g + cube[0][1][0].toString() + //r // edge 2 - cube[0][0][1].toString() + - cube[5][2][1].toString() + + cube[5][2][1].toString() + //w + cube[0][0][1].toString() + //r // edge 3 - cube[0][1][2].toString() + - cube[3][0][1].toString() + + cube[0][1][2].toString() + //r + cube[3][0][1].toString() + //b // edge 4 - cube[0][2][1].toString() + - cube[2][0][1].toString() + + cube[0][2][1].toString() + //r + cube[2][0][1].toString() + //y // edge 5 - cube[2][1][0].toString() + - cube[1][1][2].toString() + + cube[2][1][0].toString() + //y + cube[1][1][2].toString() + //g // edge 6 - cube[2][1][2].toString() + - cube[3][1][0].toString()); + cube[3][1][0].toString() + //b + cube[2][1][2].toString(); //y } /* Gets the state of the second half of the edge cubies. */ - private RubiksHalf2EdgeState getHalf2EdgeState() throws Exception { - return new RubiksHalf2EdgeState( + public String getHalf2EdgeState() { + return // edge 7 - cube[2][2][1].toString() + - cube[4][0][1].toString() + + cube[2][2][1].toString() + //y + cube[4][0][1].toString() + //o // edge 8 - cube[4][1][0].toString() + - cube[1][2][1].toString() + + cube[4][1][0].toString() + //o + cube[1][2][1].toString() + //g // edge 9 - cube[4][1][2].toString() + - cube[3][2][1].toString() + + cube[3][2][1].toString() + //b + cube[4][1][2].toString() + //o // edge 10 - cube[4][2][1].toString() + - cube[5][0][1].toString() + + cube[4][2][1].toString() + //o + cube[5][0][1].toString() + //w // edge 11 - cube[5][1][0].toString() + - cube[1][1][0].toString() + + cube[1][1][0].toString() + //g + cube[5][1][0].toString() + //w // edge 12 - cube[5][1][2].toString() + - cube[3][1][2].toString()); + cube[5][1][2].toString() + //w + cube[3][1][2].toString(); //b } /** @@ -313,22 +315,22 @@ public class RubiksCube { RubiksState original = getState(); for(int i=0; i<3; i++) { // 3 is amount of rotations - rotate(i, RubiksColor.RED); + rotate(i+1, RubiksColor.RED); states[i*6] = getState(); setState(original); - rotate(i, RubiksColor.GREEN); + rotate(i+1, RubiksColor.GREEN); states[i*6+1] = getState(); setState(original); - rotate(i, RubiksColor.YELLOW); + rotate(i+1, RubiksColor.YELLOW); states[i*6+2] = getState(); setState(original); - rotate(i, RubiksColor.BLUE); + rotate(i+1, RubiksColor.BLUE); states[i*6+3] = getState(); setState(original); - rotate(i, RubiksColor.ORANGE); + rotate(i+1, RubiksColor.ORANGE); states[i*6+4] = getState(); setState(original); - rotate(i, RubiksColor.WHITE); + rotate(i+1, RubiksColor.WHITE); states[i*6+5] = getState(); setState(original); } @@ -420,35 +422,35 @@ public class RubiksCube { break; case YELLOW: if(rotations==1) - rotatePieceVerticalClockwise(1); + rotateSidePieceVerticalClockwise(2); else if(rotations==2) - rotatePieceVertical180(1); + rotateSidePieceVertical180(2); else if(rotations==3) - rotatePieceVerticalCounterClockwise(1); + rotateSidePieceVerticalCounterClockwise(2); break; case BLUE: if(rotations==1) - rotatePieceVerticalCounterClockwise(1); + rotatePieceVerticalCounterClockwise(2); else if(rotations==2) - rotatePieceVertical180(1); + rotatePieceVertical180(2); else if(rotations==3) - rotatePieceVerticalClockwise(1); + rotatePieceVerticalClockwise(2); break; case ORANGE: if(rotations==1) - rotatePieceHorizontalClockwise(1); + rotatePieceHorizontalClockwise(2); else if(rotations==2) - rotatePieceHorizontal180(1); + rotatePieceHorizontal180(2); else if(rotations==3) - rotatePieceHorizontalCounterClockwise(1); + rotatePieceHorizontalCounterClockwise(2); break; case WHITE: if(rotations==1) - rotatePieceVerticalClockwise(0); + rotateSidePieceVerticalClockwise(0); else if(rotations==2) - rotatePieceVertical180(0); + rotateSidePieceVertical180(0); else if(rotations==3) - rotatePieceVerticalCounterClockwise(0); + rotateSidePieceVerticalCounterClockwise(0); break; default: break; @@ -791,8 +793,8 @@ 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 checkValidRotation(int piece) throws Exception { - if(piece > 2 || piece < 0) + private void checkValidRotation(int rotations) throws Exception { + if(rotations > 3 || rotations < 1) throw new Exception(); } diff --git a/src/RubiksHalf2EdgeState.java b/src/RubiksHalf2EdgeState.java @@ -10,9 +10,9 @@ public class RubiksHalf2EdgeState extends RubiksSubState { private final String[][] COMBINATIONS = { {"YO", "OY"}, {"OG", "GO"}, - {"OB", "BO"}, + {"BO", "OB"}, {"OW", "WO"}, - {"WG", "GW"}, + {"GW", "WG"}, {"WB", "BW"}}; public RubiksHalf2EdgeState(String state, int heuristic) throws Exception { diff --git a/src/RubiksHalfEdgeState.java b/src/RubiksHalfEdgeState.java @@ -7,13 +7,19 @@ import java.util.List; * the goal state. */ public class RubiksHalfEdgeState extends RubiksSubState { - private final String[][] COMBINATIONS = { - {"RG", "GR"}, - {"RW", "WR"}, + public final static String[][] COMBINATIONS = { + {"GR", "RG"}, + {"WR", "RW"}, {"RB", "BR"}, {"RY", "YR"}, {"YG", "GY"}, - {"YB", "BY"}}; + {"BY", "YB"}, + {"YO", "OY"}, + {"OG", "GO"}, + {"BO", "OB"}, + {"OW", "WO"}, + {"GW", "WG"}, + {"WB", "BW"}}; public RubiksHalfEdgeState(String state, int heuristic) throws Exception { super(state, heuristic); @@ -51,14 +57,51 @@ public class RubiksHalfEdgeState extends RubiksSubState { @Override //TODO protected int hashState() { - return 0; + int counter = 0; + int[] c = new int[6]; + int[] o = new int[6]; + int[] arraycounter = {0,1,2,3,4,5,6,7,8,9,10,11}; + + for(int i=0; i<6;i++) { + String str = state.substring(i*2,(i*2)+2); + for(int j=0; j<12;j++) { + for(int k=0; k< COMBINATIONS[j].length; k++) { + if(str.compareTo(COMBINATIONS[j][k])==0) { + for(int m=j+1; m<arraycounter.length; m++) { + arraycounter[m] = arraycounter[m] - 1; + } + c[counter] = arraycounter[j]; + o[counter] = k; + counter++; + } + } + } + } + + int f1 = + (fac(11)*c[0]+ + fac(10)*c[1]+ + fac(9)*c[2]+ + fac(8)*c[3]+ + fac(7)*c[4]+ + fac(6)*c[5])/fac(6); + + int f2 = + (int)(o[5]*Math.pow(2,5) + + o[4]*Math.pow(2,4) + + o[3]*Math.pow(2,3) + + o[2]*Math.pow(2,2) + + o[1]*Math.pow(2,1) + + o[0]*Math.pow(2,0)); + + return 64*f1 + f2; } /* * Returns which edge out of all combinations is the string * or -1 if it didn't match any. */ - private int isValidEdge(String edge) { + public static 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)) diff --git a/src/RubiksPatternTable.java b/src/RubiksPatternTable.java @@ -76,79 +76,77 @@ public class RubiksPatternTable { } // TODO test - /*private void generateTables() { + public void generateTables() throws Exception { // start at the goal state and add it to queue - RubiksAttainableState rootAttainableState = - new RubiksAttainableState( - new RubiksCube().getState().getState(),1); + RubiksState rootAttainableState = + new RubiksState(new RubiksCube(),1); - Queue<RubiksAttainableState> travq = - new LinkedList<RubiksAttainableState>(); + Queue<RubiksState> travq = + new LinkedList<RubiksState>(); travq.add(rootAttainableState); // traverse the queue and handle appropriately - RubiksAttainableState current; + RubiksState current; while(!travq.isEmpty()) { try { // poll the queue and convert it to state and cube // for easier manipulation current = travq.poll(); - RubiksState state = new RubiksState(current); - RubiksCube cube = new RubiksCube(state); + RubiksCube cube = new RubiksCube(current); // iterate the current cube's neighbors; add to queue // if the state hasn't been added yet for(RubiksState neighbor : cube.getNeighborStates()) { // TODO assure neighbor is unique travq.add( - new RubiksAttainableState( - neighbor.getState(), + new RubiksState( + neighbor, current.getHeuristic()+1)); } // save corner state to array and table - RubiksAttainableState cornerstate = - new RubiksAttainableState( - state.getCorners(), + RubiksSubState cornerstate = + new RubiksCornerState( + current.getCorners().toString(), current.getHeuristic()); - //corners[HASH] = cornerstate.getheuristic; - cornersTable.updateTable(cornerstate); - System.out.println(cornerstate.getKey()+":"+cornerstate.getHeuristic()); + int hash = cornerstate.hashState(); + if(corners[hash] == 0) { + corners[hash] = cornerstate.getHeuristic(); + cornersTable.updateTable(hash, cornerstate.getHeuristic()); + } // save first set of edges to array and table - /*RubiksAttainableState halfedgestate = - new RubiksAttainableState( - state.getHalfEdges(), + RubiksSubState halfedgestate = + new RubiksHalfEdgeState( + current.getHalfEdges().toString(), current.getHeuristic()); - halfEdges[count] = halfedgestate; - halfEdgesTable.updateTable(halfedgestate); + hash = halfedgestate.hashState(); + if(halfEdges[hash] == 0) { + halfEdges[hash] = halfedgestate.getHeuristic(); + halfEdgesTable.updateTable(hash, halfedgestate.getHeuristic()); + } // save second set of edges to array and table - RubiksAttainableState half2edgestate = - new RubiksAttainableState( - state.getHalf2Edges(), + RubiksSubState half2edgestate = + new RubiksHalfEdgeState( + current.getHalf2Edges().toString(), current.getHeuristic()); - half2Edges[count] = half2edgestate; - half2EdgesTable.updateTable(half2edgestate);*/ + hash = half2edgestate.hashState(); + if(half2Edges[hash] == 0) { + half2Edges[hash] = half2edgestate.getHeuristic(); + half2EdgesTable.updateTable(hash, half2edgestate.getHeuristic()); + } - /* } catch (Exception e) { + System.out.println( + "Added State: "+current.getState() + + " -> Heuristic: "+current.getHeuristic()); + + } catch (Exception e) { e.printStackTrace(); } } - } */ - - - - //TODO test - // queue a state if its unique or it's not saved already - /*private void queueChildState(Queue<RubiksState> travq, RubiksState state) { - for(int i=0; i<corners.length; i++) { - if(state.getState().equals(corners[i].getKey())) - return; - } - travq.add(state); - } */ + } /** * Uses IDA* search to find optimal path. diff --git a/src/RubiksState.java b/src/RubiksState.java @@ -1,3 +1,6 @@ +import java.util.LinkedList; +import java.util.List; + /** * A Rubik's Cube State. */ @@ -10,18 +13,64 @@ public class RubiksState { private RubiksHalfEdgeState halfEdges; /* State of half of the other edges. */ - private RubiksHalf2EdgeState half2Edges; + private RubiksHalfEdgeState half2Edges; + + /* Heuristic of the state. */ + private byte heuristic = -1; /** * Initiates this empty state. */ public RubiksState( - RubiksCornerState corners, - RubiksHalfEdgeState halfEdges, - RubiksHalf2EdgeState half2Edges) { - this.corners = corners; - this.halfEdges = halfEdges; - this.half2Edges = half2Edges; + String corners, + String halfEdges, + String half2Edges) throws Exception { + if(!isEdgeValid(halfEdges+half2Edges)) + throw new Exception(); + + this.corners = new RubiksCornerState(corners); + this.halfEdges = new RubiksHalfEdgeState(halfEdges); + this.half2Edges = new RubiksHalfEdgeState(half2Edges); + } + + public RubiksState( + String corners, + String halfEdges, + String half2Edges, + int heuristic) throws Exception { + this(corners,halfEdges,half2Edges); + this.heuristic = (byte) heuristic; + } + + public RubiksState(RubiksCube cube) throws Exception { + if(!isEdgeValid( + cube.getHalfEdgeState()+cube.getHalf2EdgeState())) + throw new Exception(); + + this.corners = new RubiksCornerState(cube.getCornerState()); + this.halfEdges = new RubiksHalfEdgeState(cube.getHalfEdgeState()); + this.half2Edges = new RubiksHalfEdgeState(cube.getHalf2EdgeState()); + } + + public RubiksState(RubiksCube cube, int heuristic) throws Exception { + this(cube); + this.heuristic = (byte) heuristic; + } + + public RubiksState(RubiksState state) throws Exception { + if(!isEdgeValid( + state.getHalfEdges().toString() + + state.getHalf2Edges().toString())) + throw new Exception(); + + this.corners = state.getCorners(); + this.halfEdges = state.getHalfEdges(); + this.half2Edges = state.getHalf2Edges(); + } + + public RubiksState(RubiksState state, int heuristic) throws Exception { + this(state); + this.heuristic = (byte) heuristic; } /** @@ -45,7 +94,7 @@ public class RubiksState { * @param half2Edges New state for second half of the edges. */ public void setHalf2Edges(String half2Edges) throws Exception { - this.half2Edges = new RubiksHalf2EdgeState(half2Edges); + this.half2Edges = new RubiksHalfEdgeState(half2Edges); } /** @@ -68,11 +117,19 @@ public class RubiksState { * Retrieves the state of second half of the edges. * @return State of second half of the edges. */ - public RubiksHalf2EdgeState getHalf2Edges() { + public RubiksHalfEdgeState getHalf2Edges() { return half2Edges; } /** + * Heuristic. + * @return heuristic + */ + public byte getHeuristic() { + return heuristic; + } + + /** * All part-states combined to make a final Rubik's cube state.. * @return The entire state of a cube. */ @@ -82,4 +139,33 @@ public class RubiksState { getHalfEdges().toString() + getHalf2Edges().toString(); } + + /** + * Since RubiksState combines two halves of one rubik's edge + * state, it must make sure they both match to be in one cube. + * @param str The string sequence of all edge state. + * @return True if it passes the test. + */ + protected boolean isEdgeValid(String str) { + if(str.length() == 24) { + 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 = RubiksHalfEdgeState.isValidEdge(edge); + if(check == -1) return false; + else { + int count=0; //can only be counted up to two + for(int j=0; j<edgesChecked.size(); j++) { + int edgeUsed = edgesChecked.get(j); + if(edgeUsed == check) + if(++count > 1) return false; + } + edgesChecked.add(check); + } + } + return true; + } + return false; + } } diff --git a/src/RubiksSubState.java b/src/RubiksSubState.java @@ -40,7 +40,7 @@ public abstract class RubiksSubState { * Retrieve heuristic. * @return The heuristic of RubiksSubState. */ - public short getHeuristic() { + public byte getHeuristic() { return heuristic; } @@ -50,6 +50,16 @@ public abstract class RubiksSubState { } /** + * Simply a factorial function. + * @param n Number + * @return Factorial of n (n!) + */ + protected static int fac(int n) { + if(n<=1) return 1; + return n * fac(n-1); + } + + /** * Checks if the state is valid. * @param str The string to check. * @return If the state validates. diff --git a/src/RubiksTest.java b/src/RubiksTest.java @@ -19,12 +19,12 @@ class RubiksTest //cornersTable.clearTable(); //RubiksCube cube = new RubiksCube(true); - //cube.rotate(0, RubiksRotation.VERTICAL_CLOCKWISE); + //cube.rotate(3, RubiksColor.WHITE); //cube.printState(); //RubiksPatternTable patternTable = new RubiksPatternTable(); - byte[] corners = + /*byte[] corners = new byte[88179840]; byte[] halfEdges = new byte[42577920]; @@ -71,7 +71,7 @@ class RubiksTest RubiksSubState edge2State = new RubiksHalf2EdgeState(O+P+Q+R+S+T,0); } catch (Exception e) { e.printStackTrace(); - } + } */ // test if setState works @@ -117,9 +117,18 @@ class RubiksTest } System.out.println(state.getState()); } - System.out.println("Done");*/ - + System.out.println("Done"); */ + //RubiksState s = cube.getState(); + //System.out.println(s.getHalfEdges()); + //cube.printState(); + RubiksPatternTable patternTable = new RubiksPatternTable(); + try { + patternTable.generateTables(); + } catch (Exception e) { + System.err.println(e.getMessage()); + e.printStackTrace(); + } } } \ No newline at end of file