Need a practical solution for creating pattern database(5-5-5) for 15-Puzzle

Question

I have asked this exact question on StackOverflow. I did not get the answer that I was looking for. Please read this question fully before answering. Thank You.

For static pattern database(5-5-5), see this(page 290 and 283) OR there is an explanation below. For What is 15-puzzle?
I am creating a static patter database(5-5-5). This code to to fill entries into the first table. I am doing it via the recursive function insertInDB(). The first input to the recursive function is this (actually the input puzzle contains it in 1-D array. For better understanding I have represented it as 2-D below)

---

1  2  3  4
0  6  0  0
0  0  0  0
0  0  0  0

---

This is my code :

class DBClass
{
    public Connection connection;
     public ResultSet rs;
      public PreparedStatement ps1;
    public PreparedStatement ps2;
    public int k;
      String read_statement,insert_statement;

    public DBClass()
    {
        try {
            Class.forName("com.mysql.jdbc.Driver");
        } catch (ClassNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
            try {
                connection = DriverManager
                    .getConnection("jdbc:mysql://localhost/feedback?"
                        + "user=ashwin&password=ashwin&autoReconnect=true&useUnicode=true&characterEncoding=utf8&validationQuery=Select 1");
                insert_statement="insert into staticpdb1(hash,permutation,cost) values(?,?,?)";
                read_statement="select SQL_NO_CACHE * from staticpdb1 where hash=? and permutation= ? LIMIT 1";
                 ps1=connection.prepareStatement(read_statement, ResultSet.TYPE_SCROLL_SENSITIVE, 
                            ResultSet.CONCUR_UPDATABLE);
                ps2=connection.prepareStatement(insert_statement);
                k=0;
            } catch (SQLException e) {
                // TODO Auto-generated catch block
                e.printStackTrace();
            }
    }
    public int updateIfNecessary(FifteenPuzzle sub) 
       {
           String str=sub.toDBString();
           try
           {

               ps1.setInt(1, sub.hashcode());
               ps1.setString(2,str);
               rs=ps1.executeQuery();
           if(rs.next())
              {
                  //if a row exists, check if the cost is greater than sub's
                  int cost=rs.getInt(3);
                  if(sub.g_n<cost)  //if the cost of sub is less than db row's cost
                  {
                      //replace the cost
                      rs.updateInt(3, sub.g_n);
                      rs.updateRow();
                      return 1;   //only examine - do not insert
                  }
                  else
                      return 0;   //dont examine - return

              }
           else
               return 2;      //insert and examine
           }
           catch(SQLException e)
           {

               System.out.println("here1"+e);
               System.err.println("reported recursion level was "+e.getStackTrace().length);
               return 0;
           }
           finally{

               try{
                   rs.close();}
               catch(final Exception e1)
               {
                   System.out.println("here2"+e1);
               }

           }


       }
    public void insert(FifteenPuzzle sub)
    {

        try{
        String str=sub.toDBString();


         ps2.setInt(1,sub.hashcode());
         ps2.setString(2, str);
         ps2.setInt(3,sub.g_n);
         ps2.executeUpdate();
         ps2.clearParameters();
        }catch(SQLException e)
        {
            System.out.println("here3"+e);
        }
    }

    public void InsertInDB(FifteenPuzzle sub) throws SQLException
       {

           System.out.println(k++);

           int i;

           int p=updateIfNecessary(sub);
          if(p==0)
          {
              System.out.println("returning");
           return;
          }
          if(p==2)
          {
          insert(sub);
          System.out.println("inserted");
          }


           //FifteenPuzzle temp=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n);
           for(i=0;i<sub.puzzle.length;i++)
           {
               if(sub.puzzle[i]!=0)
               {

                   //check the positions it can be moved to
                   if(i%4!=0 && sub.puzzle[i-1]==0)  //left
                   {
                       //create another clone and increment the moves
                       FifteenPuzzle temp_inner=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n+1);
                       //exchange positions
                        int t=temp_inner.puzzle[i];
                        temp_inner.puzzle[i]=temp_inner.puzzle[i-1];
                        temp_inner.puzzle[i-1]=t;
                        InsertInDB(temp_inner);
                   }
                   if(i%4!=3 && sub.puzzle[i+1]==0)  //right
                   {
                       //create another clone and increment the moves
                       FifteenPuzzle temp_inner=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n+1);
                       //exchange positions
                        int t=temp_inner.puzzle[i];
                        temp_inner.puzzle[i]=temp_inner.puzzle[i+1];
                        temp_inner.puzzle[i+1]=t;
                        InsertInDB(temp_inner);
                   }
                   if(i/4!=0 && sub.puzzle[i-4]==0)  //up
                   {
                       //create another clone and increment the moves
                       FifteenPuzzle temp_inner=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n+1);
                       //exchange positions
                        int t=temp_inner.puzzle[i];
                        temp_inner.puzzle[i]=temp_inner.puzzle[i-4];
                        temp_inner.puzzle[i-4]=t;
                        InsertInDB(temp_inner);
                   }
                   if(i/4!=3 && sub.puzzle[i+4]==0)  //down
                   {
                       //create another clone and increment the moves
                       FifteenPuzzle temp_inner=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n+1);
                       //exchange positions
                        int t=temp_inner.puzzle[i];
                        temp_inner.puzzle[i]=temp_inner.puzzle[i+4];
                        temp_inner.puzzle[i+4]=t;
                        InsertInDB(temp_inner);

                  }
             }   
       }

The function insertInDB(FifteenPuzzle fp) in the class is the recursive function and is called first from the main function with the array for the fifteen puzzle argument(puzzle is an integer array field of the Class FifteenPuzzle) being - 1,2,3,4,0,6,0,0,0,0,0,0,0,0,0,0(same as the matrix shown above). Before explaining the other functions I will explain what static pattern database is; briefly(Because of the comments below)

What is a (5-5-5) static pattern database for 15-Puzzle?

Pattern databases are heuristics used to solve a fifteen puzzle(can be any puzzle. But here I will talk about only 15-Puzzle). A heuristic is a number used to determine which state to be expanded next. I is like cost of each state. Here state is a permutation of the 15-Puzzle. For simple puzzles like 8-Puzzle, the heuristic can be manhattan distance. It gives the minimum number of moves, for each misplaced tile, to reach it's goal position. Then manhattan distances for all the tiles are added up to give the cost for that tile. Manhattan distance gives the lower bound to the estimate of the number of moves required to reach the goal state i.e you cannot reach the goal state with moves, less than the manhattan distance. BUT manhattan distance is not a very good heuristic, though admissible, because it does not consider other tiles near by it. If a tile has to be moved to it's goal position, the near by tiles also have to be moved and the number of moves increase. So, clearly for these puzzles, the actual cost is mostly much greater that the manhattan distance.
To overcome this(manhattan distance) and take into account the other tiles, pattern databases were introduced. A static patter database holds the heuristics for sub-problems or for a group of tiles to reach for their goal state. Since, you are calculating the number of moves to make these group of tiles reach their goal state, the other tiles in that group will be taken into account when a tiles is being moved. So, this is a better heuristic and mostly will always is greater than manhattan distance.
5-5-5 static pattern is just a form of static pattern database where the number of groups are 3, two of them containing 5 tiles each and the third one contains 6(6th isthe blank tile).

One of the groups is this matrix :

1  2  3  4
0  6  0  0
0  0  0  0
0  0  0  0

---

I calculating the heuristics/number_of_moves for all permutations of this group to reach the above configuration and inserting them into my database.
The total number of combinations(also the no of rows in db) possible is

16!/(16-5)! = 524160

Now, the other functions - updateIfNecessary(FifteenPuzzle) - this function checks if the array of the passed FifteenPuzzle object is already present in the database. If already present in the database, it checks if the current object's cost is less than the cost in DB. If yes, it replaces it with the current cost else does nothing. The function -insert(FifteenPuzzle) inserts a new permutaion with the cost.

NOTE : fifteenuzzle.g_n is the cost for the puzzle. For the initial puzzle that represents the matrix above, the cost is 0 and for each move the cost is incremented by1.

I have set the stack size to -Xss128m(1024, 512 and 256 were giving a fatal error) for stack size in run configurations.
Currently the recursion number or the depth is 7,500,000 and counting(value of System.out.println(k++);).
The total number of combinations possible is

16!/(16-5)! = 524160

But the depth has already reached 7,500,000. This is because of generation of duplicate states. Currently the number of entries in the database is 513423. You might think that there only 10,000 entries to fill up now. But now the rate at which entries are made has decreased drastically about 1 entry every 30 min. This will never get over then.

I need a solution that is practical - with or without recursion. Is it possible?

Answer 1

It seems that you are moving the blocks to get all the permutations. Then, checking each permutation to be present in DB; if yes then updating the number of moves if necessary.

It would generate a tree. You are generating it in DFS style (by recursive calls). If you do it in BFS style, then you will always get the smallest number of moves. The duplicate states generated later would always have larger moves required. So, you don't have to compare it in the DB.

In the following examples, we will shift 6 and then we see the number of moves.

Priority: Left, Right, Up, Down (as you gave)

DFS Style

1 2 3 4    1 2 3 4
0 6 0 0    6 0 0 0
0 0 0 0    0 0 0 0
0 0 0 0    0 0 0 0
  (0)        (1)

Left most position reached. Now, check to move to it right (from where it came from). That position is already there in the DB, so carry on. Moreover, it can't even go up. So going down.

1 2 3 4    1 2 3 4
0 0 0 0    0 0 0 0
6 0 0 0    0 0 0 0
0 0 0 0    6 0 0 0
  (2)        (3)

Now, go right

           State-1    State-2    State-3
1 2 3 4    1 2 3 4    1 2 3 4    1 2 3 4
0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0
0 0 0 0    0 0 0 0    0 0 0 0    0 0 0 0
6 0 0 0    0 6 0 0    0 0 6 0    0 0 0 6
  (3)        (4)        (5)        (6)

Here you can see that, State-1 can be reached in just 2 (not 4) moves. But that will be revealed later and we'd have to update the DB. So, clearly its a waste of effort.

BFS Style

1 2 3 4    1 2 3 4
0 6 0 0    6 0 0 0
0 0 0 0    0 0 0 0
0 0 0 0    0 0 0 0
  (0)        (1)

Leftmost position reached, now go right

1 2 3 4    1 2 3 4
0 0 6 0    0 0 0 0
0 0 0 0    0 6 0 0
0 0 0 0    0 0 0 0
  (1)        (1)

You can consider this as 6 spreading all the sides equally. Here also, we would have duplicate states but those would have larger min moves required than the first entry of the DB.

You can use a simple queue to implement this.

Pseudocode:

Initialize no_of_moves by 0
enqueue(startingPosition)
insertIntoDB(startingPattern, no_of_moves)
while((currentPattern = dequeue()) is not null)
    if(currentPattern is not already traversed)
        insertIntoDB(currentPattern);
        list<Pattern> allPatterns = patterns which can be reached from currentPattern in just 1 move
        no_of_moves++
        enqueue(allPatterns, no_of_moves)
    end if
end while

There can be many ways to check if a state has already been traversed besides checking it from the DB. I was thinking of hashing but not able to come up.

You can maintain a boolean list mapped from the pattern string (say traversed["1234060000000000"] = true or false). I don't think storing 524160 entries in the main memory would create any problem.

Answer 2

Glad to see someone implemented Pattern Databases!

From your description: "Since, you are calculating the number of moves to make these group of tiles reach their goal state, the other tiles in that group will be taken into account when a tiles is being moved" it seems to me that you are implementing MAX pattern databases while I would strongly recommend you to implement additive (ADD) pattern databases. While it cannot be assured that the latter is always more informed than the former (for a nice discussion on the subject see Fan Yang et al. A General Theory of Additive State Space Abstractions, Journal of Artificial Intelligence Research, 32, pp 631--662, 2008) they are usually preferred. I am just noting this in passing since this choice really makes a difference in the implementation though I have an implementation which can create any of the two PDBs simultaneously. I do not think that posting here the code might be the more convenient (though I would not mind to do so). Thus, if you want to get the full code, email me (or anyone) at [email protected] and I will send it to you. Of course, you can do with it whatever you want.

Now, regarding your question: note that your PDB (implemented usually as a plain binary file with as many entries as different positions might arise which contain just a signed char) serve also as a closed list. At the beginning, initialize your PDB with -1 in all locations. Everytime you generate a new permutation, rank it to get the right entry of your PDB and write down the minimum number of moves it took your algorithm to visit it. Doing so, if you ever generate the same entry again you will easily notice that its content is strictly positive and can be discarded. This works if you fill in your PDB using a backwards breadth-first search.

In case you already noted this then you might be suffering from another problem: the blank location. Be aware that the blank should never be taken into consideration (i.e., it should never be mapped or you might end up with inadmissible estimates). Hence, you have to ignore the blank location when ranking your permutation and this way, each entry of your PDB should contain the minimum number of moves to reach that particular permutation in spite of the blank location.

My last recommendation, use a separate file that just encodes the OPEN list used in the backwards breadth-first search, ie., a file which just contains two pointers: one to the next item to pop and another one to the tail with the position where the next item should be pushed. Well, 5 symbols in your PDB is not that big but you will need this when trying to generate PDBs as large as 7-8 which is the preferred configuration for solving the 15-Puzzle.

Again, feel free to e-mail me in case you want to have a look both at the code for generating PDBs and also to solve instances randomly chosen using them.

Hope this helps,