rubikscube
college code for finding optimal rubiks cube solutions in java
git clone https://9o.is/git/rubikscube.git
commit e9f5d3c87ced5bfa904f92eac6fe0945235f0955 parent 9071cba2c867c1c95c3ec49f4af3acde2d4a73f2 Author: Jul <jul@9o.is> Date: Mon, 22 Oct 2012 15:31:31 -0400 Made progress to generateTables function but running into heap overflow. Diffstat:
| A | RubiksCube.eml | | | 6 | ++++++ |
| A | RubiksCube.userlibraries | | | 3 | +++ |
| D | src/AttainableRubiksState.java | | | 39 | --------------------------------------- |
| M | src/PatternTable.java | | | 6 | +++--- |
| A | src/RubiksAttainableState.java | | | 48 | ++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | src/RubiksColor.java | | | 6 | ++++-- |
| M | src/RubiksPatternTable.java | | | 112 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------------------- |
| M | src/RubiksState.java | | | 38 | +++++++++++++++++++++++++++++++++++++- |
| M | src/RubiksTest.java | | | 18 | ++++++++++++------ |
9 files changed, 193 insertions(+), 83 deletions(-)
diff --git a/RubiksCube.eml b/RubiksCube.eml @@ -0,0 +1,6 @@ +<?xml version="1.0" encoding="UTF-8"?> +<component inherit-compiler-output="true"> + <output-test url="file://$MODULE_DIR$/out/test/RubiksCube"/> + <exclude-output/> + <contentEntry url="file://$MODULE_DIR$"/> +</component> diff --git a/RubiksCube.userlibraries b/RubiksCube.userlibraries @@ -0,0 +1,3 @@ +<?xml version="1.0" encoding="UTF-8"?> +<eclipse-userlibraries /> + diff --git a/src/AttainableRubiksState.java b/src/AttainableRubiksState.java @@ -1,39 +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. - */ -public class AttainableRubiksState { - - /* The key is the state of this AttainableRubiksState. */ - private String key; - - /* The heuristic of this AttainableRubiksState. */ - private short heuristic; - - /** - * An AttainableRubiksState has a state as a key and a heuristic. - * @param key the state - * @param heuristic the heuristic (moves from the goal state). - */ - public AttainableRubiksState(String key, short heuristic) { - this.key = key; - this.heuristic = heuristic; - } - - /** - * Retrieve state. - * @return The key of AttainableRubiksState. - */ - public String getKey() { - return key; - } - - /** - * Retrieve heuristic. - * @return The heuristic of AttainableRubiksState. - */ - public short getHeuristic() { - return heuristic; - } -} diff --git a/src/PatternTable.java b/src/PatternTable.java @@ -18,11 +18,11 @@ public class PatternTable { } /** - * Updates the pattern table with a new AttainableRubiksState's + * Updates the pattern table with a new RubiksAttainableState's * key and value. - * @param attainable The AttainableRubiksState to store. + * @param attainable The RubiksAttainableState to store. */ - public void updateTable(AttainableRubiksState attainable) { + public void updateTable(RubiksAttainableState attainable) { try { BufferedWriter out = new BufferedWriter(new FileWriter(file,true)); diff --git a/src/RubiksAttainableState.java b/src/RubiksAttainableState.java @@ -0,0 +1,48 @@ +/** + * 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 @@ -7,7 +7,8 @@ public enum RubiksColor { BLUE ("B"), YELLOW ("Y"), ORANGE ("O"), - WHITE ("W"); + WHITE ("W"), + INVALID("~"); /* The color in string format. */ private final String string; @@ -28,7 +29,8 @@ public enum RubiksColor { else if(string.equals("B")) return BLUE; else if(string.equals("Y")) return YELLOW; else if(string.equals("O")) return ORANGE; - else return WHITE; + else if(string.equals("W")) return WHITE; + else return INVALID; } public String toString() { 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 AttainableRubiksState[] corners = - new AttainableRubiksState[88179840]; + private int[] corners = + new int[88179840]; /* * Half of all attainable edge states of a rubik's cube. * There are 12!/6! * 2^6 = 42,577,920 possible combinations. */ - private AttainableRubiksState[] halfEdges = - new AttainableRubiksState[42577920]; + private int[] halfEdges = + new int[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 AttainableRubiksState[] half2Edges = - new AttainableRubiksState[42577920]; + private int[] half2Edges = + new int[42577920]; /* * All attainable corner states of a rubik's cube, @@ -75,34 +75,82 @@ public class RubiksPatternTable { this.half2EdgesTable.clearTable(); } - //TODO test - public void generateTables() { - Queue<RubiksState> travq = new LinkedList<RubiksState>(); - travq.add(new RubiksCube().getState()); - short depth = 1; - RubiksState current; + // TODO test + private void generateTables() { + // start at the goal state and add it to queue + RubiksAttainableState rootAttainableState = + new RubiksAttainableState( + new RubiksCube().getState().getState(),1); + + Queue<RubiksAttainableState> travq = + new LinkedList<RubiksAttainableState>(); + + travq.add(rootAttainableState); + + // traverse the queue and handle appropriately + RubiksAttainableState current; + int count = 0; while(!travq.isEmpty()) { - current = travq.poll(); - saveState(current, depth); - //TODO how to keep track of the depth - RubiksCube cube = new RubiksCube(current); - RubiksState[] childStates = cube.getNeighborStates(); - for(RubiksState state : childStates) { - queueChildState(travq, state); + 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); + + // 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(), + current.getHeuristic()+1)); + } + + // save corner state to array and table + RubiksAttainableState cornerstate = + new RubiksAttainableState( + state.getCorners(), + current.getHeuristic()); + //corners[count] = cornerstate; + cornersTable.updateTable(cornerstate); + System.out.println(cornerstate.getKey()+":"+cornerstate.getHeuristic()); + + // save first set of edges to array and table + /*RubiksAttainableState halfedgestate = + new RubiksAttainableState( + state.getHalfEdges(), + current.getHeuristic()); + halfEdges[count] = halfedgestate; + halfEdgesTable.updateTable(halfedgestate); + + // save second set of edges to array and table + RubiksAttainableState half2edgestate = + new RubiksAttainableState( + state.getHalf2Edges(), + current.getHeuristic()); + half2Edges[count] = half2edgestate; + half2EdgesTable.updateTable(half2edgestate);*/ + + count++; + } catch (Exception e) { + e.printStackTrace(); } } - } - //TODO test + + + //TODO test // queue a state if its unique or it's not saved already - private void queueChildState(Queue<RubiksState> travq, RubiksState state) { + /*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. @@ -120,21 +168,21 @@ public class RubiksPatternTable { // TODO test public void saveState(RubiksState state, short depth) { //corners - AttainableRubiksState attainable = - new AttainableRubiksState(state.getCorners(), depth); - corners[corners.length-1] = attainable; + RubiksAttainableState attainable = + new RubiksAttainableState(state.getCorners(), depth); + //corners[corners.length-1] = attainable; cornersTable.updateTable(attainable); //half edges - AttainableRubiksState attainable1 = - new AttainableRubiksState(state.getHalfEdges(), depth); - halfEdges[halfEdges.length-1] = attainable1; + RubiksAttainableState attainable1 = + new RubiksAttainableState(state.getHalfEdges(), depth); + //halfEdges[halfEdges.length-1] = attainable1; halfEdgesTable.updateTable(attainable1); //second half edges - AttainableRubiksState attainable2 = - new AttainableRubiksState(state.getHalf2Edges(), depth); - half2Edges[half2Edges.length-1] = attainable2; + RubiksAttainableState attainable2 = + new RubiksAttainableState(state.getHalf2Edges(), depth); + //half2Edges[half2Edges.length-1] = attainable2; half2EdgesTable.updateTable(attainable2); } diff --git a/src/RubiksState.java b/src/RubiksState.java @@ -2,6 +2,13 @@ * A Rubik's Cube State. */ 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; @@ -12,7 +19,7 @@ public class RubiksState { private String half2Edges; /** - * Initiates this state. + * Initiates this empty state. */ public RubiksState() { corners = ""; @@ -21,6 +28,25 @@ public class RubiksState { } /** + * 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); + } + } + + /** * Set the state for this corners' state. * @param corners New state for corners. */ @@ -75,4 +101,14 @@ public class RubiksState { 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; + } } diff --git a/src/RubiksTest.java b/src/RubiksTest.java @@ -1,6 +1,3 @@ -import java.security.MessageDigest; -import java.security.NoSuchAlgorithmException; - class RubiksTest { public static void main(String[] args) @@ -21,9 +18,18 @@ class RubiksTest //System.out.println(cornersTable.valueOf("WYWWRORBRBYY")); //cornersTable.clearTable(); - RubiksCube cube = new RubiksCube(true); - cube.rotate(0, RubiksRotation.VERTICAL_CLOCKWISE); - cube.printState(); + //RubiksCube cube = new RubiksCube(true); + //cube.rotate(0, RubiksRotation.VERTICAL_CLOCKWISE); + //cube.printState(); + + //RubiksPatternTable patternTable = new RubiksPatternTable(); + + int[] corners = + new int[88179840]; + int[] halfEdges = + new int[42577920]; + int[] half2Edges = + new int[42577920]; // test if setState works /*RubiksCube randomCube = new RubiksCube(true);