Breadth First Search

Many programming problems can be modeled as search problems. Given an initial state find the set of intermediate states that have to be traversed before reaching a goal state. We could formulate the Water Buckets problem, the BrainVita problem or the Sudoku solver as search problems. Here we introduced the Knights problem. But instead of using depth first we’ll use breadth first.The Knights problem may be stated as:

Given two positions, source and destination, on a blank chess board, list the sequence of legal moves a knight would have to take to move from source to destination.

In this problem we are interested to find the smallest set of moves a knight would have to make. Hence we search the solution space which is a tree with multiple descendants at every node by traversing the tree by collecting the successor nodes at every level and generating successors to each of those. Hence we don’t investigate a node until all the nodes at previous level have been investigated.

Listed below is a somewhat generic C++ code that does the breadth first. (See github for the full source)

 int Compute(
KState const& startState,
KState const& endState,
KState* seen)
{
  int curMax=0;
  if (startState == endState)
    return curMax;

  std::deque<KState> tobeseen;
  tobeseen.push_back(startState);
  while (1)
  {
    KState pos=tobeseen.front();
    tobeseen.pop_front();
    seen[curMax]= pos;
    std::vector<KState> nextpositions = ValidMoves(pos);
    if(nextpositions.end() !=
    std::find(nextpositions.begin(),nextpositions.end(),endState))
    {
    //found
    break;
    }
    for (auto& it : nextpositions)
    {
    if (std::find(seen, seen + curMax, pos) == seen + curMax &&
      std::find(tobeseen.begin(), tobeseen.end(), it) == tobeseen.end())
    {
      it.Parent = curMax;
      tobeseen.push_back(it);
    }
    }
    ++curMax;
  }
  return curMax;
} 

The input consists of the start state and the goal state (referred to as end State); ‘seen’ is an array of all intermediate states. The function returns an index to the penultimate state listed in ‘seen’. All the predecessor states can be accessed by traversing ‘seen’. For a given ‘k’, ‘seen[k].Parent’ is the index to the predecessor of state pointed to by ‘k.’ Going through the code we see that the function maintains a ‘tobeseen’ collection. ValidMoves returns the set of all possible states that can be reached from a given state. The function traverses through the ‘tobeseen’ collection until it finds the end state.

This function is generic in that we merely need to define KState, ValidMoves and equality of states to repurpose the solution to another breadth first problem.

Advertisements

About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.
This entry was posted in Algorithm, C++, Software Puzzle and tagged . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s