Backtracking

introduction

Backtracking is a bruteforce appoach that will try the next step and fall back if not success. Backtracking is a systematic way to iterate through all the possible configurations
of a search space. These configurations may represent all possible arrangements of objects (permutations) or all possible ways of building a collection of them
(subsets). Other situations may demand enumerating all spanning trees of a graph, all paths between two vertices, or all possible ways to partition vertices into color
classes.

We will model our combinatorial search solution as a vector a = (a1, a2, …, an), where each element ai is selected from a finite ordered set Si. Such a vector might represent:

  • an arrangement where ai contains the ith element of the permutation. Or,
  • the vector might represent a given subset S, where ai is true if and only if the ith element of the universe is in S.
  • The vector can even represent a sequence of moves in a game or a path in a graph, where ai contains the ith event in the sequence.
bool finished = FALSE; /* found all solutions yet? */
 
backtrack(int a[], int k, data input)
{
  int c[MAXCANDIDATES]; /* candidates for next position */
  int ncandidates; /* next position candidate count */
  int i; /* counter */
 
  if (is_a_solution(a,k,input))
    process_solution(a,k,input);
  else {
    k = k+1;
 
    construct_candidates(a,k,input,c,&ncandidates);
 
    for (i=0; i<ncandidates; i++) {
      a[k] = c[i];
      make_move(a,k,input);
      backtrack(a,k,input);
      unmake_move(a,k,input);
      if (finished) return; /* terminate early */
    }
  }
}
bool Solve(configuration conf)
{
   if (no more choices)     // BASE CASE
         return (conf is goal state);
   for (all available choices) {
      try one choice c;

      ok = Solve(conf with choice c made);   // recursively solve after making choice
      if (ok)
          return true;
      else
          unmake choice c;
  }

  return false;  // tried all choices, no soln found
}

construct candidates(a,k,input,c,ncandidates) – This routine fills an array c with the complete set of possible candidates for the kth position of a, given the contents of the first k − 1 positions. The number of candidates returned in this array is denoted by ncandidates. Again, input may be used to pass auxiliary information.

sample questions

permutations

Counting permutations of {1, … , n} is a necessary prerequisite to generating them.

There are n distinct choices for the value of the first element of a permutation. Once we have fixed a1, there are n − 1 candidates remaining for the second position,
The set of candidates for the kth position will be the set of elements that have not appeared in a yet, Sk = {1, … , n}−a, and a is a solution whenever k = n:

construct_candidates(int a[], int k, int n, int c[], int *ncandidates)
{
  int i; /* counter */
  bool in_perm[NMAX]; /* who is in the permutation? */
 
  for (i=1; i<NMAX; i++) in_perm[i] = FALSE;
  for (i=0; i<k; i++) in_perm[ a[i] ] = TRUE;
  *ncandidates = 0;
 
  for (i=1; i<=n; i++) {
    if (in_perm[i] == FALSE) {
      c[ *ncandidates] = i;
      *ncandidates = *ncandidates + 1;
    }
  }
}
 
process_solution(int a[], int k)
{
  int i; /* counter */
  for (i=1; i<=k; i++) printf(" %d",a[i]);
  printf("\n");
}
 
is_a_solution(int a[], int k, int n)
{
  return (k == n);
}
generate_permutations(int n)
{
  int a[NMAX]; /* solution vector */
  backtrack(a,0,n);
}

If you have no more characters left to rearrange, print current permutation
for (every possible choice among the characters left to rearrange) {
Make a choice and add that character to the permutation so far
Use recursion to rearrange the remaining letters
}

void RecPermute(string soFar, string rest)
{
    if (rest.empty()) {
        cout << soFar << endl;
    } else {
        for (int i = 0; i < rest.length(); i++) {
            string remaining = rest.substr(0, i) + rest.substr(i+1);
            RecPermute(soFar + rest[i], remaining);
        }
    }
}

valid words

string FindWord(string soFar, string rest, Lexicon &lex)
{
  if (rest.empty()) {
    return (lex.containsWord(soFar)? soFar : "");
  } else {
    for (int i = 0; i < rest.length(); i++) {
      string remain = rest.substr(0, i) + rest.substr(i+1);
      string found = FindWord(soFar + rest[i], remain, lex);
      if (!found.empty()) return found;
    }
  }
  return "";   // empty string indicates failure
}

all subsets

How many subsets are there of an n-element set, say the integers {1, … , n}?

Each subset is described by elements that are in it. To construct all 2n subsets, we set up an array/vector of n cells, where the value of ai (true or false) signifies whether the ith item is in the given subset. In the scheme of our general backtrack algorithm, Sk = (true, false) and a is a solution whenever k = n.

is_a_solution(int a[], int k, int n)
{
  return (k == n); /* is k == n? */
}
 
construct_candidates(int a[], int k, int n, int c[], int *ncandidates)
{
  c[0] = TRUE;
  c[1] = FALSE;
  *ncandidates = 2;
}
process_solution(int a[], int k)
{
  int i; /* counter */
  printf("{");
  for (i=1; i<=k; i++)
    if (a[i] == TRUE) printf(" %d",i);
  printf(" }\n");
}
 
generate_subsets(int n)
{
  int a[NMAX]; /* solution vector */
  backtrack(a,0,n);
}

If there are no more elements remaining,
print current subset
else {
Consider the next element of those remaining
Try adding it to the current subset, and use recursion to build subsets from here
Try not adding it to current subset, and use recursion to build subsets from here
}

void RecSubsets(string soFar, string rest)
{
   if (rest.empty())
     cout << soFar << endl;
   else {
     RecSubsets(soFar + rest[0], rest.substr(1)); // include first char
     RecSubsets(soFar, rest.substr(1));           // exclude first char
   }
}

constructing all paths in a grapth from vetex s to vetex t.

The starting point of any path from s to t is always s. Thus, s is the only candidate for the first position and S1 = {s}. The possible candidates for the
second position are the vertices v such that (s, v) is an edge of the graph and v has not been used.

construct_candidates(int a[], int k, int n, int c[], int *ncandidates)
{
    int i; /* counters */
    bool in_sol[NMAX]; /* what’s already in the solution? */
    edgenode *p; /* temporary pointer */
    int last; /* last vertex on current path */
    for (i=1; i<NMAX; i++) in_sol[i] = FALSE;
    for (i=1; i<k; i++) in_sol[ a[i] ] = TRUE;
    if (k==1) { /* always start from vertex 1 */
        c[0] = 1;
        *ncandidates = 1;
    }
    else {
        *ncandidates = 0;
        last = a[k-1];
        p = g.edges[last];
        while (p != NULL) {
            if (!in_sol[ p->y ]) {
                c[*ncandidates] = p->y;
                *ncandidates = *ncandidates + 1;
            }
            p = p->next;
        }
    }
}
 
is_a_solution(int a[], int k, int t)
{
    return (a[k] == t);
}
process_solution(int a[], int k)
{
    solution_count ++; /* count all s to t paths */
}

search pruning

  • By restricting the set of next elements to reflect only moves that are legal from the current partial configuration, we significantly reduce the search complexity.
  • Pruning is the technique of cutting off the search the instant we have established that a partial solution cannot be extended into a full solution.
  • Exploiting symmetry is another avenue for reducing combinatorial searches

8 queens problem

int a[] will stores the column of queeni at which column.

construct_candidates(int a[], int k, int n, int c[], int * ncandidates) {
    int i,  j;/* counters */
    bool legal_move;/* might the move be legal? */
    * ncandidates = 0;
 
    /*loop through all possible columns of queen k */
    for (j = 1; j <= n; j++) {
        legal_move = TRUE;
        for (i = 1; i < k; j++) {   // loop through all signed queens
            if (abs(j - a[i]) == abs(k - i)) /* diagonal threat */
                legal_move = FALSE;
            if (j == a[i])/* column threat */
                legal_move = FALSE;
        }
        if (legal_move == TRUE) {
            c[ * ncandidates] = j; 
            * ncandidates = * ncandidates + 1;
        }
    }
}
 
process_solution(int a[], int k)
{
  int i; /* counter */
  solution_count ++;
}
is_a_solution(int a[], int k, int n)
{
  return (k == n);
}
 
nqueens(int n)
{
  int a[NMAX]; /* solution vector */
  solution_count = 0;
  backtrack(a,0,n);
  printf("n=%d solution_count=%d\n",n,solution_count);
}

Start in the leftmost columm
If all queens are placed, return true
for (every possible choice among the rows in this column)
if the queen can be placed safely there,
make that choice and then recursively try to place the rest of the queens
if recursion successful, return true
if !successful, remove queen and try another row in this column
if all rows have been tried and nothing worked, return false to trigger backtracking

bool Solve(Grid<bool> &board, int col)
{
  if (col >= board.numCols()) return true; // base case
 
  for (int rowToTry = 0; rowToTry < board.numRows(); rowToTry++)  {
     if (IsSafe(board, rowToTry, col)) {
        PlaceQueen(board, rowToTry, col);     // try queen here
        if (Solve(board, col + 1)) return true;    // recur to place rest
        RemoveQueen(board, rowToTry, col);     // failed, remove, try again
    }
}
return false;
}

sudoku

Sudoku consists of a 9×9 grid filled with blanks and the digits 1 to 9. The puzzle is completed when every row, column, and sector

The candidates for open squares (i, j) are exactly the integers from 1 to 9 that have not yet appeared in row i, column j, or the 3 × 3 sector
containing (i, j). We backtrack as soon as we are out of candidates for a square.

The solution vector a supported by backtrack only accepts a single integer per position. This is enough to store contents of a board square (1-9) but not the
coordinates of the board square. Thus, we keep a separate array of Point that encapsulate the two dimension array.

#define DIMENSION 9 /* 9*9 board */
#define NCELLS DIMENSION*DIMENSION /* 81 cells in a 9*9 problem */
typedef struct {
  int x, y;  /* x and y coordinates of point */
} point;
 
typedef struct {
  int m[DIMENSION+1][DIMENSION+1]; /* matrix of board contents */
  int freecount; /* how many open squares remain? */
  point move[NCELLS+1]; /* which cell is k mapped to ? or how did we fill the squares? */
} boardtype;

Constructing the candidates for the next solution position involves first decide which point maps to k, i.e picking the open square we want to fill next (next square), and then identifying which
numbers are candidates to fill that square (possible values).

construct_candidates(int a[], int k, boardtype *board, int c[],
int *ncandidates)
{
    int x,y; /* position of next move */
    int i; /* counter */
    bool possible[DIMENSION+1]; /* what is possible for the square */
 
    next_square(&x,&y,board); /* which square should we fill next? */
 
    board->move[k].x = x; /* store our choice of next position */
    board->move[k].y = y;
 
    *ncandidates = 0;
    if ((x<0) && (y>0)) return; /* error condition, no moves possible */
 
    possible_values(x,y,board,possible);
 
    for (i=0; i <=DIMENSION; i++)
    if (possible[i] == TRUE) {
        c[*ncandidates] = i;
        *ncandidates = *ncandidates + 1;
    }
}
 
make_move(int a[], int k, boardtype *board)
{
  fill_square(board->move[k].x,board->move[k].y,a[k],board);
}
unmake_move(int a[], int k, boardtype *board)
{
  free_square(board->move[k].x,board->move[k].y,board);
}
 
is_a_solution(int a[], int k, boardtype *board)
{
  if (board->freecount == 0)
    return (TRUE);
  else
    return(FALSE);
}

We print the configuration and turn off the backtrack search by setting off the global finished flag on finding a solution. This can be done without consequence because “official” Sudoku puzzles are only allowed to have one solution. There can be an enormous number of solutions to nonofficial Sudoku puzzles.

process_solution(int a[], int k, boardtype *board)
{
  print_board(board);
  finished = TRUE;
}

http://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf

In pseudocode, our strategy is:

Find row, col of an unassigned cell
If there is none, return true

For digits from 1 to 9
if there is no conflict for digit at row,col
assign digit to row,col and recursively try fill in rest of grid
if recursion successful, return true
if !successful, remove digit and try another
if all digits have been tried and nothing worked, return false to trigger backtracking

bool SolveSudoku(Grid<int>&grid) {
    int row, col;
    if (!FindUnassignedLocation(grid, row, col)) return true;  // success!
 
    for (int num = 1;    num <= 9;    num++) {   // consider digits 1 to 9        
        if (NoConflicts(grid, row, col, num)) {  // if looks promising, 
            grid(row, col) = num;   // make tentative assignment
            if (SolveSudoku(grid)) return true; // recur, if success, yay! 
            grid(row, col) = UNASSIGNED;  // failure, unmake & try again;
        }
        // this triggers backtracking;
    }
    return false;
}
bool FindUnassignedLocation(Grid<int>&grid, int &row, int &col) {
  for (row = 0; row < grid.numRows(); row++)
    for (col = 0; col < grid.numCols(); col++)
       if (grid(row, col) == UNASSIGNED) return true;
  return false;
}
 
bool NoConflicts(Grid<int>&grid, int row, int col, int num) {
    return !UsedInRow(grid, row, num) && !UsedInCol(grid, col, num)
    && !UsedInBox(grid, row - row%3, col - col%3, num);
}
 
bool UsedInRow(Grid<int>&grid, int row, int num) {
    for (int col = 0; col < grid.numCols(); col++)
          if (grid(row, col) == num) return true;
    return false;
}
 
bool UsedInCol(Grid<int>&grid, int col, int num) {
    for (int row = 0; row < grid.numRows(); row++)
        if (grid(row, col) == num) return true;
    return false;
}
 
bool UsedInBox(Grid<int>&grid, int boxStartRow, int boxStartCol, int num) {
    for (int row = 0; row < 3; row++)
       for (int col = 0; col < 3; col++)
          if (grid(row+boxStartRow, col+boxStartCol) == num)
              return true;
    return false;
}

numbers

typedef struct {
  int src[N] /* numbers  array*/
  int weight = 0;
  int last_index = 0;
  int expected_weight = W;
} data;
 
construct_candidates(int a[], int k, data* input, int c[], int *ncandidates)
{
  int i; /* counter */
 
   if (input->last_index >= n )  {
     finished = TRUE;
     return;
 
  *ncandidates = 0;
 
  for (i= input->last_index; i<n; i++) {
      c[ *ncandidates] = input->src[i];
      *ncandidates = *ncandidates + 1;
    }
  }
 
  input->last_index = input->last_index + 1;
}
 
process_solution(int a[], int k, data *input)
{
  int i; /* counter */
  if (input->weight == input->expected_weight) {
    for (i=1; i<=k; i++) printf(" %d", a[i]);
    printf("\n");
 }
}
 
is_a_solution(int a[], int k, int n, data* input)
{
  return (input->weight >= input->expected_weight);
}
 
make_move(int a[], int k, data *input)
{
   input->weight = input->weight + a[k];
}
 
unmake_move(int a[], int k, boardtype *board)
{
  input->weight = input->weight - a[k];
}
 
generate_solution(int n)
{  
  backtrack(a,0,input);
}

boggle

http://www.kandysoftwareinc.com/tech-articles/boggle

Add a New Comment
or Sign in as Wikidot user
(will not be published)
- +
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License