Anurag Sharma Sun Campus Ambassador, KIIT-University

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...
Eg.
     1
   /   \
  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
fringe.push(root_node_of_tree);
while( ! fringe.empty())
{
    node n=fringe.pop();
    if(goalTest(n)){
       return solution(n);
    }
    if(!closed.contains(n)){
        closed.add(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 goes my C/C++ implementation: 

Here is the final code to download

Posted at 11:03AM Nov 28, 2009 by Anurag Sharma in Personal  |  Comments[4]