rubikscube
college code for finding optimal rubiks cube solutions in java
git clone https://9o.is/git/rubikscube.git
RubiksCubeSolver.java
(4973B)
1 import java.util.Collection;
2 import java.util.LinkedList;
3 import java.util.PriorityQueue;
4 import java.util.Stack;
5
6 public class RubiksCubeSolver {
7
8 /* Generated pattern tables. */
9 private RubiksPatternTable table;
10
11 /* Keeps track of nodes used. */
12 private LinkedList<Node> usedNodes = new LinkedList<Node>();
13
14 /* Max Depth of the traversal to solve. */
15 private final int MAX_DEPTH = 18;
16
17 public RubiksCubeSolver(RubiksPatternTable table) {
18 this.table = table;
19 }
20
21 /**
22 * Solves a rubik's cube optimally.
23 * @param cube The rubik's cube to solve.
24 * @return The sequence of moves it took to solve.
25 */
26 public String solve(RubiksCube cube) {
27 PriorityQueue<Node> travq =
28 new PriorityQueue<Node>(MAX_DEPTH*MAX_DEPTH);
29 travq.add(new Node(cube, null, 0, heuristic(cube), -1));
30 Node current = new Node(null, null, -1, -1, -1);
31 int depth = 0;
32 while(!travq.isEmpty()) {
33 current = travq.poll();
34 if(current.cube.isEqualTo(RubiksCube.GOAL)) {
35 break;
36 } else {
37 usedNodes.add(current);
38 Collection<Node> children = explore(current);
39 travq.addAll(children);
40 }
41 }
42 usedNodes.clear();
43 return path(current);
44 }
45
46 /**
47 * Explores all neighbors.
48 * @param node The cube node root.
49 * @return Neighbors that haven't been checked.
50 */
51 private Collection<Node> explore(Node node) {
52 Collection<Node> children = new LinkedList<Node>();
53 for (RubiksColor face : RubiksColor.values()) {
54 for (int i = 0; i < 3; i++) {
55 if(node.action % 6 != i) {
56 RubiksCube childState = new RubiksCube(node.cube.getState());
57 childState.rotate(i + 1, face);
58 if(!usedNodes.contains(childState)) {
59 int childCost = node.cost + 1;
60 int heuristic = heuristic(childState);
61 int actionId = 6*i + face.toInt();
62 children.add(new Node(childState, node, childCost, heuristic, actionId));
63 }
64 }
65 }
66 }
67 return children;
68 }
69
70 /**
71 * Traverses all cube nodes that it took to reach goal state.
72 * @param node The node to start from.
73 * @return The string sequence of moves
74 */
75 private String path(Node node) {
76 String path = "";
77 Stack<String> actions = new Stack<String>();
78 Node traverser = node;
79 while(traverser.parent != null) {
80 actions.push(getAction(traverser.action));
81 traverser = traverser.parent;
82 }
83 while(!actions.isEmpty())
84 path += actions.pop();
85
86 return path;
87 }
88
89 private String getAction(int action) {
90 String color = RubiksColor.find(action % 6).toString();
91 return color + ((int)action / 6) +1;
92 }
93
94 private int heuristic(RubiksCube cube) {
95 RubiksState state = cube.getState();
96
97 int corners = table.getCorners()[state.getCorners().hashState()];
98 int edgeState = table.getHalfEdges()[state.getHalfEdges().hashState()];
99 int edge2State = table.getHalf2Edges()[state.getHalf2Edges().hashState()];
100 int max = corners;
101 if(edgeState > max) max = edgeState;
102 if(edge2State > max) max = edge2State;
103 return max;
104 }
105
106 private class Node implements Comparable<Node> {
107 public RubiksCube cube;
108 public Node parent;
109 public int cost, heuristic, action;
110 public Node(
111 RubiksCube cube,
112 Node parent,
113 int cost,
114 int heuristic,
115 int action) {
116 this.cost = cost;
117 this.heuristic = heuristic;
118 this.cube = cube;
119 this.parent = parent;
120 this.action = action;
121 }
122
123 @Override
124 public String toString() {
125 return "Action: "+getAction(action)+" -> " + (cost + heuristic);
126 }
127 @Override
128 public boolean equals(Object obj) {
129 if (this == obj) return true;
130 else if (obj == null) return false;
131 else if (getClass() != obj.getClass()) return false;
132
133 Node other = (Node) obj;
134 if (!getOuterType().equals(other.getOuterType())) return false;
135 else if (cube == null && other.cube != null) return false;
136 else if (!cube.equals(other.cube)) return false;
137
138 return true;
139 }
140 private RubiksCubeSolver getOuterType() {
141 return RubiksCubeSolver.this;
142 }
143 @Override
144 public int compareTo(Node other) {
145 int value = this.cost + this.heuristic;
146 int otherValue = other.cost + other.heuristic;
147 return value - otherValue;
148 }
149 }
150 }