rubikscube

commit 394a040e7a0cea22f95955c7615d370499fe7348
parent 6d1cdce53a4ab201f63d56608b3c0fcf6d540a66
Author: Jul <jul@9o.is>
Date:   Fri, 26 Oct 2012 10:39:46 -0400

Makes sure cube is unique when generating tables.

Diffstat:
M
src/RubiksCube.java
 | 
46
++++++++++++++++++++++++++++++++++++++++++++--
M
src/RubiksPatternTable.java
 | 
32
+++++++++++++++++++++-----------

2 files changed, 65 insertions(+), 13 deletions(-)
diff --git a/src/RubiksCube.java b/src/RubiksCube.java
@@ -8,6 +8,10 @@ import java.util.Random;
  * rotate to a random position, and more.
  */
 public class RubiksCube {
+
+    /** The cube in goal state. */
+    public static final RubiksCube GOAL = new RubiksCube(false);
+
     /*
      * Amount of sides or faces in this cube.
      * A cube has to be six sides.
@@ -124,8 +128,8 @@ public class RubiksCube {
         cube[0][1][2] = RubiksColor.find(halfEdges.substring(4,5));
         cube[3][0][1] = RubiksColor.find(halfEdges.substring(5,6));
         // edge 4
-        cube[2][0][1] = RubiksColor.find(halfEdges.substring(6,7));
-        cube[0][2][1] = RubiksColor.find(halfEdges.substring(7,8));
+        cube[0][2][1] = RubiksColor.find(halfEdges.substring(6,7));
+        cube[2][0][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));
@@ -152,6 +156,8 @@ public class RubiksCube {
         // edge 12
         cube[5][1][2] = RubiksColor.find(half2Edges.substring(10,11));
         cube[3][1][2] = RubiksColor.find(half2Edges.substring(11,12));
+
+        fillInMiddleColors();
     }
 
     /**
@@ -166,6 +172,7 @@ public class RubiksCube {
                     String input = state.substring(count, ++count);
                     cube[side][row][column] = RubiksColor.find(input);
                 }
+        fillInMiddleColors();
     }
 
     /**
@@ -307,6 +314,14 @@ public class RubiksCube {
     }
 
     /**
+     * The array state of this rubik's cube.
+     * @return The state array.
+     */
+    public RubiksColor[][][] getCubeArray() {
+        return cube;
+    }
+
+    /**
      * Rotates and returns all the possible children/neighbor states.
      * @return an array of all neighbor states.
      */
@@ -807,4 +822,31 @@ public class RubiksCube {
     private int switchPiece(int piece) {
         if(piece==2) return 0; else return 2;
     }
+
+    private void fillInMiddleColors() {
+        cube[0][1][1] = RubiksColor.RED;
+        cube[1][1][1] = RubiksColor.GREEN;
+        cube[2][1][1] = RubiksColor.YELLOW;
+        cube[3][1][1] = RubiksColor.BLUE;
+        cube[4][1][1] = RubiksColor.ORANGE;
+        cube[5][1][1] = RubiksColor.WHITE;
+    }
+
+    /**
+     * Checks if this cube has same state as another cube.
+     * @param otherCube The cube to compare with this.
+     * @return If it's the same or not.
+     */
+    public boolean isEqualTo(RubiksCube otherCube) {
+        RubiksColor[][][] otherColors = otherCube.getCubeArray();
+        int side,row,column;
+        for (side=0; side<CUBE_SIDES; side++)
+            for(row=0; row<CUBE_SIZE; row++)
+                for (column=0; column<CUBE_SIZE; column++) {
+                    if(!cube[side][row][column].
+                            equals(otherColors[side][row][column]))
+                        return false;
+                }
+        return true;
+    }
 }
diff --git a/src/RubiksPatternTable.java b/src/RubiksPatternTable.java
@@ -1,4 +1,6 @@
+import java.util.ArrayList;
 import java.util.LinkedList;
+import java.util.List;
 import java.util.Queue;
 
 /**
@@ -78,13 +80,11 @@ public class RubiksPatternTable {
     // TODO test
     public void generateTables() throws Exception {
         // start at the goal state and add it to queue
-        RubiksState rootAttainableState =
-                new RubiksState(new RubiksCube(),1);
+        RubiksState rootCube =
+                new RubiksState(RubiksCube.GOAL,1);
 
-        Queue<RubiksState> travq =
-                new LinkedList<RubiksState>();
-
-        travq.add(rootAttainableState);
+        Queue<RubiksState> travq = new LinkedList<RubiksState>();
+        travq.add(rootCube);
 
         // traverse the queue and handle appropriately
         RubiksState current;
@@ -98,11 +98,12 @@ public class RubiksPatternTable {
                 // 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 RubiksState(
-                                    neighbor,
-                                    current.getHeuristic()+1));
+                    if(corners[neighbor.getCorners().hashState()]==0 &&
+                       halfEdges[neighbor.getHalfEdges().hashState()]==0 &&
+                       half2Edges[neighbor.getHalf2Edges().hashState()]==0)
+                        travq.add(new RubiksState(
+                                neighbor,
+                                current.getHeuristic()+1));
                 }
 
                 // save corner state to array and table
@@ -148,6 +149,15 @@ public class RubiksPatternTable {
         }
     }
 
+    /* Checks if current rubik's state is unique among a group of cubes. */
+    private boolean isCubeUnique(List<RubiksCube> cubes, RubiksState current) {
+        for(RubiksCube check : cubes) {
+            if(check.isEqualTo(new RubiksCube(current)))
+                return false;
+        }
+        return true;
+    }
+
     /**
      * Uses IDA* search to find optimal path.
      * TODO for later