Searchy type problems

A lot of problems in the ACM and TopCoder competitions can be solved using a general search technique like breadth-first search (BFS). Many BFS type problems are represented with an initial grid and you want to determine whether you can achieve a certain state or grid configuration, possibly in the minimum number of moves. These problems are very popular and can vary in complexity, however, the general problem solving principles remain the same.

You can usually determine whether BFS is the right approach for a problem of this sort by first checking the bounds of the grid. Most of the time, the grid will be less than 20×20. Secondly, you need to determine how to represent the current state of the problem. You can think of this state as a node in a graph. Finally, you need to determine if one state can be transformed into a subsequent and valid state through a move with a cost of one. You can think of these moves as edges between your nodes. Another hint is that many of these problems can be classified as single player game problems.

Let’s consider an example. In the problem Traffic!, a simple game is described where are given an initial puzzle configuration consisting of blocks of varying sizes. The goal of the game is to figure out how to remove the white piece by moving the various puzzle pieces and repositioning the white piece so that it slides through the opening in the puzzle. In the problem you are asked to find the minimum number of moves to accomplish this task.

So, let’s go back to our criteria for determining whether BFS is a valid approach. First, the grid is of size 6×6, so that’s well within our heuristic 20×20 bound. Second, the state of the problem can be represented as a list of the current locations for each puzzle piece. A move in the game consists of moving a single puzzle piece any number of open positions horizontally or vertically. Horizontal pieces can only move horizontally and vertical pieces can only move vertically. Sliding a horizontal piece one spot to the right has the same cost as moving it two spots to the right, that is, it counts as one single move. Thus, we can transition from one state of the board to another with a cost of one. Finally, the problem even fits the format of being described as a single player game.

Once we’ve established that we can solve the problem using BFS, then the algorithm to actually solve the problem is quite straight-forward. A generic approach could be something similar to the following code:

int solve(State start) {
  set<State> visited;
  queue<State> q;

  q.push(start);

  while(!q.empty()) {
    State s = q.top(); q.pop();
    // skip states we've already processed
    if(visited.find(s) != visited.end()) continue;

    // we reached our goal, return moves
    if(goalStateReached(s)) return s.moves;

    // visit the state
    visited.insert(s);

    // try all valid moves 
    // and add them to our queue
    enqueueValidMoves(q, s);
  }
  // never reached the goal
  return -1;
}

In this case, State is going to consist of a list of the current block locations, the number of moves it took to achieve this state, and a less than operator for storing the state properly within our visited set. The enqueueValidMoves will loop over the positions in our state object and create a new state for any valid vertical and horizontal moves. We know we reached the goal state when the white piece is located in column 6.

There are a few simple tips for working on problems of this type or grid representations in general. First, let’s consider a simple 0/1 matrix where from any cell i,j, containing a one, you can move east, west, north or south provided the move takes you to a cell containing a one:

110
010
111

So, the cell 0,0 can only move to cell 0,1 as this is its only neighbor containing a one. We could potentially perform a BFS where we check for valid moves as follows:

while(!q.empty()) {
  // queue consists of pairs of integers 
  // representing cell locations
  pair<int, int> p = q.top(); q.pop();

  if(visited[p]) continue;

  // process potential moves
  if(p.first-1 >= 0 && grid[p.first-1][p.second] == 1)  
    // enqueue item
  if(p.first+1 < rowCount && grid[p.first+1][p.second] == 1) 
   // enqueue item
  if(p.second-1 >= 0 && grid[p.first][p.second-1] == 1) 
   // enqueue item
  if(p.second+1 < colCount && grid[p.first][p.second+1] == 1) 
   // enqueue item
}

That will work, but all the bounds checking and if statements are kind of ugly and error prone.

To clean up this code a bit, one simple trick is to remove bound checks by padding the grid with empty cells. For example, our grid from above would become:

00000
01100
00100
01110
00000

Now, our check just needs to verify whether a given cell contains a value of one.

Another simple tip when processing moves over a grid, like north, south, east and west transitions is to store these moves as x, y and possibly z deltas in an array. Thus, with those two simple tricks combined, our messy code above becomes:

int x[] = {1, 0, -1, 0};
int y[] = {0, 1, 0, -1};
while(!q.empty()) {
  // queue consists of pairs of integers representing cell locations
  pair p = q.top(); q.pop();

 if(visited[p]) continue;

 // process potential moves
 for(int i = 0; i < 4; i++) {
   int r = p.first+x[i];
   int c = p.second+y[i];
   if(grid[r][c] == 1) // enqueue move
 }
}

It seems like a pretty simple change, and I’m sure some will think it’s not worth it, especially for this simple example where there’s only four possible move directions, but once you start allowing moves along the diagonal you are up to having 8 if statements to write. The more code you have to write, especially with only slight modifications like adding one here and subtracting one there, the more probable it is that you will make a mistake that will cost you debugging time.

Other problems of this type:
439 – Knight Moves
841 – Snake
589 – Pushing Boxes
10793 – The Orc Attack