Backtracking

From Chessprogramming wiki
Jump to: navigation, search

Home * Programming * Algorithms * Backtracking

Eight queens puzzle [1]

Backtracking,
a general search algorithm for finding solutions of certain computational problems. It incrementally builds candidates to a solution, and "backtracks" a partial candidate as soon as it determines it cannot become member of the solution. Therefor backtracking algorithms, most often implemented as recursive depth-first algorithm, are not considered brute-force, and have the advantage of potentially requiring a search tree with less nodes.

History

Bitner and Reingold [2] credit Derrick H. Lehmer with first using the term 'backtrack' in the 1950s, but it has been discovered and rediscovered many times. Robert J. Walker [3] was the first who called using a well-known depth-first procedure Backtracking in 1960.

Applications

Classic examples of using backtracking algorithms are solving Exact cover problems and Tour puzzles, like the Eight queens puzzle, the Knight's tour puzzle and other Maze or Labyrinth puzzles. Knuth's Algorithm X along with Dancing Links finds all solutions to an exact cover problem. Backtracking is further applied to solving Constraint satisfaction problems, such as Crossword puzzles, Sudoku, Pentomino tiling, boolean satisfiability problems and other NP-complete problems. Logic programming languages such as Prolog internally use backtracking to generate answers.

De Bruijn Sequences

A further sample is to find De Bruijn sequences, as demonstrated by the recursive De Bruijn Sequence Generator. Here early partial candidates may be discarded if the lock indicates a new six-bit number already occured before.

Looking for Magics

Unfortunately, looking for magics to find factors for the application of Magic Bitboards, seems not to fit into a class of these kind of problems. Here trial and error with spare populated, but otherwise randomly chosen numbers is used.

8Q in Bitboards

"Thinking" Bitboards, Gerd Isenberg made following Eight queens [4] [5] proposal, to traverse ranks as disjoint candidate sets for one queen each, with premature elimination of redundant tests [6] of squares already attacked by queens put on the board . Therefor, while serializing the set of not attacked candidate squares from one rank to put a queen on it, it maintains a "taboo" union set for consequent queens on upper ranks by "oring" queen attacks in north directions. It performs some optimization to keep the processed rank always the first, to only use a lookup array of queen attacks of that first rank, and to shift the taboo-set consecutively one rank down. A little space-time tradeoff saves the bitscan at the cost of some more memory to index the eight attacks from an sparse array of 129 bitboards with the single isolated bit inside one byte (the first rank).

Code

The sample C code demonstrates an iterative solution using arrays as explicit stacks on the stack: 

typedef unsigned char U8;

/**
 * eightQueen Bitboard implementation
 * @author Gerd Isenberg
 * @date April 29, 2011
 */
void eightQueenBitboard( /*U64 taboo */ ) {
   U64 t[8];             /* stack of taboo bitboards */
   U8  q[8], c[8];       /* stack of queens and candidate squares */
   unsigned int p = 0;   /* ply, queen index 0..7 as "stack pointer" */
   t[0] = 0;             /* no square attacked so far (taboo) */

C: c[p] = ~(U8)t[p];     /* 1. rank squares not attacked */
   while ( c[p] ) {      /* while candidate squares */
      q[p] = c[p]&-c[p]; /* LS1B -> 1,2,4,8,16,32,64,128 */
      if ( p == 7 ) {
         print8Q( q );   /* solution found */
      } else {           /* "or" attacks to taboo, shift it  */
         t[p+1] = (t[p] | nAtt[q[p]]) >> 8; /* one rank down */
         ++p; goto C;    /* make "recursive call" iterative  */
R:       p--;
      }
      c[p] ^= q[p];      /* reset candidate square */
   }
   if ( p ) goto R;      /* return from iterative "call" */
}

Node Counts

The algorithm backtracks all 92 distinct Eight queen solutions. Using an if do-while else construct instead of while control structure allows counting "pruned" nodes, where the candidate set is initially empty in the else case, leaving following node statistics differentiated by ply (excluding the root):

Ply Nodes Pruned Sum
0 8 0 8
1 42 0 42
2 140 0 140
3 344 0 344
4 568 18 586
5 550 150 700
6 312 256 568
7 92 220 312
Sum 2056 644 2700

Data and Print

The declaration of the north attack array to save a byte-wise bitscan, and for convenience the print routine used: 

/**
 * north | nw | ne attacks of a queen on the 1. rank
 *
 * indexed by a first rank - bitboard
 * with one bit set, representing the file
 * 1,2,4,8,16,32,64,128
 */
static const U64 nAtt[130] = {
   0,
   C64(0x8141211109050300), /*   1 */
   C64(0x02824222120A0700), /*   2 */
   0,
   C64(0x0404844424150E00), /*   4 */
   0,0,0,
   C64(0x08080888492A1C00), /*   8 */
   0,0,0,0,0,0,0,
   C64(0x1010101192543800), /*  16 */
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   C64(0x2020212224A87000), /*  32 */
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   C64(0x404142444850E000), /*  64 */
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   C64(0x8182848890A0C000), /* 128 */
   0
};

/**
 * printing 8q boards
 */
void print8Q( unsigned char q8[] ) {
   static int count=1;
   int r, f, b;
   printf("NQ %d\n", count++ );
   for (r=7; r >= 0; --r) { /* 8th rank top */
      for ( f=0, b=1; f < 8; ++f, b <<= 1) {
         printf("%c ", (q8[r] & b) ? 'Q' : '.');
      }
      printf("\n");
   }
   printf("\n");
}

N Queens

By Marcel van Kervinck

A very short and therefor slightly obfuscated, but elegant and tricky general backtracker in enumerating N Queen solutions is given by Marcel van Kervinck in two lines of C code, Version 2, 1996 [7], Bit-Twiddling as its best: 

t(a,b,c){int d=0,e=a&~b&~c,f=1;if(a)for(f=0;e-=d,d=e&-e;f+=t(a-d,(b+d)*2,(
c+d)/2));return f;}main(q){scanf("%d",&q);printf("%d\n",t(~(~0<<q),0,0));}

By Tony Lezard

As mentioned by Marcel van Kervinck, a similar 8 Queen program was introduced by Tony Lezard in 1991 [8]: 

static int count = 0;

void try(int row, int left, int right) {
   int poss, place;
   if (row == 0xFF) ++count;
   else {
      poss = ~(row|left|right) & 0xFF;
      while (poss != 0) {
         place = poss & -poss;
         try(row|place, (left|place)<<1, (right|place)>>1);
         poss &= ~place;
      }
   }
}

void main() {   
   try(0,0,0);
   printf("There are %d solutions.\n", count);
}

See also

Publications

1960 ...

Chapter 16: The Eight Queens and Other Chessboard Diversions.

1970 ...

1980 ...

1990 ...

2000 ...

2010 ...

Chapter 16: The Eight Queens and Other Chessboard Diversions.

Forum Posts

External Links

References

  1. ↑ Visual Example of the Eight Queens backtrack Algorithm, Wikimedia Commons, Eight queens puzzle from Wikipedia
  2. ↑ James R. Bitner, Edward M. Reingold (1975). Backtrack Programming Techniques. Communications of the ACM, Vol. 18, No. 11
  3. ↑ Robert J. Walker (1960). An Enumerative Technique for a Class of Combinatorial Problems. Proceedings of Symposia in Applied Mathematics, Vol. X, Combinatorial Analysis, Richard E. Bellman and Marshall Hall, Jr., eds., American Mathematical Society, Providence, Rhode Island, pp. 91-94
  4. ↑ Onur Demirörs, N. Rafraf, M.M. Tanik (1992). Obtaining n-queens solutions from magic squares and constructing magic squares from n-queens solutions. Journal of Recreational Mathematics, Vol. 24
  5. ↑ Magic square from Wikipedia
  6. ↑ John Gaschnig (1977). A General Backtrack Algorithm That Eliminates Most Redundant Tests. IJCAI 1977
  7. ↑ Queens ~ /etc/marcelk
  8. ↑ 8 Queens (NO *SPOILER*) by Tony Lezard, rec.puzzles, November 18, 1991
  9. ↑ The 70*70 Square Puzzle by Thomas Wolf
  10. ↑ Re: Perft(15) estimate after averaging 800 MC samples by Daniel Shawul, CCC, November 21, 2013 » Perft
  11. ↑ Branch and bound - Wikipedia
  12. ↑ WalkSAT from WIkipedia
  13. ↑ Hamiltonian path problem from Wikipedia

Up one Level

Retrieved from "https://www.chessprogramming.org/index.php?title=Backtracking&oldid=25225"