rubikscube
college code for finding optimal rubiks cube solutions in java
git clone https://9o.is/git/rubikscube.git
commit 946ebca372979ff668d0d3a0c75709dd658cd5d8 parent be4b84b5626603206fe46410e4356aaf7833acfc Author: Jul <jul@9o.is> Date: Fri, 26 Oct 2012 23:02:08 -0400 Submitted project. Diffstat:
| D | RubiksCube.eml | | | 6 | ------ |
| D | RubiksCube.userlibraries | | | 3 | --- |
| M | src/PatternTable.java | | | 30 | +++++++++++++++++++++++++++--- |
| M | src/RubiksColor.java | | | 37 | ++++++++++++++++++++++++++++++------- |
| A | src/RubiksCubeSolver.java | | | 150 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | src/RubiksPatternTable.java | | | 95 | ++++++++++++++++++++++++++++++++++++++++++++++--------------------------------- |
| M | src/RubiksTest.java | | | 15 | +++++++++++---- |
7 files changed, 273 insertions(+), 63 deletions(-)
diff --git a/RubiksCube.eml b/RubiksCube.eml @@ -1,6 +0,0 @@ -<?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 @@ -1,3 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<eclipse-userlibraries /> - diff --git a/src/PatternTable.java b/src/PatternTable.java @@ -18,9 +18,9 @@ public class PatternTable { } /** - * Updates the pattern table with a new RubiksSubState's - * key and value. - * @param state The RubiksSubState to store. + * Updates the pattern table with a new key and value. + * @param state The hashed state. + * @param heuristic Heuristic of state. */ public void updateTable(int state, byte heuristic) { try { @@ -36,6 +36,30 @@ public class PatternTable { } /** + * Reads the pattern table. + * @returns Byte array of byte[key] = value. + */ + public byte[] readTable() { + // 88mil is the max for corner states in rubik's cube + byte[] result = new byte[88179840]; + + try { + BufferedReader in = + new BufferedReader(new FileReader(file)); + String str; + while ((str = in.readLine()) != null) { + String[] parts = str.trim().split(":"); + result[Integer.valueOf(parts[0])] = Byte.valueOf(parts[1]); + } + in.close(); + } catch (IOException e) { + System.err.println("Error: " + e.getMessage()); + e.printStackTrace(); + } + return result; + } + + /** * Clears or empties the entire target file. */ public void clearTable() { diff --git a/src/RubiksColor.java b/src/RubiksColor.java @@ -7,19 +7,23 @@ import java.util.Random; * Different kinds of colors in a Rubik's cube. */ public enum RubiksColor { - RED ("R"), - GREEN ("G"), - BLUE ("B"), - YELLOW ("Y"), - ORANGE ("O"), - WHITE ("W"); + RED ("R",0), + GREEN ("G",1), + BLUE ("B",2), + YELLOW ("Y",3), + ORANGE ("O",4), + WHITE ("W",5); /* The color in string format. */ private final String string; + /* The number of color. */ + private final int num; + /* Every RubiksColor requires a string format. */ - RubiksColor(String string) { + RubiksColor(String string, int num) { this.string = string; + this.num = num; } /** @@ -39,6 +43,21 @@ public enum RubiksColor { } /** + * Finds the RubiksColor type by searching with its int type. + * @param num The integer of the RubiksColor. + * @return The correct RubiksColor of the integer num. + */ + public static RubiksColor find(int num) { + if(num == 0) return RED; + else if(num == 1) return GREEN; + else if(num == 2) return BLUE; + else if(num == 3) return YELLOW; + else if(num == 4) return ORANGE; + else if(num == 5) return WHITE; + else return null; + } + + /** * Picks a random rotation. * @return The random rotation. */ @@ -56,4 +75,8 @@ public enum RubiksColor { public String toString() { return this.string; } + + public int toInt() { + return this.num; + } } diff --git a/src/RubiksCubeSolver.java b/src/RubiksCubeSolver.java @@ -0,0 +1,150 @@ +import java.util.Collection; +import java.util.LinkedList; +import java.util.PriorityQueue; +import java.util.Stack; + +public class RubiksCubeSolver { + + /* Generated pattern tables. */ + private RubiksPatternTable table; + + /* Keeps track of nodes used. */ + private LinkedList<Node> usedNodes = new LinkedList<Node>(); + + /* Max Depth of the traversal to solve. */ + private final int MAX_DEPTH = 18; + + public RubiksCubeSolver(RubiksPatternTable table) { + this.table = table; + } + + /** + * Solves a rubik's cube optimally. + * @param cube The rubik's cube to solve. + * @return The sequence of moves it took to solve. + */ + public String solve(RubiksCube cube) { + PriorityQueue<Node> travq = + new PriorityQueue<Node>(MAX_DEPTH*MAX_DEPTH); + travq.add(new Node(cube, null, 0, retrieveCubeHeuristic(cube), -1)); + Node current = new Node(null, null, -1, -1, -1); + int depth = 0; + while(!travq.isEmpty()) { + current = travq.poll(); + if(current.cube.isEqualTo(RubiksCube.GOAL)) { + break; + } else { + usedNodes.add(current); + Collection<Node> children = explore(current); + travq.addAll(children); + } + } + usedNodes.clear(); + return retrievePathToNode(current); + } + + /** + * Explores all neighbors. + * @param node The cube node root. + * @return Neighbors that haven't been checked. + */ + private Collection<Node> explore(Node node) { + Collection<Node> children = new LinkedList<Node>(); + for (RubiksColor face : RubiksColor.values()) { + for (int i = 0; i < 3; i++) { + if(node.action % 6 != i) { + RubiksCube childState = new RubiksCube(node.cube.getState()); + childState.rotate(i + 1, face); + if(!usedNodes.contains(childState)) { + int childCost = node.cost + 1; + int heuristic = retrieveCubeHeuristic(childState); + int actionId = 6*i + face.toInt(); + children.add(new Node(childState, node, childCost, heuristic, actionId)); + } + } + } + } + return children; + } + + /** + * Traverses all cube nodes that it took to reach goal state. + * @param node The node to start from. + * @return The string sequence of moves + */ + private String retrievePathToNode(Node node) { + String path = ""; + Stack<String> actions = new Stack<String>(); + Node traverser = node; + while(traverser.parent != null) { + actions.push(getAction(traverser.action)); + traverser = traverser.parent; + } + while(!actions.isEmpty()) + path += actions.pop(); + + return path; + } + + private String getAction(int action) { + String color = RubiksColor.find(action % 6).toString(); + return color + ((int)action / 6) +1; + } + + private int retrieveCubeHeuristic(RubiksCube cube) { + RubiksState state = cube.getState(); + + int corners = table.getCorners()[state.getCorners().hashState()]; + int edgeState = table.getHalfEdges()[state.getHalfEdges().hashState()]; + int edge2State = table.getHalf2Edges()[state.getHalf2Edges().hashState()]; + int max = corners; + if(edgeState > max) max = edgeState; + if(edge2State > max) max = edge2State; + return max; + } + + private class Node implements Comparable<Node> { + public RubiksCube cube; + public Node parent; + public int cost, heuristic, action; + public Node( + RubiksCube cube, + Node parent, + int cost, + int heuristic, + int action) { + this.cost = cost; + this.heuristic = heuristic; + this.cube = cube; + this.parent = parent; + this.action = action; + } + + @Override + public String toString() { + return "Action: "+getAction(action)+" -> " + (cost + heuristic); + } + @Override + public boolean equals(Object obj) { + if (this == obj) return true; + else if (obj == null) return false; + else if (getClass() != obj.getClass()) return false; + + Node other = (Node) obj; + if (!getOuterType().equals(other.getOuterType())) return false; + else if (cube == null && other.cube != null) return false; + else if (!cube.equals(other.cube)) return false; + + return true; + } + private RubiksCubeSolver getOuterType() { + return RubiksCubeSolver.this; + } + @Override + public int compareTo(Node other) { + int value = this.cost + this.heuristic; + int otherValue = other.cost + other.heuristic; + return value - otherValue; + } + } +} diff --git a/src/RubiksPatternTable.java b/src/RubiksPatternTable.java @@ -55,9 +55,9 @@ public class RubiksPatternTable { cornersTable = new PatternTable("corners.txt"); halfEdgesTable = new PatternTable("halfEdges.txt"); half2EdgesTable = new PatternTable("half2Edges.txt"); - cornersTable.clearTable(); - halfEdgesTable.clearTable(); - half2EdgesTable.clearTable(); + transferCorners(cornersTable.readTable()); + transferHalfEdge(halfEdgesTable.readTable()); + transferHalf2Edge(half2EdgesTable.readTable()); } /** @@ -72,12 +72,16 @@ public class RubiksPatternTable { this.cornersTable = corners; this.halfEdgesTable = halfEdges; this.half2EdgesTable = half2Edges; - this.cornersTable.clearTable(); - this.halfEdgesTable.clearTable(); - this.half2EdgesTable.clearTable(); + transferCorners(cornersTable.readTable()); + transferHalfEdge(halfEdgesTable.readTable()); + transferHalf2Edge(half2EdgesTable.readTable()); } - // TODO test + /** + * Generates a pattern table of all possible rubik's cube states. + * Tables are separated by corners and half of the edges. + * @throws Exception + */ public void generateTables() throws Exception { // start at the goal state and add it to queue RubiksState rootCube = @@ -139,9 +143,9 @@ public class RubiksPatternTable { half2EdgesTable.updateTable(hash, half2edgestate.getHeuristic()); } - System.out.println( + /*System.out.println( "Added State: "+current.getState() + - " -> Heuristic: "+current.getHeuristic()); + " -> Heuristic: "+current.getHeuristic());*/ } catch (Exception e) { e.printStackTrace(); @@ -158,39 +162,26 @@ public class RubiksPatternTable { return true; } - /** - * Uses IDA* search to find optimal path. - * TODO for later - */ - public void lookupTable() { - RubiksCube cube = new RubiksCube(true); - // check if is goal state - // if not open its children - // search each and open child with lowest heuristic + current depth - // frontier queue to search next - // check if maxLimit depth has been passed + /* Transfers table state to array. */ + private void transferCorners(byte[] values) { + for(int i=0; i<corners.length; i++) { + corners[i] = values[i]; + } } - // TODO test - /*public void saveState(RubiksState state, short depth) { - //corners - RubiksAttainableState attainable = - new RubiksAttainableState(state.getCorners(), depth); - //corners[corners.length-1] = attainable; - cornersTable.updateTable(attainable); - - //half edges - RubiksAttainableState attainable1 = - new RubiksAttainableState(state.getHalfEdges(), depth); - //halfEdges[halfEdges.length-1] = attainable1; - halfEdgesTable.updateTable(attainable1); - - //second half edges - RubiksAttainableState attainable2 = - new RubiksAttainableState(state.getHalf2Edges(), depth); - //half2Edges[half2Edges.length-1] = attainable2; - half2EdgesTable.updateTable(attainable2); - } */ + /* Transfers table state to array. */ + private void transferHalfEdge(byte[] values) { + for(int i=0; i<halfEdges.length; i++) { + halfEdges[i] = values[i]; + } + } + + /* Transfers table state to array. */ + private void transferHalf2Edge(byte[] values) { + for(int i=0; i<half2Edges.length; i++) { + half2Edges[i] = values[i]; + } + } /** * Retrieve pattern table of all corner states. @@ -215,4 +206,28 @@ public class RubiksPatternTable { public PatternTable getHalf2EdgesTable() { return half2EdgesTable; } + + /** + * Retrieve all corner states. + * @return all corner states. + */ + public byte[] getCorners() { + return corners; + } + + /** + * Retrieve first half of all edge states. + * @return first half of all edge states. + */ + public byte[] getHalfEdges() { + return halfEdges; + } + + /** + * Retrieve second half of all edge states. + * @return second half of all edge states. + */ + public byte[] getHalf2Edges() { + return half2Edges; + } } diff --git a/src/RubiksTest.java b/src/RubiksTest.java @@ -1,5 +1,6 @@ import java.io.FileNotFoundException; import java.io.FileReader; +import java.util.PriorityQueue; class RubiksTest { @@ -128,13 +129,19 @@ class RubiksTest /*RubiksPatternTable patternTable = new RubiksPatternTable(); try { - patternTable.generateTables(); + RubiksCube cube0 = + new RubiksCube(new FileReader("test_cases/cube0")); + + RubiksCubeSolver solver = new RubiksCubeSolver(patternTable); + + System.out.println(solver.solve(cube0)); + } catch (Exception e) { System.err.println(e.getMessage()); e.printStackTrace(); - } */ + } */ - try { + /*try { RubiksCube cube0 = new RubiksCube(new FileReader("test_cases/cube0")); RubiksCube cube1 = new RubiksCube(new FileReader("test_cases/cube1")); RubiksCube cube2 = new RubiksCube(new FileReader("test_cases/cube2")); @@ -147,6 +154,6 @@ class RubiksTest RubiksCube cube9 = new RubiksCube(new FileReader("test_cases/cube9")); } catch (FileNotFoundException e) { e.printStackTrace(); - } + } */ } } \ No newline at end of file