Earth Hour

Friday, November 27, 2009

Using BFS to solve the minimum number moves problems

Often in various programming contests we find problems related to calculating minimum moves for some toy problems like "8-puzzle problem", where the step cost to move a block from 1 location to other is constant for every move (or analogous). Generally such problems can be tackled by BFS (it means Breadth First Search, for my friends who didn't know earlier) technique. Well, the concept is pretty simple for BFS. it refers to traversing a tree level wise, i.e. first level 0, then level 1, then 2, 3...
/ \
2 3
/ \ / \
4 5 6 7
For a tree like the above, a BFS traversal guarantees the traversal order: 1->2->3->4->5->6->7
Though in a linked implementation of a tree, the BFS traversal is a bit trickier but for an array representation this is nothing but a straight traversal of the array sequentially.
Since in most of the programming problems, generally the tree is not known at the beginning, therefore the limit of the total number of nodes is uncertain. But, theres nothing to worry much, for the ArrayList in Java and vector classe in C++ are the way out. Well a generalized BFS traversal may look something like this, when the code to remove the repeated states is added to the main BFS logic:
(Note: its just a pseudo code)

fringe= a queue
closed= a set containing visited nodes
while( ! fringe.empty())
node n=fringe.pop();
return solution(n);
//add all children of n to fringe

Based on this below is my C++ implementation for finding out the minimum move sequence to solve the 8-puzzle problem. In this problem given a 3*3 matrix with numbers 1..8 filled in random 8 places among 9 in the matrix with 1 block empty. Our goal is to slide a block at a time in the empty place and finally arrange the puzzle back to sorted order, just like this
1 2 3
4 5 6
7 8 0
(Note: 0 indicates the empty block)

Here is my complete C++ implementation

No comments:

Post a Comment

You can drop me a message here. I will try to get back to you as soon as possible