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:
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 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):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 ...
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
What links here?
Up one Level