Implementing BFS for Pattern Database

Introduction

This is basically the tutorial on the heuristic “Pattern Database” for N-Puzzle mentioned over here, as I have mentioned in the tutorial, pattern database is the database of all the possible permutations of a particular group of tiles and the minimum moves required from that pattern to reach the goal state for that group.

---

Prerequisites

• The basic knowledge of BFS algorithm is required which can be found in my earlier tutorial here.
• Knowledge about reading and writing to binary files/text files is required. This is to save the pattern database into files.

Working

Let’s work on this in the order of the previous article. So first of all we need to decide what all information is needed to be kept in the node.

• We need to save the puzzle state at that instance, thus a NxN grid.
• We need to store the heuristic value h.
• We may store the row and column of the blank space to speed up the process, however it’s not required.

Structure of a Node

Structure Node
{
              variable array grid[N][N] , variable h;
}

Partitioning

We need do define our partitioning as explained in the post initially mentioned. For explaining purposes we’ll use a 15-Puzzle with a 6-6-3 partitioning. The exact partitioning is shown below.

As we can see the 15-Puzzle is partitioned into two blocks consisting of 6 tiles each and 1 block consisting of 3 tiles, hence we need to create 3 files consisting the cost values of the 3 partitions respectively.We have already discussed the merits of 6-6-3 partitioning over others.

Breadth-First Search

Now let’s see how to use BFS on the Patterns to create the database, out of the 3 let’s take the following group

As you already know that the cost is calculated without considering the interference of tiles of other groups, we take all the other tiles as ‘-1’.
We now have to apply BFS to the blank tile. The progress is as follows:

We see that in all the cases above, the blank tile exchanges it’s position with ‘-1’ which is nothing but some random tile from the other group hence when the new state is saved, if it is formed after the exchange of blank space with ‘-1’ we do not add +1 to the cost of reaching the new state, cost is incremented only when the blank space exchanges it’s position with a tile of that group only.

Let’s consider the last leftmost state found above and continue further

Here we see the increment in cost as the blank tile exchanges it’s position with tiles in the group.
Note: BFS is applied on the blank tile for each group/pattern. We do not apply BFS to any tile other than the blank tile.

Making the database and the queue

The state can be saved in the database and queue in many forms
For example it can be saved by saving the co-ordinates of each number in that group in the same order into a 12 digit number(for pattern consisting of 6 tiles)

For the following state

the 12 digit number comes out to be : 112122313241 since all the tiles are in their destination position we get this, let’s take another example where the positions of tile ‘9’ and tile ’10’ are swapped, we would acquire the following number: 112122323141.
Thus this is one method of saving the state , its up to the programmer to use whatever he feels comfortable with to save the state.

Note: While creating the database we DO NOT save the position of the blank tile/ consider the blank tile, however while inserting into the “queue” or the “closed_list” we save the state with the position of the blank tile/considering the blank tile. While copying the entries from the “closed_list” to the database we take the least value of cost of a particular pattern from all the similar patterns with different position of space.
For example, let’s consider these similar patterns in the entire “closed_list”.

As you can see the patterns consisting of the tiles in the group is same, only the position of blank space is at different position, thus while inserting into the database we take the least value i.e 1, this ensures the admissibility of the heuristic while reducing the size of the final database.

We do this to save memory as mapping the blank tile in the database will create
16!/(16-7)!=57657600 database entries , whereas not mapping the blank tile will give us 16!/(16-6)!=5765760 database entries.

Here is the summary of the database creation.

• We can use various methods to save the state of a pattern in the group. For eg, saving the row and column value of each tile in the group in order.
• Blank tile is mapped and stored in the “BFS queue” and the “closed list” to check for duplicate states and performing BFS.
• Blank tile is not mapped while storing the values in the database, instead, the least cost out of all blank space locations for each pattern is stored in the database.
• The database is in the form of a table with each pattern value and it’s BFS cost.
• Since BFS is executed from the goal state, the cost of each pattern will be the one when the pattern occurred first in the BFS process all the duplicate patterns occurring in the later phase of the BFS are removed/not stored.

This process is performed on all the pattern groups and different database files are formed for each group.

Usage

We now know how to create the database, but how do we use this information to solve the N-Puzzle?
Well the “cost” that we have saved for each pattern is combined/added and that is the heuristic cost while applying IDA* or A*. At each cycle of the algorithm when we create next nodes in the graph, the cost for each node/Puzzle state is calculated by finding the cost of each group with the help of the database and combining it to get the heuristic value of that state.That’s it!
This is one of the heuristics that solves N-Puzzle the fastest.

---

Make sure you read the Breadth-First Search tutorial to get the general understanding of how BFS works and read the A* for N-Puzzle where I have explained N-Puzzle and different heuristics in detail. Make sure you try to code pattern database heuristic to solve N-Puzzle for a better and practical understanding.

---

If you see anything wrong with the post or if you have any queries regarding the algorithm. Post them in the comment section. There can be things wrong with this as I am still a beginner on the path of learning and this is based on what I have learnt so far with examples from external sources as well. So experts, please let me know through the comments section.