rubikscube

RubiksPatternTable.java

(7961B)

 import java.util.ArrayList;
 import java.util.LinkedList;
 import java.util.List;
 import java.util.Queue;
 
 /**
  * Generates tables of ALL attainable Rubik's cube states alongside
  * heuristics or the amount of moves to its goal state.
  */
 public class RubiksPatternTable {
 
     /*
      * All attainable corner states of a rubik's cube.
      * There are 8! * 3^7 = 88,179,840 possible combination.
      */
     private byte[] corners =
             new byte[88179840];
 
     /*
      * Half of all attainable edge states of a  rubik's cube.
      * There are 12!/6! * 2^6 = 42,577,920 possible combinations.
      */
     private byte[] halfEdges =
             new byte[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 byte[] half2Edges =
             new byte[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;
 
     /**
      * Create a Rubik's Pattern Table.
      */
     public RubiksPatternTable() {
         cornersTable = new PatternTable("corners.txt");
         halfEdgesTable = new PatternTable("halfEdges.txt");
         half2EdgesTable = new PatternTable("half2Edges.txt");
         transferCorners(cornersTable.readTable());
         transferHalfEdge(halfEdgesTable.readTable());
         transferHalf2Edge(half2EdgesTable.readTable());
     }
 
     /**
      * 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) {
         this.cornersTable = corners;
         this.halfEdgesTable = halfEdges;
         this.half2EdgesTable = half2Edges;
         transferCorners(cornersTable.readTable());
         transferHalfEdge(halfEdgesTable.readTable());
         transferHalf2Edge(half2EdgesTable.readTable());
     }
 
     /**
      * 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 =
                 new RubiksState(RubiksCube.GOAL,1);
 
         Queue<RubiksState> travq = new LinkedList<RubiksState>();
         travq.add(rootCube);
 
         // traverse the queue and handle appropriately
         RubiksState current;
         while(!travq.isEmpty()) {
             try {
                 // poll the queue and convert it to state and cube
                 // for easier manipulation
                 current = travq.poll();
                 RubiksCube cube = new RubiksCube(current);
 
                 // iterate the current cube's neighbors; add to queue
                 // if the state hasn't been added yet
                 for(RubiksState neighbor : cube.getNeighborStates()) {
                     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
                 RubiksSubState cornerstate =
                         new RubiksCornerState(
                                 current.getCorners().toString(),
                                 current.getHeuristic());
                 int hash = cornerstate.hashState();
                 if(corners[hash] == 0) {
                     corners[hash] = cornerstate.getHeuristic();
                     cornersTable.updateTable(hash, cornerstate.getHeuristic());
                 }
 
                 // save first set of edges to array and table
                 RubiksSubState halfedgestate =
                         new RubiksHalfEdgeState(
                                 current.getHalfEdges().toString(),
                                 current.getHeuristic());
                 hash = halfedgestate.hashState();
                 if(halfEdges[hash] == 0) {
                     halfEdges[hash] = halfedgestate.getHeuristic();
                     halfEdgesTable.updateTable(hash, halfedgestate.getHeuristic());
                 }
 
                 // save second set of edges to array and table
                 RubiksSubState half2edgestate =
                         new RubiksHalfEdgeState(
                                 current.getHalf2Edges().toString(),
                                 current.getHeuristic());
                 hash = half2edgestate.hashState();
                 if(half2Edges[hash] == 0) {
                     half2Edges[hash] = half2edgestate.getHeuristic();
                     half2EdgesTable.updateTable(hash, half2edgestate.getHeuristic());
                 }
 
                 /*System.out.println(
                         "Added State: "+current.getState() +
                                 " -> Heuristic: "+current.getHeuristic());*/
 
            } catch (Exception e) {
                 e.printStackTrace();
             }
         }
     }
 
     /* 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;
     }
 
     /* Transfers table state to array. */
     private void transferCorners(byte[] values) {
         for(int i=0; i<corners.length; i++) {
             corners[i] = values[i];
         }
     }
 
     /* 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.
      * @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;
     }
 
     /**
      * 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;
     }
 }