Backtracking is 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 recursivedepth-first algorithm, are not considered brute-force, and have the advantage of potentially requiring a search tree with less nodes.

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.

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 northdirections. 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 isolatedbit inside one byte (the first rank).

typedefunsignedchar 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 */unsignedint 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
*/staticconst 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(unsignedchar q8[]){staticint 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:

Home * Programming * Algorithms * BacktrackingBacktrackingis 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.^{[1]}## Table of Contents

## 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:## Node Counts

The algorithm backtracks all 92 distinct Eight queen solutions. Using anif do-while elseconstruct instead ofwhilecontrol 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):92## Data and Print

The declaration of the north attack array to save a byte-wise bitscan, and for convenience the print routine used:## 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:## By Tony Lezard

As mentioned by Marcel van Kervinck, a similar 8 Queen program was introduced by Tony Lezard in 1991^{[8]}:## See also

## Publications

## 1960 ...

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-941965).Backtrack Programming. Journal of the ACM, Vol. 12, No. 41969, 1991).The Unexpected Hanging and Other Mathematical Diversions. Simon & Schuster, University Of Chicago Press.Chapter 16:

The Eight Queens and Other Chessboard Diversions.## 1970 ...

1971).Elements of Combinatorial Computing. Pergamon Press, amazon.com1975).Backtrack Programming Techniques. Communications of the ACM, Vol. 18, No. 11^{[9]}1974).Estimating efficiency of backtrack programs. STAN-CS-74-442, CS-Department, Stanford University^{[10]}1975).Estimating the Efficiency of Backtrack Programs. Mathemathics of Computation, Vol. 291977).Backtracking in Recursive Computations. Acta Informatica Vol. 8, No. 21977).A General Backtrack Algorithm That Eliminates Most Redundant Tests. IJCAI 19771979).A technique for implementing backtrack algorithms and its application. Information Processing Letters Vol. 8, No. 41979).Backtracking in a Generalized Control Setting. ACM Transactions on Programming Languages and Systems, Vol. 1, No. 1## 1980 ...

1981).Backtracking with Multi-Level Dynamic Search Rearrangement. Acta Informatica Vol. 15, No. 21986).Superlinear Speedup for Parallel Backtracking.Technical Report 30, University of Paderborn1988).The World’s Fastest Scrabble Program. Communications of the ACM, Vol. 31, No. 5, pdf » Scrabble## 1990 ...

1991).Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, ISBN 0201529890, amazon.com1993).Backtracking and Probing. zipped ps1993).Dynamic Backtracking. JAIR Vol. 11993).Hybrid Algorithms for the Constraint Satisfaction Problem. Computational Intelligence, Vol. 9, No. 3, pdf1993).Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the ACM, Vol. 40, No. 3^{[11]}1994).GSAT and Dynamic Backtracking. KR 1994^{[12]}1995).Better Algorithms for Parallel Backtracking. IRREGULAR 1995## 2000 ...

2004).Statistical Regimes Across Constrainedness Regions. CP 2004, pdf2008, 2011).Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting. CPAIOR 2008, Annals of Operations Research, Vol. 184## 2010 ...

2011).New decision rules for exact search in N-Queens. Journal of Global Optimization, Vol. 51, No. 32014).Knots and Borromean Rings, Rep-Tiles, and Eight Queens: Martin Gardner’s Unexpected Hanging. The Mathematical Association of America / Cambridge University PressChapter 16:

The Eight Queens and Other Chessboard Diversions.## Forum Posts

## External Links

## References

1975).Backtrack Programming Techniques. Communications of the ACM, Vol. 18, No. 111960).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-941992).Obtaining n-queens solutions from magic squares and constructing magic squares from n-queens solutions. Journal of Recreational Mathematics, Vol. 241977).A General Backtrack Algorithm That Eliminates Most Redundant Tests. IJCAI 1977## What links here?

Up one Level