25,161
edits
Changes
Created page with "'''Home * Programming * Algorithms * Backtracking''' FILE:Eight-queens-animation.gif|border|right|thumb| link=https://commons.wikimedia.org/wiki/File:..."
'''[[Main Page|Home]] * [[Programming]] * [[Algorithms]] * Backtracking'''
[[FILE:Eight-queens-animation.gif|border|right|thumb|
link=https://commons.wikimedia.org/wiki/File:Eight-queens-animation.gif|Eight queens puzzle <ref>Visual Example of the Eight Queens backtrack Algorithm, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Eight_queens_puzzle Eight queens puzzle from Wikipedia]</ref> ]]
'''Backtracking''',<br/>
a general search algorithm for finding solutions of certain [https://en.wikipedia.org/wiki/Computational_problem 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 [[Recursion|recursive]] [[Depth-First|depth-first]] algorithm, are not considered [[Brute-Force|brute-force]], and have the advantage of potentially requiring a search tree with less nodes.
=History=
[[Mathematician#JRBitner|Bitner]] and [[Mathematician#EMReingold|Reingold]] <ref>[[Mathematician#JRBitner|James R. Bitner]], [[Mathematician#EMReingold|Edward M. Reingold]] ('''1975'''). ''[http://portal.acm.org/citation.cfm?id=361224&dl=ACM&coll=DL&CFID=18128359&CFTOKEN=31610180 Backtrack Programming Techniques]''. [https://en.wikipedia.org/wiki/Communications_of_the_ACM Communications of the ACM], Vol. 18, No. 11</ref> credit [[Mathematician#DHLehmer|Derrick H. Lehmer]] with first using the term 'backtrack' in the 1950s, but it has been discovered and rediscovered many times. [[Mathematician#RJWalker|Robert J. Walker]] <ref>[[Mathematician#RJWalker|Robert J. Walker]] ('''1960'''). ''An Enumerative Technique for a Class of Combinatorial Problems''. [http://www.bibliopolis.com/main/books/caliban_0036592.html Proceedings of Symposia in Applied Mathematics, Vol. X, Combinatorial Analysis], [[Richard E. Bellman]] and [[Mathematician#MHallJr|Marshall Hall, Jr.]], eds., [https://en.wikipedia.org/wiki/American_Mathematical_Society American Mathematical Society], [https://en.wikipedia.org/wiki/Providence,_RI Providence, Rhode Island], pp. 91-94</ref> was the first who called using a well-known depth-first procedure Backtracking in 1960.
=Applications=
Classic examples of using backtracking algorithms are solving [https://en.wikipedia.org/wiki/Exact_cover Exact cover problems] and [https://en.wikipedia.org/wiki/Tour_puzzle Tour puzzles], like the [https://en.wikipedia.org/wiki/Eight_queens_puzzle Eight queens puzzle], the [https://en.wikipedia.org/wiki/Knight%27s_tour Knight's tour puzzle] and other [https://en.wikipedia.org/wiki/Maze Maze] or [https://en.wikipedia.org/wiki/Labyrinth Labyrinth] puzzles. [[Donald Knuth|Knuth's]] [https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X Algorithm X] along with [https://en.wikipedia.org/wiki/Dancing_Links Dancing Links] finds all solutions to an exact cover problem. Backtracking is further applied to solving [https://en.wikipedia.org/wiki/Constraint_satisfaction_problem Constraint satisfaction problems], such as [https://en.wikipedia.org/wiki/Crosswords Crossword puzzles], [https://en.wikipedia.org/wiki/Sudoku Sudoku], [https://en.wikipedia.org/wiki/Pentomino Pentomino] tiling, [https://en.wikipedia.org/wiki/Boolean_satisfiability_problem boolean satisfiability problems] and other [https://en.wikipedia.org/wiki/NP-complete NP-complete problems]. [https://en.wikipedia.org/wiki/Logic_programming Logic programming languages] such as [[Prolog]] internally use backtracking to generate answers.
==De Bruijn sequences==
A further sample is to find [[De Bruijn sequence|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|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|trial and error]] with spare populated, but otherwise randomly chosen numbers is used.
<span id="8QinBitboards"></span>
==8Q in Bitboards==
"Thinking" [[Bitboards]], [[Gerd Isenberg]] made following [https://en.wikipedia.org/wiki/Eight_queens_puzzle Eight queens] <ref>[http://www.ii.metu.edu.tr/people/onur-demir%C3%B6rs Onur Demirörs], [http://www.ii.metu.edu.tr/biblio/author/749 N. Rafraf], [http://www.ii.metu.edu.tr/biblio/author/750 M.M. Tanik] ('''1992'''). ''[http://www.ii.metu.edu.tr/publications/1992/obtaining-n-queens-solutions-magic-squares-and-constructing-magic-squares-n-queens Obtaining n-queens solutions from magic squares and constructing magic squares from n-queens solutions]''. Journal of Recreational Mathematics, Vol. 24</ref> <ref>[https://en.wikipedia.org/wiki/Magic_square Magic square from Wikipedia]</ref> proposal, to traverse [[Ranks|ranks]] as disjoint candidate sets for one [[Queen|queen]] each, with premature elimination of redundant tests <ref>[[John Gaschnig]] ('''1977'''). ''[http://portal.acm.org/citation.cfm?id=1624534 A General Backtrack Algorithm That Eliminates Most Redundant Tests]''. [http://www.informatik.uni-trier.de/%7Eley/db/conf/ijcai/ijcai77.html IJCAI 1977]</ref> of [[Squares|squares]] already [[Sliding Piece Attacks|attacked]] by queens put on the board . Therefor, while [[Bitboard Serialization|serializing]] the set of not attacked candidate squares from one rank to put a queen on it, it maintains a "taboo" [[General Setwise Operations#Union|union set]] for consequent queens on upper ranks by "oring" [[On an empty Board|queen attacks]] in [[On an empty Board#PositiveRays|north]] [[Direction|directions]]. It performs some optimization to keep the processed rank always the first, to only use a lookup [[Array|array]] of queen attacks of that first rank, and to [[General Setwise Operations#ShiftingBitboards|shift]] the taboo-set consecutively [[General Setwise Operations#OneStepOnly|one rank down]]. A little [[Space-Time Tradeoff|space-time tradeoff]] saves the [[BitScan|bitscan]] at the cost of some more [[Memory|memory]] to index the eight attacks from an [https://en.wikipedia.org/wiki/Sparse_array sparse array] of 129 bitboards with the [[General Setwise Operations#LS1BIsolation|single isolated]] [[Bit|bit]] inside one [[Byte|byte]] (the first rank).
===Code===
The sample [[C]] code demonstrates an [[Iteration|iterative solution]] using [[Array|arrays]] as explicit [[Stack|stacks]] on the stack:
<pre>
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" */
}
</pre>
===Node Counts===
The algorithm backtracks all [https://en.wikipedia.org/wiki/Eight_queens_puzzle#Constructing_a_solution 92 distinct Eight queen solutions]. Using an '''if do-while else''' construct instead of '''while''' control structure allows counting "pruned" [[Node|nodes]], where the candidate set is initially empty in the else case, leaving following node statistics differentiated by ply (excluding the [[Root|root]]):
{| class="wikitable"
|-
! Ply
! Nodes
! Pruned
! Sum
|-
! 0
| style="text-align:right;" | 8
| style="text-align:right;" | 0
| style="text-align:right;" | 8
|-
! 1
| style="text-align:right;" | 42
| style="text-align:right;" | 0
| style="text-align:right;" | 42
|-
! 2
| style="text-align:right;" | 140
| style="text-align:right;" | 0
| style="text-align:right;" | 140
|-
! 3
| style="text-align:right;" | 344
| style="text-align:right;" | 0
| style="text-align:right;" | 344
|-
! 4
| style="text-align:right;" | 568
| style="text-align:right;" | 18
| style="text-align:right;" | 586
|-
! 5
| style="text-align:right;" | 550
| style="text-align:right;" | 150
| style="text-align:right;" | 700
|-
! 6
| style="text-align:right;" | 312
| style="text-align:right;" | 256
| style="text-align:right;" | 568
|-
! 7
| style="text-align:right;" | '''92'''
| style="text-align:right;" | 220
| style="text-align:right;" | 312
|-
! Sum
| style="text-align:right;" | 2056
| style="text-align:right;" | 644
| style="text-align:right;" | 2700
|}
===Data and Print===
The declaration of the north attack array to save a byte-wise [[BitScan|bitscan]], and for convenience the print routine used:
<pre>
/**
* 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");
}
</pre>
==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 <ref>[http://marcelk.net/queens/ Queens ~ /etc/marcelk]</ref>, [[Bit-Twiddling]] as its best:
<pre>
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));}
</pre>
===By Tony Lezard===
As mentioned by Marcel van Kervinck, a similar 8 Queen program was introduced by Tony Lezard in 1991 <ref>[http://groups.google.com/group/rec.puzzles/msg/4820204ffbaad284?hl=en&dmode=source 8 Queens (NO *SPOILER*)] by Tony Lezard, [http://groups.google.com/group/rec.puzzles/topics?hl=en rec.puzzles], November 18, 1991</ref>:
<pre>
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);
}
</pre>
=See also=
* [[Brute-Force]]
* [[De Bruijn Sequence Generator]]
* [[Depth-First]]
* [[Iterative Search]]
* [[Looking for Magics]]
* [[Prolog]]
* [[Recursion]]
* [[Search]]
* [[Trial and Error]]
=Publications=
==1960 ...==
* [[Mathematician#RJWalker|Robert J. Walker]] ('''1960'''). ''An Enumerative Technique for a Class of Combinatorial Problems''. [http://www.bibliopolis.com/main/books/caliban_0036592.html Proceedings of Symposia in Applied Mathematics, Vol. X, Combinatorial Analysis], [[Richard E. Bellman]] and [[Mathematician#MHallJr|Marshall Hall, Jr.]], eds., [https://en.wikipedia.org/wiki/American_Mathematical_Society American Mathematical Society], [https://en.wikipedia.org/wiki/Providence,_RI Providence, Rhode Island], pp. 91-94
* [[Mathematician#SMGolomb|Solomon W. Golomb]], [[Mathematician#LDBaumert|Leonard D. Baumert]] ('''1965'''). ''[http://portal.acm.org/citation.cfm?id=321300&dl=ACM&coll=DL Backtrack Programming]''. [[ACM#Journal|Journal of the ACM]], Vol. 12, No. 4
* [[Martin Gardner]] ('''1969, 1991'''). ''The Unexpected Hanging and Other Mathematical Diversions''. [https://en.wikipedia.org/wiki/Simon_%26_Schuster Simon & Schuster], [https://en.wikipedia.org/wiki/University_of_Chicago_Press University Of Chicago Press].
: Chapter 16: ''The Eight Queens and Other Chessboard Diversions''.
==1970 ...==
* [[Mathematician#MBWells|Mark B. Wells]] ('''1971'''). ''Elements of Combinatorial Computing''. [https://en.wikipedia.org/wiki/Pergamon_Press Pergamon Press], [http://www.amazon.com/Elements-combinatorial-computing-Mark-Wells/dp/B0000EG7JI amazon.com]
* [[Mathematician#JRBitner|James R. Bitner]], [[Mathematician#EMReingold|Edward M. Reingold]] ('''1975'''). ''[http://portal.acm.org/citation.cfm?id=361224&dl=ACM&coll=DL&CFID=18128359&CFTOKEN=31610180 Backtrack Programming Techniques]''. [[ACM#Communications|Communications of the ACM]], Vol. 18, No. 11 <ref>[http://home.datacomm.ch/t_wolf/tw/misc/squares.html The 70*70 Square Puzzle] by [http://home.datacomm.ch/t_wolf/ Thomas Wolf]</ref>
* [[Donald Knuth]] ('''1974'''). ''Estimating efficiency of backtrack programs''. STAN-CS-74-442, CS-Department, [[Stanford University]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47740&start=36 Re: Perft(15) estimate after averaging 800 MC samples] by [[Daniel Shawul]], [[CCC]], November 21, 2013 » [[Perft]]</ref>
* [[Donald Knuth]] ('''1975'''). ''[http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0373371-6/home.html Estimating the Efficiency of Backtrack Programs]''. [http://www.ams.org/publications/journals/journalsframework/mcom Mathemathics of Computation], Vol. 29
* [http://www.cs.technion.ac.il/%7Efrancez/ Nissim Francez], [http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/k/Klebansky:Boris.html Boris Klebansky], [https://en.wikipedia.org/wiki/Amir_Pnueli Amir Pnueli] ('''1977'''). ''Backtracking in Recursive Computations''. [http://ftp.math.utah.edu/pub//tex/bib/toc/actainfo.html#8%282%29:May:1977 Acta Informatica Vol. 8, No. 2]
* [[John Gaschnig]] ('''1977'''). ''[http://portal.acm.org/citation.cfm?id=1624534 A General Backtrack Algorithm That Eliminates Most Redundant Tests]''. [http://www.informatik.uni-trier.de/%7Eley/db/conf/ijcai/ijcai77.html IJCAI 1977]
* [http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/h/Hitotumatu:Hirosi.html Hirosi Hitotumatua], [[Kohei Noshita]] ('''1979'''). ''[http://portal.acm.org/citation.cfm?id=1710829 A technique for implementing backtrack algorithms and its application]''. [https://en.wikipedia.org/wiki/Information_Processing_Letters Information Processing Letters] Vol. 8, No. 4
* [[Gary Lindstrom]] ('''1979'''). ''[http://dl.acm.org/citation.cfm?id=357063 Backtracking in a Generalized Control Setting]''. [[ACM#TOPLAS|ACM Transactions on Programming Languages and Systems]], Vol. 1, No. 1
==1980 ...==
* [https://www.cs.indiana.edu/%7Epwp/ Paul Walton Purdom, Jr.], [http://web.cecs.pdx.edu/%7Ecbrown/ Cynthia A. Brown], [https://www.cs.indiana.edu/%7Eedrbtsn/ Edward L. Robertson] ('''1981'''). ''Backtracking with Multi-Level Dynamic Search Rearrangement''. [http://ftp.math.utah.edu/pub//tex/bib/toc/actainfo.html#15%282%29:December:1981 Acta Informatica Vol. 15, No. 2]
* [[Oliver Vornberger]], [[Burkhard Monien]], [[Ewald Speckenmeyer]] ('''1986'''). ''Superlinear Speedup for Parallel Backtracking.'' Technical Report 30, [[University of Paderborn]]
* [[Andrew Appel]], [[Guy Jacobson]] ('''1988'''). ''The World’s Fastest Scrabble Program''. [[ACM#Communications|Communications of the ACM]], Vol. 31, No. 5, [https://pdfs.semanticscholar.org/da31/cb24574f7c881a5dbf008e52aac7048c9d9c.pdf pdf] » [[Scrabble]]
==1990 ...==
* [[Ilan Vardi]] ('''1991'''). ''Computational Recreations in Mathematica''. Redwood City, CA: Addison-Wesley, ISBN 0201529890, [http://www.amazon.com/Computational-Recreations-Mathematica-Ilan-Vardi/dp/0201529890 amazon.com]
* [https://www.cs.indiana.edu/%7Epwp/ Paul Walton Purdom, Jr.] ('''1993'''). ''Backtracking and Probing''. [ftp://ftp.cs.indiana.edu/pub/techreports/TR387.ps.Z zipped ps]
* [[Matthew L. Ginsberg]] ('''1993'''). ''[http://www.jair.org/papers/paper1.html Dynamic Backtracking]''. [http://www.jair.org/vol/vol1.html JAIR Vol. 1]
* [http://www.dcs.gla.ac.uk/%7Epat/ Patrick Prosser] ('''1993'''). ''Hybrid Algorithms for the Constraint Satisfaction Problem''. [http://www.blackwellpublishing.com/journal.asp?ref=0824-7935 Computational Intelligence], Vol. 9, No. 3, [http://www.dcs.gla.ac.uk/publications/PAPERS/8104/prosser_cbj.pdf pdf]
* [[Richard Karp]], [[Yanjun Zhang]] ('''1993'''). ''[http://dl.acm.org/citation.cfm?id=174130.174145&coll=DL&dl=GUIDE&CFID=67253533&CFTOKEN=20355103 Randomized parallel algorithms for backtrack search and branch-and-bound computation]''. [[ACM#Journal|Journal of the ACM]], Vol. 40, No. 3 <ref>[https://en.wikipedia.org/wiki/Branch_and_bound Branch and bound - Wikipedia]</ref>
* [[Matthew L. Ginsberg]], [[David McAllester]] ('''1994'''). ''GSAT and Dynamic Backtracking''. [http://www.informatik.uni-trier.de/~ley/db/conf/kr/kr94.html#GinsbergM94 KR 1994] <ref>[https://en.wikipedia.org/wiki/WalkSAT WalkSAT from WIkipedia]</ref>
* [[Peter Sanders]] ('''1995'''). ''Better Algorithms for Parallel Backtracking''. [http://www.informatik.uni-trier.de/~ley/db/conf/irregular/irregular95.html#HoppS95 IRREGULAR 1995]
==2000 ...==
* [http://www.cs.cornell.edu/gomes/ Carla P. Gomes], [http://dblp.uni-trier.de/pers/hd/f/Fern=aacute=ndez:C=egrave=sar Cèsar Fernández], [[Bart Selman]], [http://dblp.uni-trier.de/pers/hd/b/Bessiere:Christian Christian Bessière] ('''2004'''). ''Statistical Regimes Across Constrainedness Regions''. [http://dblp.uni-trier.de/db/conf/cp/cp2004.html#GomesFSB04 CP 2004], [http://www.cs.cornell.edu/selman/papers/pdf/04.cp.stat-regimes.pdf pdf]
* [http://www.cs.cornell.edu/~kroc/ Lukas Kroc], [[Ashish Sabharwal]], [[Bart Selman]] ('''2008, 2011'''). ''[http://link.springer.com/article/10.1007%2Fs10479-009-0680-7 Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting]''. [http://dblp.uni-trier.de/db/conf/cpaior/cpaior2008.html#KrocSS08 CPAIOR 2008], [http://dblp.uni-trier.de/db/journals/anor/anor184.html#KrocSS11 Annals of Operations Research, Vol. 184]
==2010 ...==
* [[Pablo San Segundo]] ('''2011'''). ''[http://www.springerlink.com/content/t18m6980g334nu84/ New decision rules for exact search in N-Queens]''. [http://www.informatik.uni-trier.de/~ley/db/journals/jgo/jgo51.html#Segundo11 Journal of Global Optimization, Vol. 51, No. 3]
* [[Martin Gardner]] ('''2014'''). ''[http://www.cambridge.org/gb/academic/subjects/mathematics/recreational-mathematics/knots-and-borromean-rings-rep-tiles-and-eight-queens-martin-gardners-unexpected-hanging Knots and Borromean Rings, Rep-Tiles, and Eight Queens: Martin Gardner’s Unexpected Hanging]''. [https://en.wikipedia.org/wiki/Mathematical_Association_of_America The Mathematical Association of America] / [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press]
: Chapter 16: ''The Eight Queens and Other Chessboard Diversions''.
=Forum Posts=
* [http://groups.google.com/group/rec.games.chess.misc/browse_frm/thread/b72dbea8a0e52542 N-Queens number for large boards] by [[Truman Collins]], [[Computer Chess Forums|rgcm]], January 30, 1997
* [http://www.talkchess.com/forum/viewtopic.php?t=66016 N Queens Puzzle Algorithm] by Aaron Alfer, [[CCC]], December 15, 2017
=External Links=
* [https://en.wikipedia.org/wiki/Backtracking Backtracking from Wikipedia]
* [https://en.wikipedia.org/wiki/Backjumping Backjumping from Wikipedia]
* [http://www.cecm.sfu.ca/organics/papers/lam/paper/html/node4.html Backtrack Search using a Computer] from [http://www.cecm.sfu.ca/organics/papers/lam/paper/html/paper.html The Search for a Finite Projective Plane of Order 10] by [http://www.cecm.sfu.ca/organics/authors/lam/ Clement W. H. Lam]
* [https://en.wikipedia.org/wiki/Constraint_satisfaction_problem Constraint satisfaction problem from Wikipedia]
* [https://en.wikipedia.org/wiki/Boolean_satisfiability_problem Boolean satisfiability problem]
* [https://en.wikipedia.org/wiki/NP-complete NP-complete from Wikipedia]
* [https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems Karp's 21 NP-complete problems from Wikipedia]
* [https://en.wikipedia.org/wiki/List_of_NP-complete_problems List of NP-complete problems from Wikipedia]
* [https://en.wikipedia.org/wiki/Four_color_theorem Four color theorem from Wikipedia]
* [https://en.wikipedia.org/wiki/Knight%27s_tour Knight's tour from Wikipedia] and [http://www.compgeom.com/%7Epiyush/teach/3330/homeworks/knightour.cpp a backtracking implementation in C++]
* [https://en.wikipedia.org/wiki/Eight_queens_puzzle Eight queens puzzle from Wikipedia]
* [http://rosettacode.org/wiki/N-queens_problem N-queens problem] - [https://en.wikipedia.org/wiki/Rosetta_Code Rosetta Code]
* [https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X Knuth's Algorithm X from Wikipedia]
* [https://en.wikipedia.org/wiki/Dancing_Links Dancing Links from Wikipedi]
* [http://cgi.cse.unsw.edu.au/%7Exche635/dlx_sodoku/ Dancing Links : Solving Sodoku] by [http://youtu.be/FL2VahPZlk4 Xi Chen]
* [https://en.wikipedia.org/wiki/Sudoku_algorithms Sudoku algorithms from Wikipedia]
* [http://www.dylanscott.org/blog/2010/03/exact-covering-and-dlx/ Exact Covering and DLX] by [http://www.dylanscott.org/ Dylan Scott], March 6, 2010
* [http://www.dylanscott.org/blog/2010/03/sudoku-as-an-exact-cover-problem/ Sudoku as an Exact Cover Problem] by [http://www.dylanscott.org/ Dylan Scott], March 17, 2010
* [https://en.wikipedia.org/wiki/Trial_and_error Trial and error from Wikipedia]
* [http://www.hostpublications.com/books/backtracking.html Backtracking] poems by [http://www.hostpublications.com/books/bookinfo/backtracking-author.html Dave Oliphant]
* [[Videos#FloraPurim|Flora Purim]] - Niura is Coming Back, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=IHi8BbeVq68|alignment=left|valignment=top}}
=References=
<references />
'''[[Algorithms|Up one Level]]'''
[[FILE:Eight-queens-animation.gif|border|right|thumb|
link=https://commons.wikimedia.org/wiki/File:Eight-queens-animation.gif|Eight queens puzzle <ref>Visual Example of the Eight Queens backtrack Algorithm, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Eight_queens_puzzle Eight queens puzzle from Wikipedia]</ref> ]]
'''Backtracking''',<br/>
a general search algorithm for finding solutions of certain [https://en.wikipedia.org/wiki/Computational_problem 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 [[Recursion|recursive]] [[Depth-First|depth-first]] algorithm, are not considered [[Brute-Force|brute-force]], and have the advantage of potentially requiring a search tree with less nodes.
=History=
[[Mathematician#JRBitner|Bitner]] and [[Mathematician#EMReingold|Reingold]] <ref>[[Mathematician#JRBitner|James R. Bitner]], [[Mathematician#EMReingold|Edward M. Reingold]] ('''1975'''). ''[http://portal.acm.org/citation.cfm?id=361224&dl=ACM&coll=DL&CFID=18128359&CFTOKEN=31610180 Backtrack Programming Techniques]''. [https://en.wikipedia.org/wiki/Communications_of_the_ACM Communications of the ACM], Vol. 18, No. 11</ref> credit [[Mathematician#DHLehmer|Derrick H. Lehmer]] with first using the term 'backtrack' in the 1950s, but it has been discovered and rediscovered many times. [[Mathematician#RJWalker|Robert J. Walker]] <ref>[[Mathematician#RJWalker|Robert J. Walker]] ('''1960'''). ''An Enumerative Technique for a Class of Combinatorial Problems''. [http://www.bibliopolis.com/main/books/caliban_0036592.html Proceedings of Symposia in Applied Mathematics, Vol. X, Combinatorial Analysis], [[Richard E. Bellman]] and [[Mathematician#MHallJr|Marshall Hall, Jr.]], eds., [https://en.wikipedia.org/wiki/American_Mathematical_Society American Mathematical Society], [https://en.wikipedia.org/wiki/Providence,_RI Providence, Rhode Island], pp. 91-94</ref> was the first who called using a well-known depth-first procedure Backtracking in 1960.
=Applications=
Classic examples of using backtracking algorithms are solving [https://en.wikipedia.org/wiki/Exact_cover Exact cover problems] and [https://en.wikipedia.org/wiki/Tour_puzzle Tour puzzles], like the [https://en.wikipedia.org/wiki/Eight_queens_puzzle Eight queens puzzle], the [https://en.wikipedia.org/wiki/Knight%27s_tour Knight's tour puzzle] and other [https://en.wikipedia.org/wiki/Maze Maze] or [https://en.wikipedia.org/wiki/Labyrinth Labyrinth] puzzles. [[Donald Knuth|Knuth's]] [https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X Algorithm X] along with [https://en.wikipedia.org/wiki/Dancing_Links Dancing Links] finds all solutions to an exact cover problem. Backtracking is further applied to solving [https://en.wikipedia.org/wiki/Constraint_satisfaction_problem Constraint satisfaction problems], such as [https://en.wikipedia.org/wiki/Crosswords Crossword puzzles], [https://en.wikipedia.org/wiki/Sudoku Sudoku], [https://en.wikipedia.org/wiki/Pentomino Pentomino] tiling, [https://en.wikipedia.org/wiki/Boolean_satisfiability_problem boolean satisfiability problems] and other [https://en.wikipedia.org/wiki/NP-complete NP-complete problems]. [https://en.wikipedia.org/wiki/Logic_programming Logic programming languages] such as [[Prolog]] internally use backtracking to generate answers.
==De Bruijn sequences==
A further sample is to find [[De Bruijn sequence|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|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|trial and error]] with spare populated, but otherwise randomly chosen numbers is used.
<span id="8QinBitboards"></span>
==8Q in Bitboards==
"Thinking" [[Bitboards]], [[Gerd Isenberg]] made following [https://en.wikipedia.org/wiki/Eight_queens_puzzle Eight queens] <ref>[http://www.ii.metu.edu.tr/people/onur-demir%C3%B6rs Onur Demirörs], [http://www.ii.metu.edu.tr/biblio/author/749 N. Rafraf], [http://www.ii.metu.edu.tr/biblio/author/750 M.M. Tanik] ('''1992'''). ''[http://www.ii.metu.edu.tr/publications/1992/obtaining-n-queens-solutions-magic-squares-and-constructing-magic-squares-n-queens Obtaining n-queens solutions from magic squares and constructing magic squares from n-queens solutions]''. Journal of Recreational Mathematics, Vol. 24</ref> <ref>[https://en.wikipedia.org/wiki/Magic_square Magic square from Wikipedia]</ref> proposal, to traverse [[Ranks|ranks]] as disjoint candidate sets for one [[Queen|queen]] each, with premature elimination of redundant tests <ref>[[John Gaschnig]] ('''1977'''). ''[http://portal.acm.org/citation.cfm?id=1624534 A General Backtrack Algorithm That Eliminates Most Redundant Tests]''. [http://www.informatik.uni-trier.de/%7Eley/db/conf/ijcai/ijcai77.html IJCAI 1977]</ref> of [[Squares|squares]] already [[Sliding Piece Attacks|attacked]] by queens put on the board . Therefor, while [[Bitboard Serialization|serializing]] the set of not attacked candidate squares from one rank to put a queen on it, it maintains a "taboo" [[General Setwise Operations#Union|union set]] for consequent queens on upper ranks by "oring" [[On an empty Board|queen attacks]] in [[On an empty Board#PositiveRays|north]] [[Direction|directions]]. It performs some optimization to keep the processed rank always the first, to only use a lookup [[Array|array]] of queen attacks of that first rank, and to [[General Setwise Operations#ShiftingBitboards|shift]] the taboo-set consecutively [[General Setwise Operations#OneStepOnly|one rank down]]. A little [[Space-Time Tradeoff|space-time tradeoff]] saves the [[BitScan|bitscan]] at the cost of some more [[Memory|memory]] to index the eight attacks from an [https://en.wikipedia.org/wiki/Sparse_array sparse array] of 129 bitboards with the [[General Setwise Operations#LS1BIsolation|single isolated]] [[Bit|bit]] inside one [[Byte|byte]] (the first rank).
===Code===
The sample [[C]] code demonstrates an [[Iteration|iterative solution]] using [[Array|arrays]] as explicit [[Stack|stacks]] on the stack:
<pre>
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" */
}
</pre>
===Node Counts===
The algorithm backtracks all [https://en.wikipedia.org/wiki/Eight_queens_puzzle#Constructing_a_solution 92 distinct Eight queen solutions]. Using an '''if do-while else''' construct instead of '''while''' control structure allows counting "pruned" [[Node|nodes]], where the candidate set is initially empty in the else case, leaving following node statistics differentiated by ply (excluding the [[Root|root]]):
{| class="wikitable"
|-
! Ply
! Nodes
! Pruned
! Sum
|-
! 0
| style="text-align:right;" | 8
| style="text-align:right;" | 0
| style="text-align:right;" | 8
|-
! 1
| style="text-align:right;" | 42
| style="text-align:right;" | 0
| style="text-align:right;" | 42
|-
! 2
| style="text-align:right;" | 140
| style="text-align:right;" | 0
| style="text-align:right;" | 140
|-
! 3
| style="text-align:right;" | 344
| style="text-align:right;" | 0
| style="text-align:right;" | 344
|-
! 4
| style="text-align:right;" | 568
| style="text-align:right;" | 18
| style="text-align:right;" | 586
|-
! 5
| style="text-align:right;" | 550
| style="text-align:right;" | 150
| style="text-align:right;" | 700
|-
! 6
| style="text-align:right;" | 312
| style="text-align:right;" | 256
| style="text-align:right;" | 568
|-
! 7
| style="text-align:right;" | '''92'''
| style="text-align:right;" | 220
| style="text-align:right;" | 312
|-
! Sum
| style="text-align:right;" | 2056
| style="text-align:right;" | 644
| style="text-align:right;" | 2700
|}
===Data and Print===
The declaration of the north attack array to save a byte-wise [[BitScan|bitscan]], and for convenience the print routine used:
<pre>
/**
* 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");
}
</pre>
==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 <ref>[http://marcelk.net/queens/ Queens ~ /etc/marcelk]</ref>, [[Bit-Twiddling]] as its best:
<pre>
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));}
</pre>
===By Tony Lezard===
As mentioned by Marcel van Kervinck, a similar 8 Queen program was introduced by Tony Lezard in 1991 <ref>[http://groups.google.com/group/rec.puzzles/msg/4820204ffbaad284?hl=en&dmode=source 8 Queens (NO *SPOILER*)] by Tony Lezard, [http://groups.google.com/group/rec.puzzles/topics?hl=en rec.puzzles], November 18, 1991</ref>:
<pre>
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);
}
</pre>
=See also=
* [[Brute-Force]]
* [[De Bruijn Sequence Generator]]
* [[Depth-First]]
* [[Iterative Search]]
* [[Looking for Magics]]
* [[Prolog]]
* [[Recursion]]
* [[Search]]
* [[Trial and Error]]
=Publications=
==1960 ...==
* [[Mathematician#RJWalker|Robert J. Walker]] ('''1960'''). ''An Enumerative Technique for a Class of Combinatorial Problems''. [http://www.bibliopolis.com/main/books/caliban_0036592.html Proceedings of Symposia in Applied Mathematics, Vol. X, Combinatorial Analysis], [[Richard E. Bellman]] and [[Mathematician#MHallJr|Marshall Hall, Jr.]], eds., [https://en.wikipedia.org/wiki/American_Mathematical_Society American Mathematical Society], [https://en.wikipedia.org/wiki/Providence,_RI Providence, Rhode Island], pp. 91-94
* [[Mathematician#SMGolomb|Solomon W. Golomb]], [[Mathematician#LDBaumert|Leonard D. Baumert]] ('''1965'''). ''[http://portal.acm.org/citation.cfm?id=321300&dl=ACM&coll=DL Backtrack Programming]''. [[ACM#Journal|Journal of the ACM]], Vol. 12, No. 4
* [[Martin Gardner]] ('''1969, 1991'''). ''The Unexpected Hanging and Other Mathematical Diversions''. [https://en.wikipedia.org/wiki/Simon_%26_Schuster Simon & Schuster], [https://en.wikipedia.org/wiki/University_of_Chicago_Press University Of Chicago Press].
: Chapter 16: ''The Eight Queens and Other Chessboard Diversions''.
==1970 ...==
* [[Mathematician#MBWells|Mark B. Wells]] ('''1971'''). ''Elements of Combinatorial Computing''. [https://en.wikipedia.org/wiki/Pergamon_Press Pergamon Press], [http://www.amazon.com/Elements-combinatorial-computing-Mark-Wells/dp/B0000EG7JI amazon.com]
* [[Mathematician#JRBitner|James R. Bitner]], [[Mathematician#EMReingold|Edward M. Reingold]] ('''1975'''). ''[http://portal.acm.org/citation.cfm?id=361224&dl=ACM&coll=DL&CFID=18128359&CFTOKEN=31610180 Backtrack Programming Techniques]''. [[ACM#Communications|Communications of the ACM]], Vol. 18, No. 11 <ref>[http://home.datacomm.ch/t_wolf/tw/misc/squares.html The 70*70 Square Puzzle] by [http://home.datacomm.ch/t_wolf/ Thomas Wolf]</ref>
* [[Donald Knuth]] ('''1974'''). ''Estimating efficiency of backtrack programs''. STAN-CS-74-442, CS-Department, [[Stanford University]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=47740&start=36 Re: Perft(15) estimate after averaging 800 MC samples] by [[Daniel Shawul]], [[CCC]], November 21, 2013 » [[Perft]]</ref>
* [[Donald Knuth]] ('''1975'''). ''[http://www.ams.org/journals/mcom/1975-29-129/S0025-5718-1975-0373371-6/home.html Estimating the Efficiency of Backtrack Programs]''. [http://www.ams.org/publications/journals/journalsframework/mcom Mathemathics of Computation], Vol. 29
* [http://www.cs.technion.ac.il/%7Efrancez/ Nissim Francez], [http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/k/Klebansky:Boris.html Boris Klebansky], [https://en.wikipedia.org/wiki/Amir_Pnueli Amir Pnueli] ('''1977'''). ''Backtracking in Recursive Computations''. [http://ftp.math.utah.edu/pub//tex/bib/toc/actainfo.html#8%282%29:May:1977 Acta Informatica Vol. 8, No. 2]
* [[John Gaschnig]] ('''1977'''). ''[http://portal.acm.org/citation.cfm?id=1624534 A General Backtrack Algorithm That Eliminates Most Redundant Tests]''. [http://www.informatik.uni-trier.de/%7Eley/db/conf/ijcai/ijcai77.html IJCAI 1977]
* [http://www.informatik.uni-trier.de/%7Eley/db/indices/a-tree/h/Hitotumatu:Hirosi.html Hirosi Hitotumatua], [[Kohei Noshita]] ('''1979'''). ''[http://portal.acm.org/citation.cfm?id=1710829 A technique for implementing backtrack algorithms and its application]''. [https://en.wikipedia.org/wiki/Information_Processing_Letters Information Processing Letters] Vol. 8, No. 4
* [[Gary Lindstrom]] ('''1979'''). ''[http://dl.acm.org/citation.cfm?id=357063 Backtracking in a Generalized Control Setting]''. [[ACM#TOPLAS|ACM Transactions on Programming Languages and Systems]], Vol. 1, No. 1
==1980 ...==
* [https://www.cs.indiana.edu/%7Epwp/ Paul Walton Purdom, Jr.], [http://web.cecs.pdx.edu/%7Ecbrown/ Cynthia A. Brown], [https://www.cs.indiana.edu/%7Eedrbtsn/ Edward L. Robertson] ('''1981'''). ''Backtracking with Multi-Level Dynamic Search Rearrangement''. [http://ftp.math.utah.edu/pub//tex/bib/toc/actainfo.html#15%282%29:December:1981 Acta Informatica Vol. 15, No. 2]
* [[Oliver Vornberger]], [[Burkhard Monien]], [[Ewald Speckenmeyer]] ('''1986'''). ''Superlinear Speedup for Parallel Backtracking.'' Technical Report 30, [[University of Paderborn]]
* [[Andrew Appel]], [[Guy Jacobson]] ('''1988'''). ''The World’s Fastest Scrabble Program''. [[ACM#Communications|Communications of the ACM]], Vol. 31, No. 5, [https://pdfs.semanticscholar.org/da31/cb24574f7c881a5dbf008e52aac7048c9d9c.pdf pdf] » [[Scrabble]]
==1990 ...==
* [[Ilan Vardi]] ('''1991'''). ''Computational Recreations in Mathematica''. Redwood City, CA: Addison-Wesley, ISBN 0201529890, [http://www.amazon.com/Computational-Recreations-Mathematica-Ilan-Vardi/dp/0201529890 amazon.com]
* [https://www.cs.indiana.edu/%7Epwp/ Paul Walton Purdom, Jr.] ('''1993'''). ''Backtracking and Probing''. [ftp://ftp.cs.indiana.edu/pub/techreports/TR387.ps.Z zipped ps]
* [[Matthew L. Ginsberg]] ('''1993'''). ''[http://www.jair.org/papers/paper1.html Dynamic Backtracking]''. [http://www.jair.org/vol/vol1.html JAIR Vol. 1]
* [http://www.dcs.gla.ac.uk/%7Epat/ Patrick Prosser] ('''1993'''). ''Hybrid Algorithms for the Constraint Satisfaction Problem''. [http://www.blackwellpublishing.com/journal.asp?ref=0824-7935 Computational Intelligence], Vol. 9, No. 3, [http://www.dcs.gla.ac.uk/publications/PAPERS/8104/prosser_cbj.pdf pdf]
* [[Richard Karp]], [[Yanjun Zhang]] ('''1993'''). ''[http://dl.acm.org/citation.cfm?id=174130.174145&coll=DL&dl=GUIDE&CFID=67253533&CFTOKEN=20355103 Randomized parallel algorithms for backtrack search and branch-and-bound computation]''. [[ACM#Journal|Journal of the ACM]], Vol. 40, No. 3 <ref>[https://en.wikipedia.org/wiki/Branch_and_bound Branch and bound - Wikipedia]</ref>
* [[Matthew L. Ginsberg]], [[David McAllester]] ('''1994'''). ''GSAT and Dynamic Backtracking''. [http://www.informatik.uni-trier.de/~ley/db/conf/kr/kr94.html#GinsbergM94 KR 1994] <ref>[https://en.wikipedia.org/wiki/WalkSAT WalkSAT from WIkipedia]</ref>
* [[Peter Sanders]] ('''1995'''). ''Better Algorithms for Parallel Backtracking''. [http://www.informatik.uni-trier.de/~ley/db/conf/irregular/irregular95.html#HoppS95 IRREGULAR 1995]
==2000 ...==
* [http://www.cs.cornell.edu/gomes/ Carla P. Gomes], [http://dblp.uni-trier.de/pers/hd/f/Fern=aacute=ndez:C=egrave=sar Cèsar Fernández], [[Bart Selman]], [http://dblp.uni-trier.de/pers/hd/b/Bessiere:Christian Christian Bessière] ('''2004'''). ''Statistical Regimes Across Constrainedness Regions''. [http://dblp.uni-trier.de/db/conf/cp/cp2004.html#GomesFSB04 CP 2004], [http://www.cs.cornell.edu/selman/papers/pdf/04.cp.stat-regimes.pdf pdf]
* [http://www.cs.cornell.edu/~kroc/ Lukas Kroc], [[Ashish Sabharwal]], [[Bart Selman]] ('''2008, 2011'''). ''[http://link.springer.com/article/10.1007%2Fs10479-009-0680-7 Leveraging Belief Propagation, Backtrack Search, and Statistics for Model Counting]''. [http://dblp.uni-trier.de/db/conf/cpaior/cpaior2008.html#KrocSS08 CPAIOR 2008], [http://dblp.uni-trier.de/db/journals/anor/anor184.html#KrocSS11 Annals of Operations Research, Vol. 184]
==2010 ...==
* [[Pablo San Segundo]] ('''2011'''). ''[http://www.springerlink.com/content/t18m6980g334nu84/ New decision rules for exact search in N-Queens]''. [http://www.informatik.uni-trier.de/~ley/db/journals/jgo/jgo51.html#Segundo11 Journal of Global Optimization, Vol. 51, No. 3]
* [[Martin Gardner]] ('''2014'''). ''[http://www.cambridge.org/gb/academic/subjects/mathematics/recreational-mathematics/knots-and-borromean-rings-rep-tiles-and-eight-queens-martin-gardners-unexpected-hanging Knots and Borromean Rings, Rep-Tiles, and Eight Queens: Martin Gardner’s Unexpected Hanging]''. [https://en.wikipedia.org/wiki/Mathematical_Association_of_America The Mathematical Association of America] / [https://en.wikipedia.org/wiki/Cambridge_University_Press Cambridge University Press]
: Chapter 16: ''The Eight Queens and Other Chessboard Diversions''.
=Forum Posts=
* [http://groups.google.com/group/rec.games.chess.misc/browse_frm/thread/b72dbea8a0e52542 N-Queens number for large boards] by [[Truman Collins]], [[Computer Chess Forums|rgcm]], January 30, 1997
* [http://www.talkchess.com/forum/viewtopic.php?t=66016 N Queens Puzzle Algorithm] by Aaron Alfer, [[CCC]], December 15, 2017
=External Links=
* [https://en.wikipedia.org/wiki/Backtracking Backtracking from Wikipedia]
* [https://en.wikipedia.org/wiki/Backjumping Backjumping from Wikipedia]
* [http://www.cecm.sfu.ca/organics/papers/lam/paper/html/node4.html Backtrack Search using a Computer] from [http://www.cecm.sfu.ca/organics/papers/lam/paper/html/paper.html The Search for a Finite Projective Plane of Order 10] by [http://www.cecm.sfu.ca/organics/authors/lam/ Clement W. H. Lam]
* [https://en.wikipedia.org/wiki/Constraint_satisfaction_problem Constraint satisfaction problem from Wikipedia]
* [https://en.wikipedia.org/wiki/Boolean_satisfiability_problem Boolean satisfiability problem]
* [https://en.wikipedia.org/wiki/NP-complete NP-complete from Wikipedia]
* [https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems Karp's 21 NP-complete problems from Wikipedia]
* [https://en.wikipedia.org/wiki/List_of_NP-complete_problems List of NP-complete problems from Wikipedia]
* [https://en.wikipedia.org/wiki/Four_color_theorem Four color theorem from Wikipedia]
* [https://en.wikipedia.org/wiki/Knight%27s_tour Knight's tour from Wikipedia] and [http://www.compgeom.com/%7Epiyush/teach/3330/homeworks/knightour.cpp a backtracking implementation in C++]
* [https://en.wikipedia.org/wiki/Eight_queens_puzzle Eight queens puzzle from Wikipedia]
* [http://rosettacode.org/wiki/N-queens_problem N-queens problem] - [https://en.wikipedia.org/wiki/Rosetta_Code Rosetta Code]
* [https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X Knuth's Algorithm X from Wikipedia]
* [https://en.wikipedia.org/wiki/Dancing_Links Dancing Links from Wikipedi]
* [http://cgi.cse.unsw.edu.au/%7Exche635/dlx_sodoku/ Dancing Links : Solving Sodoku] by [http://youtu.be/FL2VahPZlk4 Xi Chen]
* [https://en.wikipedia.org/wiki/Sudoku_algorithms Sudoku algorithms from Wikipedia]
* [http://www.dylanscott.org/blog/2010/03/exact-covering-and-dlx/ Exact Covering and DLX] by [http://www.dylanscott.org/ Dylan Scott], March 6, 2010
* [http://www.dylanscott.org/blog/2010/03/sudoku-as-an-exact-cover-problem/ Sudoku as an Exact Cover Problem] by [http://www.dylanscott.org/ Dylan Scott], March 17, 2010
* [https://en.wikipedia.org/wiki/Trial_and_error Trial and error from Wikipedia]
* [http://www.hostpublications.com/books/backtracking.html Backtracking] poems by [http://www.hostpublications.com/books/bookinfo/backtracking-author.html Dave Oliphant]
* [[Videos#FloraPurim|Flora Purim]] - Niura is Coming Back, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=IHi8BbeVq68|alignment=left|valignment=top}}
=References=
<references />
'''[[Algorithms|Up one Level]]'''
