rubikscube
college code for finding optimal rubiks cube solutions in java
git clone https://9o.is/git/rubikscube.git
commit 9071cba2c867c1c95c3ec49f4af3acde2d4a73f2 parent 4fede60b7d0cf63140aa8839ea55db37dd74d26a Author: Jul <jul@9o.is> Date: Sun, 21 Oct 2012 19:09:58 -0400 Javadoc commented almost everything and formatted code so it can stay within a right margin of 70 col. Diffstat:
| M | src/AttainableRubiksState.java | | | 11 | +++++------ |
| M | src/PatternTable.java | | | 17 | +++++++++++++++-- |
| M | src/RubiksColor.java | | | 17 | ++++++++++++----- |
| M | src/RubiksCube.java | | | 145 | +++++++++++++++++++++++++++++++++++++++++++++++++++---------------------------- |
| M | src/RubiksPatternTable.java | | | 50 | ++++++++++++++++++++++++++++++++++++-------------- |
| M | src/RubiksRotation.java | | | 16 | +++++++++++----- |
| M | src/RubiksState.java | | | 34 | ++++++++++++++++++++++++++++++++-- |
| M | src/RubiksTest.java | | | 4 | +++- |
8 files changed, 208 insertions(+), 86 deletions(-)
diff --git a/src/AttainableRubiksState.java b/src/AttainableRubiksState.java @@ -1,8 +1,7 @@ -import java.security.MessageDigest; -import java.security.NoSuchAlgorithmException; - /** - * Just a helper class. + * 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 { @@ -13,9 +12,9 @@ public class AttainableRubiksState { private short heuristic; /** - * An AttainableRubiksState must have a state as a key and a heuristic + * An AttainableRubiksState has a state as a key and a heuristic. * @param key the state - * @param heuristic the heuristic (or moves away from the goal state). + * @param heuristic the heuristic (moves from the goal state). */ public AttainableRubiksState(String key, short heuristic) { this.key = key; diff --git a/src/PatternTable.java b/src/PatternTable.java @@ -1,17 +1,27 @@ import java.io.*; /** - * Stores a mapping of a key (hash) to two values (state,heuristic) in a file. + * Stores a mapping of a key to a value in a file. + * Stores in the format: key:value */ public class PatternTable { /** The file that contains the pattern table. */ private String file; - PatternTable(String file) { + /** + * Creates a pattern table in a specified file. + * @param file The file to save the pattern table. + */ + public PatternTable(String file) { this.file = file; } + /** + * Updates the pattern table with a new AttainableRubiksState's + * key and value. + * @param attainable The AttainableRubiksState to store. + */ public void updateTable(AttainableRubiksState attainable) { try { BufferedWriter out = @@ -24,6 +34,9 @@ public class PatternTable { } } + /** + * Clears or empties the entire target file. + */ public void clearTable() { try { BufferedWriter out = diff --git a/src/RubiksColor.java b/src/RubiksColor.java @@ -1,5 +1,5 @@ /** - * Different colors in a Rubik's cube. + * Different kinds of colors in a Rubik's cube. */ public enum RubiksColor { RED ("R"), @@ -9,16 +9,19 @@ public enum RubiksColor { ORANGE ("O"), WHITE ("W"); + /* The color in string format. */ private final String string; + /* Every RubiksColor requires a string format. */ RubiksColor(String string) { this.string = string; } - public String toString() { - return this.string; - } - + /** + * Finds the RubiksColor type by searching with its string type. + * @param string The string of the RubiksColor. + * @return The correct RubiksColor of the string string. + */ public static RubiksColor find(String string) { if(string.equals("R")) return RED; else if(string.equals("G")) return GREEN; @@ -27,4 +30,8 @@ public enum RubiksColor { else if(string.equals("O")) return ORANGE; else return WHITE; } + + public String toString() { + return this.string; + } } diff --git a/src/RubiksCube.java b/src/RubiksCube.java @@ -1,24 +1,30 @@ import java.util.Random; /** - * A 3 by 3, six sided Rubik's cube. - * - * @author Julio Enrique Cabrera + * A 3 by 3, six sided Rubik's cube. It can rotate, print its state, + * rotate to a random position, and more. */ public class RubiksCube { - /* Amount of sides or faces (6) in this cube. */ + /* + * Amount of sides or faces in this cube. + * A cube has to be six sides. + */ private final int CUBE_SIDES = 6; - /* Size of the cube. (3 by 3). Might break if changed. */ + /* + * Size of the cube. (3 by 3). Might break if changed. + */ private final int CUBE_SIZE = 3; - /* 3-Dimensional array that stores the state of the cube. */ + /* + * 3-Dimensional array that stores the state of the cube. + */ private RubiksColor cube[][][]; /** * Initiates a rubik's cube at it's goal state. */ - RubiksCube() { + public RubiksCube() { cube = new RubiksColor[CUBE_SIDES][CUBE_SIZE][CUBE_SIZE]; initGoalState(); } @@ -26,8 +32,9 @@ public class RubiksCube { /** * Initiates a rubik's cube at it's goal state if parameter is * false or it randomizes the state if parameter is true. + * @param random If the state will be random or not. */ - RubiksCube(boolean random) { + public RubiksCube(boolean random) { cube = new RubiksColor[CUBE_SIDES][CUBE_SIZE][CUBE_SIZE]; if(random) { initGoalState(); @@ -37,63 +44,67 @@ public class RubiksCube { /** * Initiates a Rubik's cube from an existing state. + * @param state The existing state. */ - RubiksCube(RubiksState state) { + public RubiksCube(RubiksState state) { cube = new RubiksColor[CUBE_SIDES][CUBE_SIZE][CUBE_SIZE]; setState(state); } /** * 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]; + RubiksColor[] cornerColors = + new RubiksColor[CUBE_SIDES*CORNERS]; int i=0; for(char ch : state.getCorners().toCharArray()) { - cornerColors[i] = RubiksColor.find(Character.toString(ch)); i++; + 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){ + if(j==0) cube[i][0][0] = cornerColors[i*CORNERS + j]; - } else if(j==1) { + else if(j==1) cube[i][0][2] = cornerColors[i*CORNERS + j]; - } else if(j==2) { + else if(j==2) cube[i][2][0] = cornerColors[i*CORNERS + j]; - } else if(j==3) { + 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]; + RubiksColor[] halfEdgesColors = + new RubiksColor[CUBE_SIDES*HALF_EDGES]; i=0; for(char ch : state.getHalfEdges().toCharArray()) { - halfEdgesColors[i] = RubiksColor.find(Character.toString(ch)); i++; + 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){ + if(j==0) cube[i][0][1] = halfEdgesColors[i*HALF_EDGES + j]; - } else if(j==1) { + else if(j==1) cube[i][1][0] = halfEdgesColors[i*HALF_EDGES + j]; - } } i=0; for(char ch : state.getHalf2Edges().toCharArray()) { - halfEdgesColors[i] = RubiksColor.find(Character.toString(ch)); i++; + 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){ + if(j==0) cube[i][1][2] = halfEdgesColors[i*HALF_EDGES + j]; - } else if(j==1) { + else if(j==1) cube[i][2][1] = halfEdgesColors[i*HALF_EDGES + j]; - } } } @@ -105,12 +116,18 @@ public class RubiksCube { for (side=0; side<CUBE_SIDES; side++) for(row=0; row<CUBE_SIZE; row++) for (column=0; column<CUBE_SIZE; column++) { - if(side==0) cube[side][row][column]= RubiksColor.RED; - else if(side==1) cube[side][row][column]= RubiksColor.GREEN; - else if(side==2) cube[side][row][column]= RubiksColor.YELLOW; - else if(side==3) cube[side][row][column]= RubiksColor.BLUE; - else if(side==4) cube[side][row][column]= RubiksColor.ORANGE; - else cube[side][row][column]= RubiksColor.WHITE; + if(side==0) + cube[side][row][column]= RubiksColor.RED; + else if(side==1) + cube[side][row][column]= RubiksColor.GREEN; + else if(side==2) + cube[side][row][column]= RubiksColor.YELLOW; + else if(side==3) + cube[side][row][column]= RubiksColor.BLUE; + else if(side==4) + cube[side][row][column]= RubiksColor.ORANGE; + else + cube[side][row][column]= RubiksColor.WHITE; } } @@ -118,9 +135,9 @@ public class RubiksCube { * Shuffles the rubik's cube to a random state. */ public void initRandomState() { - Random random = new Random(); for(int i=0; i<100; i++) { - rotate(random.nextInt(1), RubiksRotation.randomRotation()); + rotate(new Random().nextInt(1), + RubiksRotation.randomRotation()); } } @@ -135,11 +152,14 @@ public class RubiksCube { 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]); + state.setCorners(state.getCorners() + + cube[side][row][column]); else if((row==0 || row==2) && column==1) - state.setHalfEdges(state.getHalfEdges() + cube[side][row][column]); + state.setHalfEdges(state.getHalfEdges() + + cube[side][row][column]); else if(row==1 && (column==0 || column==2)) - state.setHalf2Edges(state.getHalf2Edges() + cube[side][row][column]); + state.setHalf2Edges(state.getHalf2Edges() + + cube[side][row][column]); } return state; } @@ -149,7 +169,7 @@ public class RubiksCube { * @return an array of all neighbor states. */ public RubiksState[] getNeighborStates() { - RubiksState[] states = new RubiksState[18]; // 18 total states + RubiksState[] states = new RubiksState[18]; //18 total states for(int i=0; i<CUBE_SIZE-1; i++) { //vertical rotate(i,RubiksRotation.VERTICAL_CLOCKWISE); @@ -158,7 +178,9 @@ public class RubiksCube { states[2+i] = getState(); rotate(i,RubiksRotation.VERTICAL_CLOCKWISE); states[4+i] = getState(); - rotate(i,RubiksRotation.VERTICAL_CLOCKWISE); //original state + + //original state + rotate(i,RubiksRotation.VERTICAL_CLOCKWISE); rotate(i,RubiksRotation.SIDE_VERTICAL_CLOCKWISE); states[6+i] = getState(); @@ -166,7 +188,9 @@ public class RubiksCube { states[8+i] = getState(); rotate(i,RubiksRotation.SIDE_VERTICAL_CLOCKWISE); states[10+i] = getState(); - rotate(i,RubiksRotation.SIDE_VERTICAL_CLOCKWISE); //original state + + //original state + rotate(i,RubiksRotation.SIDE_VERTICAL_CLOCKWISE); rotate(i,RubiksRotation.HORIZONTAL_CLOCKWISE); states[12+i] = getState(); @@ -174,7 +198,9 @@ public class RubiksCube { states[14+i] = getState(); rotate(i,RubiksRotation.HORIZONTAL_CLOCKWISE); states[16+i] = getState(); - rotate(i,RubiksRotation.HORIZONTAL_CLOCKWISE); //original state + + //original state + rotate(i,RubiksRotation.HORIZONTAL_CLOCKWISE); } return states; } @@ -193,20 +219,37 @@ public class RubiksCube { if(side==1 || side==2 || side==3) { if(side==1) { - if(row==0) System.out.print(cube[side+row][row][column]); - else if(row==1) System.out.print(cube[side+row][row-1][column]); - else System.out.print(cube[side+row][row-2][column]); + if(row==0) + System.out.print( + cube[side+row][row][column]); + else if(row==1) + System.out.print( + cube[side+row][row-1][column]); + else + System.out.print( + cube[side+row][row-2][column]); } if(side==2) { - if(row==0) System.out.print(cube[side-1][row+1][column]); - else if(row==1) System.out.print(cube[side][row][column]); - else System.out.print(cube[side+1][row-1][column]); + if(row==0) + System.out.print( + cube[side-1][row+1][column]); + else if(row==1) + System.out.print( + cube[side][row][column]); + else + System.out.print( + cube[side+1][row-1][column]); } else if(side==3) { - if(row==0) System.out.print(cube[side-2][row+2][column]); - else if(row==1) System.out.print(cube[side-1][row+1][column]); - else System.out.print(cube[side][row][column]); + if(row==0) + System.out.print( + cube[side-2][row+2][column]); + else if(row==1) + System.out.print( + cube[side-1][row+1][column]); + else + System.out.print( + cube[side][row][column]); } - //else System.out.print(threeD[side+(column-1)][row][column]); if(row==2 && column==2) System.out.println(); } else System.out.print(cube[side][row][column]); @@ -221,7 +264,7 @@ 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, ignores the middle piece) + * @param piece Piece to rotate (0-1 if cube size is 3) * @param rotation Type of rotation */ public void rotate(int piece, RubiksRotation rotation) { diff --git a/src/RubiksPatternTable.java b/src/RubiksPatternTable.java @@ -2,8 +2,8 @@ import java.util.LinkedList; import java.util.Queue; /** - * Has the potential of generating tables of heuristics - * for the Rubik's cube. + * Generates tables of ALL attainable Rubik's cube states alongside + * heuristics or the amount of moves to its goal state. */ public class RubiksPatternTable { @@ -11,39 +11,45 @@ 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 AttainableRubiksState[] corners = + new AttainableRubiksState[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 AttainableRubiksState[] halfEdges = + new AttainableRubiksState[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 AttainableRubiksState[] half2Edges = + new AttainableRubiksState[42577920]; /* - * All attainable corner states of a rubik's cube, alongside its heuristic, - * will be stored in a table (file). + * All attainable corner states of a rubik's cube, + * alongside its heuristic, will be stored in a table (file). */ private PatternTable cornersTable; /* - * Half of all attainable edge states of a rubik's cube, alongside its heuristic, - * will be stored in a table (file). + * Half of all attainable edge states of a rubik's cube, + * alongside its heuristic, will be stored in a table (file). */ private PatternTable halfEdgesTable; /* - * Second half of all attainable edge states of a rubik's cube, alongside - * its heuristic, will be stored in a table (file). + * Second half of all attainable edge states of a rubik's cube, + * alongside its heuristic, will be stored in a table (file). */ private PatternTable half2EdgesTable; - RubiksPatternTable() { + /** + * Create a Rubik's Pattern Table. + */ + public RubiksPatternTable() { cornersTable = new PatternTable("corners.txt"); halfEdgesTable = new PatternTable("halfEdges.txt"); half2EdgesTable = new PatternTable("half2Edges.txt"); @@ -52,6 +58,12 @@ public class RubiksPatternTable { half2EdgesTable.clearTable(); } + /** + * Create a Rubik's Pattern Table with specified files. + * @param corners File to store corner states. + * @param halfEdges File to store half of the edge states. + * @param half2Edges File to store other half of the edge states. + */ RubiksPatternTable(PatternTable corners, PatternTable halfEdges, PatternTable half2Edges) { @@ -126,17 +138,27 @@ public class RubiksPatternTable { half2EdgesTable.updateTable(attainable2); } + /** + * Retrieve pattern table of all corner states. + * @return Pattern table of all corner states. + */ public PatternTable getCornersTable() { return cornersTable; } + /** + * Retrieve pattern table for the first half of all edge states. + * @return Pattern table for the first half of all edge states. + */ public PatternTable getHalfEdgesTable() { return halfEdgesTable; } + /** + * Retrieve pattern table for the second half of all edge states. + * @return Pattern table for the second half of all edge states. + */ public PatternTable getHalf2EdgesTable() { return half2EdgesTable; } - - } diff --git a/src/RubiksRotation.java b/src/RubiksRotation.java @@ -14,12 +14,18 @@ public enum RubiksRotation { 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())); - private static final int SIZE = VALUES.size(); - private static final Random RANDOM = new Random(); - public static RubiksRotation randomRotation() { - return VALUES.get(RANDOM.nextInt(SIZE)); - } + /* Cached size of all possible values. */ + private static final int SIZE = VALUES.size(); } diff --git a/src/RubiksState.java b/src/RubiksState.java @@ -11,37 +11,67 @@ public class RubiksState { /* State of half of the other edges. */ private String half2Edges; - RubiksState(){ + /** + * Initiates this state. + */ + public RubiksState() { corners = ""; halfEdges = ""; half2Edges = ""; } + /** + * Set the state for this corners' state. + * @param corners New state for corners. + */ public void setCorners(String corners) { this.corners = 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; } + /** + * 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; } + /** + * Retrieves the state of the corners. + * @return State of the corners. + */ public String getCorners() { return corners; } + /** + * Retrieves the state of first half of the edges. + * @return State of first half of the edges. + */ public String getHalfEdges() { return halfEdges; } + /** + * Retrieves the state of second half of the edges. + * @return State of second half of the edges. + */ public String getHalf2Edges() { return half2Edges; } - /** All states combined. */ + /** + * All part-states combined to make a final Rubik's cube state.. + * @return The entire state of a cube. + */ public String getState() { return getCorners() + getHalfEdges() + getHalf2Edges(); } diff --git a/src/RubiksTest.java b/src/RubiksTest.java @@ -21,7 +21,9 @@ class RubiksTest //System.out.println(cornersTable.valueOf("WYWWRORBRBYY")); //cornersTable.clearTable(); - RubiksCube cube = new RubiksCube(); + RubiksCube cube = new RubiksCube(true); + cube.rotate(0, RubiksRotation.VERTICAL_CLOCKWISE); + cube.printState(); // test if setState works /*RubiksCube randomCube = new RubiksCube(true);