Backtracking
Home * Programming * Algorithms * Backtracking
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.
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:
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
- Brute-Force
- De Bruijn Sequence Generator
- Depth-First
- Iterative Search
- Looking for Magics
- Prolog
- Recursion
- Search
- Trial and Error
Publications
1960 ...
- 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
- Solomon W. Golomb, Leonard D. Baumert (1965). Backtrack Programming. Journal of the ACM, Vol. 12, No. 4
- Martin Gardner (1969, 1991). The Unexpected Hanging and Other Mathematical Diversions. Simon & Schuster, University Of Chicago Press.
- Chapter 16: The Eight Queens and Other Chessboard Diversions.
1970 ...
- Mark B. Wells (1971). Elements of Combinatorial Computing. Pergamon Press, amazon.com
- James R. Bitner, Edward M. Reingold (1975). Backtrack Programming Techniques. Communications of the ACM, Vol. 18, No. 11 ^{[9]}
- Donald Knuth (1974). Estimating efficiency of backtrack programs. STAN-CS-74-442, CS-Department, Stanford University ^{[10]}
- Donald Knuth (1975). Estimating the Efficiency of Backtrack Programs. Mathemathics of Computation, Vol. 29
- Nissim Francez, Boris Klebansky, Amir Pnueli (1977). Backtracking in Recursive Computations. Acta Informatica Vol. 8, No. 2
- John Gaschnig (1977). A General Backtrack Algorithm That Eliminates Most Redundant Tests. IJCAI 1977
- Hirosi Hitotumatua, Kohei Noshita (1979). A technique for implementing backtrack algorithms and its application. Information Processing Letters Vol. 8, No. 4
- Gary Lindstrom (1979). Backtracking in a Generalized Control Setting. ACM Transactions on Programming Languages and Systems, Vol. 1, No. 1
1980 ...
- Paul W. Purdom, Cynthia A. Brown, Edward L. Robertson (1981). Backtracking with Multi-Level Dynamic Search Rearrangement. Acta Informatica Vol. 15, No. 2
- Robert A. Wagner, Robert Geist (1984). The Crippled Queen Placement Problem. Science of Computer Programming, Vol. 4, No. 3, pdf
- Oliver Vornberger, Burkhard Monien, Ewald Speckenmeyer (1986). Superlinear Speedup for Parallel Backtracking. Technical Report 30, Paderborn University
- Andrew Appel, Guy Jacobson (1988). The World’s Fastest Scrabble Program. Communications of the ACM, Vol. 31, No. 5, pdf » Scrabble
1990 ...
- Ilan Vardi (1991). Computational Recreations in Mathematica. Redwood City, CA: Addison-Wesley, ISBN 0201529890, amazon.com
- Matthew L. Ginsberg (1993). Dynamic Backtracking. JAIR Vol. 1
- Patrick Prosser (1993). Hybrid Algorithms for the Constraint Satisfaction Problem. Computational Intelligence, Vol. 9, No. 3
- Richard Karp, Yanjun Zhang (1993). Randomized parallel algorithms for backtrack search and branch-and-bound computation. Journal of the ACM, Vol. 40, No. 3 ^{[11]}
- Matthew L. Ginsberg, David McAllester (1994). GSAT and Dynamic Backtracking. KR 1994 ^{[12]}
- Peter Sanders (1995). Better Algorithms for Parallel Backtracking. IRREGULAR 1995
- Paul W. Purdom, G. Neil Haven (1996). Backtracking and Probing. Satisfiability Problem: Theory and Applications 1996, pdf
- Basil Vandegriend, Joe Culberson (1998). The Gn, m Phase Transition is Not Hard for the Hamiltonian Cycle Problem. JAIR, Vol. 9, arXiv:1105.5443 ^{[13]}
2000 ...
- Carla P. Gomes, Cèsar Fernández, Bart Selman, Christian Bessière (2004). Statistical Regimes Across Constrainedness Regions. CP 2004, pdf
- Lukas Kroc, Ashish Sabharwal, Bart Selman (2008, 2011). Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting. CPAIOR 2008, Annals of Operations Research, Vol. 184
2010 ...
- Pablo San Segundo (2011). New decision rules for exact search in N-Queens. Journal of Global Optimization, Vol. 51, No. 3
- Martin Gardner (2014). Knots and Borromean Rings, Rep-Tiles, and Eight Queens: Martin Gardner’s Unexpected Hanging. The Mathematical Association of America / Cambridge University Press
- Chapter 16: The Eight Queens and Other Chessboard Diversions.
Forum Posts
- N-Queens number for large boards by Truman Collins, rgcm, January 30, 1997
- N Queens Puzzle Algorithm by Aaron Alfer, CCC, December 15, 2017
External Links
- Backtracking from Wikipedia
- Backjumping from Wikipedia
- Backtrack Search using a Computer from The Search for a Finite Projective Plane of Order 10 by Clement W. H. Lam
- Constraint satisfaction problem from Wikipedia
- Boolean satisfiability problem
- NP-complete from Wikipedia
- Karp's 21 NP-complete problems from Wikipedia
- List of NP-complete problems from Wikipedia
- Four color theorem from Wikipedia
- Knight's tour from Wikipedia and a backtracking implementation in C++
- Eight queens puzzle from Wikipedia
- N-queens problem - Rosetta Code
- Knuth's Algorithm X from Wikipedia
- Dancing Links from Wikipedi
- Dancing Links : Solving Sodoku by Xi Chen
- Sudoku algorithms from Wikipedia
- Exact Covering and DLX by Dylan Scott, March 6, 2010
- Sudoku as an Exact Cover Problem by Dylan Scott, March 17, 2010
- Trial and error from Wikipedia
- Backtracking poems by Dave Oliphant
- Flora Purim - Niura is Coming Back, YouTube Video
References
- ↑ Visual Example of the Eight Queens backtrack Algorithm, Wikimedia Commons, Eight queens puzzle from Wikipedia
- ↑ James R. Bitner, Edward M. Reingold (1975). Backtrack Programming Techniques. Communications of the ACM, Vol. 18, No. 11
- ↑ 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
- ↑ 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
- ↑ Magic square from Wikipedia
- ↑ John Gaschnig (1977). A General Backtrack Algorithm That Eliminates Most Redundant Tests. IJCAI 1977
- ↑ Queens ~ /etc/marcelk
- ↑ 8 Queens (NO *SPOILER*) by Tony Lezard, rec.puzzles, November 18, 1991
- ↑ The 70*70 Square Puzzle by Thomas Wolf
- ↑ Re: Perft(15) estimate after averaging 800 MC samples by Daniel Shawul, CCC, November 21, 2013 » Perft
- ↑ Branch and bound - Wikipedia
- ↑ WalkSAT from WIkipedia
- ↑ Hamiltonian path problem from Wikipedia