Fast Brute Force Solutions by Undoing

A long time ago I learned an interesting way to implement programs that need to enumerate all possible states of a game board in order to find a brute force solution. It runs fast and uses very little memory.

I picked it up from Korf's A* solution to sliding tile puzzles. The basic idea is that you make a change to the state of the board, check if the board is a valid solution, and then recurse on to the next position. Once the recursion has finished, you undo the change you had made to the board, and try another option.

Here is the relevant portion of his solution:

search (int blank, int oldblank,int  g,int  h)
{
  int index;                                    /* index into operator array */
  int newblank;                               /* blank position in new state */
  int tile;                                              /* tile being moved */
  int newh;                             /* heuristic evaluation of new state */

  for (index = 0; index < oprs[blank].num; index++)     /* for each appl opr */
    if ((newblank = oprs[blank].pos[index]) != oldblank) /*not inv last move */
      {tile = s[newblank];            /* tile moved is in new blank position */
       newh = h + increment[tile][newblank][blank];     /* new heuristic est */
       generated++;                                 /* count nodes generated */
       if (newh+g+1 <= thresh)                    /* less than search cutoff */
         {s[blank] = tile;                               /* make actual move */
          s[newblank] = 0;
          if ((newh == 0) ||                     /* goal state is reached or */
              (search(newblank, blank, g+1, newh)))       /* search succeeds */
            return (1);                                 /* exit with success */
          s[newblank] = tile;
          s[blank] = 0;}}       /* undo current move before doing next */
  return (0);
}

Notice how he undoes his change before trying the next change (on the line right before the final return statement.

Consider, for example, a sudoku board. It is a 9x9 grid with 9 different values possible in each tile. In order to use this technique, we'll only need memory space for the 81 piece board, and we only recurse only 81 times, meaning the stack usage will be minimal.

Here is what the important part of a sudoku solver using this technique looks like:

char* board;
#define width 9

bool search(int start_i, int start_j)
{
  // Search to the right and down from our start position for a spot that
  hasn't been written to yet
  for( int i = start_i; i < width; i++ ) {
    for( int j = start_j; j < width; j++ ) {

      // Skip positions that are already written
      if( board[i*width+j] != 0 )
        continue;

      // Try all possible values in this position
      for( int k = 1; k < width+1; k++ ) {
        board[i*width+j] = k;

        if( !verify( i, j ) )
          continue;

        if( search(i,j) )
            return 1;
      }

      // Undo our move
      board[i*width+j] = 0;
      return 0;
    }

    start_j = 0;
  }

  return 1;
}

In a benchmark, this is able to verify 25 million different boards per second, being limited by the speed of the verification. It is only appropriate for a certain subset of problems, but I thought it was a neat trick.

Steven Jewel Blog

Fast Brute Force Solutions by Undoing