# Need a practical solution to build a pattern database for 15-Puzzle



## ashwin (Nov 7, 2012)

I am developing a 15-Puzzle solver. I intend to solve it using *pattern database(specifically 5-5-5 static)* heuristic. To know more about this heuristic see this (page 283 and page 290). This is the code to fill the database with moves this input - 

1  2  3  4
0  6  0  0
0  0  0  0
0  0  0  0
(actually it is 1-d array. But for visualization..)
This is the input that is fed into the function *insertInDB()* for the first time(then successive recursive calls are made)
This is the complete code.

```
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);
    			   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);
    		  
    		  
    		   //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 start value of  *g_n* is zero. The for each move *g_n* is incremented by 1 and then again the recursive function is called. In the function *updateIfNecessary()*, I am checking if this value is already present in the database. If present, I am checking its cost against that of in the database. If it is less, then update the new cost. 
Now the number of values that will go into the database is *16!/(16-5)! = 524160*. But this program has been running since the last 23 hours. And currently the number of entries is *510432*. But the balance 10,000 entries will take ages to complete because now the insert rate has gone very low. Just *1 entry for every 30-60min*. This is because of the generation of the duplicate states.
So, I have stopped the program and am looking for some other solution *with or without recursion*. Can anyone suggest the solution?


----------



## Aquinus (Nov 7, 2012)

You don't want to use a database for this kind of data. The problem is that you're putting your data at a lower tier on the memory hierarchy and takes significantly more time to query a database then to look up a location in memory. You only want to use the database as storage once you have results from your initial set, not as a persistent store for everything that you're doing.

Basically, you're using a database incorrectly. Sorry, can't help you.


----------



## ashwin (Nov 7, 2012)

Aquinus said:


> You don't want to use a database for this kind of data. The problem is that you're putting your data at a lower tier on the memory hierarchy and takes significantly more time to query a database then to look up a location in memory. You only want to use the database as storage once you have results from your initial set, not as a persistent store for everything that you're doing.
> 
> Basically, you're using a database incorrectly. Sorry, can't help you.



its okay if you can't help me. But a *pattern database* heuristic requires a database. The heuristics for the sub-problems are stored in the database once, initially, and then the database can be queried upon to solve the puzzle. So, a database is required. Please see the links that I have given above.


----------



## Aquinus (Nov 7, 2012)

ashwin said:


> its okay if you can't help me. But a *pattern database* heuristic requires a database. The heuristics for the sub-problems are stored in the database once, initially, and then the database can be queried upon to solve the puzzle. So, a database is required. Please see the links that I have given above.



You're not using it for strictly heuristics though, from what I gathered, you're using the database to store the entire state of the puzzle and making a lot of queries takes a lot more time than looking up a variable. It's hard to say what is actually happening without seeing the rest of the code but I think the problem may have been over-simplified.


----------



## ashwin (Nov 7, 2012)

Aquinus said:


> You're not using it for strictly heuristics though, from what I gathered, you're using the database to store the entire state of the puzzle and making a lot of queries takes a lot more time than looking up a variable. It's hard to say what is actually happening without seeing the rest of the code but I think the problem may have been over-simplified.



I am using to for the heuristics. I am storing each *permutation of "1234060000000000"* in the database and finding out the least cost for these permutaions to reach the sub-goal state - *1234060000000000*. I think the recursion is the problem not the database. The problem can be solved in a much simpler way, I think without recursion also.


----------



## Aquinus (Nov 7, 2012)

ashwin said:


> I am storing each *permutation of "1234060000000000"* in the database and finding out the least cost for these permutaions to reach the sub-goal state - *1234060000000000*.



The problem could be the size of your database table. 15! is a huge number if you really are storing every permutation of a set of 15 items. If the number of rows is looking something like "1307674368000 rows" then you have a problem and you're not using the database correctly. I can tell you right now that even on enterprise grade hardware with 15k RPM SAS drives that a table with a few million rows takes a little bit of time to query and update, not to mention that you're storing gigabytes worth of data at this point and every time you run a query, it has to do an index or sequential scan every time you select off of the database and with a table that big you're looking at minutes for every query and you need to execute thousands of queries to do it the way you're suggesting.

I would recommend storing considerably less in the database and keeping the data that you need to quickly search for in the database. I'm assuming that you're using MySQL as the database as well?


----------



## ashwin (Nov 7, 2012)

Aquinus said:


> The problem could be the size of your database table. 15! is a huge number if you really are storing every permutation of a set of 15 items. If the number of rows is looking something like "1307674368000 rows" then you have a problem and you're not using the database correctly. I can tell you right now that even on enterprise grade hardware with 15k RPM SAS drives that a table with a few million rows takes a little bit of time to query and update, not to mention that you're storing gigabytes worth of data at this point and every time you run a query, it has to do an index or sequential scan every time you select off of the database and with a table that big you're looking at minutes for every query and you need to execute thousands of queries to do it the way you're suggesting.
> 
> I would recommend storing considerably less in the database and keeping the data that you need to quickly search for in the database. I'm assuming that you're using MySQL as the database as well?


I am not storing 15! rows. I am only storing *16!(16-5)!=524160* Please read the question fully.


----------



## Fourstaff (Nov 7, 2012)

You can setup a stochastic search algorithm, where it doesn't go through all the possible moves but tries to obtain the ideal as fast as possible. (eg every move should bring 1 closer to its supposed place, etc). 

Also, consider permutating the current state to a state "solved earlier", that will obviously get you and answer but its not always the minimum number of moves. Problem with heuristics is always the algo, you will need to massively increase the complexity for relatively small amount of gain.


----------



## ashwin (Nov 7, 2012)

Fourstaff said:


> You can setup a stochastic search algorithm, where it doesn't go through all the possible moves but tries to obtain the ideal as fast as possible. (eg every move should bring 1 closer to its supposed place, etc).
> 
> Also, consider permutating the current state to a state "solved earlier", that will obviously get you and answer but its not always the minimum number of moves. Problem with heuristics is always the algo, you will need to massively increase the complexity for relatively small amount of gain.


Thanks for replying. But, I did not quite understand your comment. I just want to ensure that we are both on the same track. So..the above code is to actually calculate the heuristic, which will then be used to solve the 15 puzzle problem. I am not able to compute the heuristic itself. The recursion is a very exaggerated solution. I think a simpler solution exists. maybe loops?


----------

