
%\noindent \textbf{Backtracking}
\subsection{Backtracking}

Backtracking allows you to try all the possible configurations
of a problem to find a solution using global data structures.  General idea:

\lstset{language=C++}
\begin{lstlisting}
BT (state s) {
  if (s is the goal state) { 
      // process
  }
  if (goal state is unreachable from s)
     return

  foreach value v for state s {
     mark (s, v)
     BT (next-state)
     unmark (s, v)
  }
}
\end{lstlisting}
\normalsize

\noindent \texttt{mark}/\texttt{unmark} adjust the global data
structure to account for \texttt{s1}.  
For a problem like solving sudoku, the global data structure
would the playing grid.  A state would a row and column number for
a particular cell and the possible values that cell could take.  
Expanding the state tries each possible cell value.  mark would
adjust the playing grid so that all other cells in the row, column
and region cannot use the value \texttt{v} anymore.  unmark 
undoes the adjustments of mark.

For placing $n$ queens on a $n x n$ chessboard:
\small
\begin{lstlisting}
#include <cstdio>

const int N = 8;
 // row r's queen is in columm col[r]
int col[N],
    s = 0; // solution number

#define FOR(i,n) for(int i = 0; i < n; ++i)

bool safe(int x, int r) {
  FOR(z,r) {
   int i = z + 1;
   int c = col[r - i];
   if (c == x - i || c == x
     || c == x + i) return false;
   }
   return true;
}

void find(int r) {
 FOR(x,N) {
  if (safe(col[r] = x, r))
   if (r+1 < N) find(r+1);
   else putboard();
 }
}
int main() {
 find(0);
 return 0;
}

\end{lstlisting}

\newpage
\subsection{Sudoku with bitsets}
\begin{lstlisting}
#include <queue>
#include <set>
#include <cassert>
#include "prelude.cpp"

using namespace std;

ifstream in("sudoku.in");

typedef bitset<9> cell;
typedef pair<int,int> pos;
typedef int val;
typedef map<pos,cell> aBoard;
queue<pos> q; // positions with exactly one value
// possible values the cell could be
vector<int> values(cell c) {
  vector<int> v;
  FOR(i,c.size())
    if(c.test(i) != 0) v.push_back(i+1);
  return v;
}

int valueof(cell c) { return values(c)[0]; }
string str(cell c) {
  return "[" + str(values(c)) + "]"; }

// set "0" positions to be any number,
// and add known values to the queue
aBoard parseBoard() {
  aBoard board;
  string line;
  char num;
  FOR(i,9) {
    getline(in, line);
    stringstream ss(line);
    FOR(j,9) {
      pos ij(i,j);
      ss >> num;
      board[ij].reset(); // all off
      if(num == '0') {
        board[ij].set(); // all on
      } else {
        board[ij].set(num-'1');
        q.push(ij);
      }
    }
  }
  return board;
}

// coords of row, column, and block positions
map<pos, set<pos> > peers;

void init() {
  FOR(i,9) FOR(j,9) {
    pos p(i,j);
    int base_i = i - i%3;
    int base_j = j - j%3;
    FOR(k,9) {
      if(k != i) // add row
        from[p].insert( pos(k,j) );
      if(k != j) // add column
        from[p].insert( pos(i,k) );

      pos block( base_i + k/3,
                 base_j + k%3 );
      if(block != p)
        from[p].insert(block);
    }
  }
}

bool isFinished(aBoard& b) {
  FOREACH(p, b) // p is <pos,cell>
    if(p->second.count() != 1)
      return false;
  return true;
}

void printBoard(aBoard& b) {
  FOR(i,9) {
    FOR(j,9)
      printf("%13s",
        str(b[pos(i,j)]).c_str());
    printf("\n");
  }
}

// returns true if contradiction
bool expand(aBoard& b) {
  while(!q.empty()) {
    pos p = q.front(); q.pop();
    assert(b[p].count() == 1);

    // remove c's bit from each neighbor
    FOREACH(nbr, peers[p]) {
      if(b[*nbr].count() == 1)
        continue;
      b[*nbr] &= ~b[p];
      switch(b[*nbr].count()) {
        case 0: return true;
        case 1: q.push(*nbr);
      }
    }
  }
  return false; // no contradictions!
}

// returns true if we found a solution
bool backtrack(aBoard b) {
  bool failed = expand(b);
  if(failed) return false;
  else if(isFinished(b)) {
    printBoard(b);
    return true;
  } else { // try every value for some cell
    vector<pair<int,pos> > choices;
    FOR(i,9) FOR(j,9) {
      pos ij = pos(i,j);
      int count = b[ij].count();
      if(count <= 1)
        continue;
      choices.push_back(
        make_pair(count, ij));
    } // find cell with smallest # choices
    sort(ALL(choices));
    pos ij = choices[0].second;
    vector<int> poss = values(b[ij]);
    FOREACH(num, poss) {
      b[ij].reset();
      b[ij].set(*num-1);
      q.push(ij);
      if(backtrack(b))
        return true;
    }
  } // should not ever get here...
  return false;
}

int main() {
  init();
  while(in.good()) {
    aBoard b = parseBoard();
    backtrack(b);
    return 0;
  }
}
\end{lstlisting}
\normalsize
%void putboard() {
% printf("\nSolution #%d:"
%        "\n---------------------------------\n", ++s);
% FOR(r,N) {
%  FOR(x,N)
%   printf(x == col[r] ? "| Q " : "|   ");
%   printf("|\n---------------------------------\n");
% }
%}
  
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "../ref-doc"
%%% End: 
