rubikscube

commit 4fede60b7d0cf63140aa8839ea55db37dd74d26a
parent a2ce3fc4d70dd222ba3a8208ae65e6109ab3065c
Author: Jul <jul@9o.is>
Date:   Sun, 21 Oct 2012 16:52:32 -0400

Made changes & fixes to rubik's pattern table generator

Diffstat:
D
src/KorfHeuristic.java
 | 
110
-------------------------------------------------------------------------------
A
src/RubiksPatternTable.java
 | 
142
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 142 insertions(+), 110 deletions(-)
diff --git a/src/KorfHeuristic.java b/src/KorfHeuristic.java
@@ -1,110 +0,0 @@
-import java.util.LinkedList;
-import java.util.Queue;
-
-/**
- * Has the potential of generating tables of heuristics
- * for the Rubik's cube.
- */
-public class KorfHeuristic {
-
-    private AttainableRubiksState[] corners = new AttainableRubiksState[44089920];
-    private AttainableRubiksState[] halfEdges = new AttainableRubiksState[15360];
-    private AttainableRubiksState[] half2Edges = new AttainableRubiksState[15360];
-
-    private PatternTable cornersTable;
-    private PatternTable halfEdgesTable;
-    private PatternTable half2EdgesTable;
-
-    KorfHeuristic() {
-        cornersTable = new PatternTable("corners.txt");
-        halfEdgesTable = new PatternTable("halfEdges.txt");
-        half2EdgesTable = new PatternTable("half2Edges.txt");
-        cornersTable.clearTable();
-        halfEdgesTable.clearTable();
-        half2EdgesTable.clearTable();
-    }
-
-    KorfHeuristic(PatternTable corners,
-                  PatternTable halfEdges,
-                  PatternTable half2Edges) {
-        this.cornersTable = corners;
-        this.halfEdgesTable = halfEdges;
-        this.half2EdgesTable = half2Edges;
-        this.cornersTable.clearTable();
-        this.halfEdgesTable.clearTable();
-        this.half2EdgesTable.clearTable();
-    }
-
-    public void generateTables() {
-        Queue<RubiksState> travq = new LinkedList<RubiksState>();
-        travq.add(new RubiksCube().getState());
-        short depth = 1;
-        RubiksState current;
-        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);
-            }
-        }
-
-    }
-
-    // queue a state if its unique or it's not saved already
-    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.
-     */
-    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
-    }
-
-    public void saveState(RubiksState state, short depth) {
-        //corners
-        AttainableRubiksState attainable =
-                new AttainableRubiksState(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;
-        halfEdgesTable.updateTable(attainable1);
-
-        //second half edges
-        AttainableRubiksState attainable2 =
-                new AttainableRubiksState(state.getHalf2Edges(), depth);
-        half2Edges[half2Edges.length-1] = attainable2;
-        half2EdgesTable.updateTable(attainable2);
-    }
-
-    public PatternTable getCornersTable() {
-        return cornersTable;
-    }
-
-    public PatternTable getHalfEdgesTable() {
-        return halfEdgesTable;
-    }
-
-    public PatternTable getHalf2EdgesTable() {
-        return half2EdgesTable;
-    }
-
-
-}
diff --git a/src/RubiksPatternTable.java b/src/RubiksPatternTable.java
@@ -0,0 +1,142 @@
+import java.util.LinkedList;
+import java.util.Queue;
+
+/**
+ * Has the potential of generating tables of heuristics
+ * for the Rubik's cube.
+ */
+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];
+
+    /*
+     * 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];
+
+    /*
+    * 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];
+
+    /*
+     * 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).
+     */
+    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).
+     */
+    private PatternTable half2EdgesTable;
+
+    RubiksPatternTable() {
+        cornersTable = new PatternTable("corners.txt");
+        halfEdgesTable = new PatternTable("halfEdges.txt");
+        half2EdgesTable = new PatternTable("half2Edges.txt");
+        cornersTable.clearTable();
+        halfEdgesTable.clearTable();
+        half2EdgesTable.clearTable();
+    }
+
+    RubiksPatternTable(PatternTable corners,
+                       PatternTable halfEdges,
+                       PatternTable half2Edges) {
+        this.cornersTable = corners;
+        this.halfEdgesTable = halfEdges;
+        this.half2EdgesTable = half2Edges;
+        this.cornersTable.clearTable();
+        this.halfEdgesTable.clearTable();
+        this.half2EdgesTable.clearTable();
+    }
+
+    //TODO test
+    public void generateTables() {
+        Queue<RubiksState> travq = new LinkedList<RubiksState>();
+        travq.add(new RubiksCube().getState());
+        short depth = 1;
+        RubiksState current;
+        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);
+            }
+        }
+
+    }
+
+    //TODO test
+    // queue a state if its unique or it's not saved already
+    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.
+     * 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
+    }
+
+    // TODO test
+    public void saveState(RubiksState state, short depth) {
+        //corners
+        AttainableRubiksState attainable =
+                new AttainableRubiksState(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;
+        halfEdgesTable.updateTable(attainable1);
+
+        //second half edges
+        AttainableRubiksState attainable2 =
+                new AttainableRubiksState(state.getHalf2Edges(), depth);
+        half2Edges[half2Edges.length-1] = attainable2;
+        half2EdgesTable.updateTable(attainable2);
+    }
+
+    public PatternTable getCornersTable() {
+        return cornersTable;
+    }
+
+    public PatternTable getHalfEdgesTable() {
+        return halfEdgesTable;
+    }
+
+    public PatternTable getHalf2EdgesTable() {
+        return half2EdgesTable;
+    }
+
+
+}