Difference between revisions of "Backtracking"

From Chessprogramming wiki
Jump to: navigation, search
 
(2 intermediate revisions by the same user not shown)
Line 20: Line 20:
 
<span id="8QinBitboards"></span>
 
<span id="8QinBitboards"></span>
 
==8Q in Bitboards==  
 
==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).  
+
"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'''). ''[https://dl.acm.org/citation.cfm?id=1624534 A General Backtrack Algorithm That Eliminates Most Redundant Tests]''. [[Conferences#IJCAI1977|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===
 
===Code===
Line 215: Line 215:
 
* [[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
 
* [[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]
 
* [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]
+
* [[John Gaschnig]] ('''1977'''). ''[https://dl.acm.org/citation.cfm?id=1624534 A General Backtrack Algorithm That Eliminates Most Redundant Tests]''. [[Conferences#IJCAI1977|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
 
* [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
 
* [[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 ...==
 
==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]
 
* [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]
 +
* [[Robert A. Wagner]], [[Mathematician#RGeist|Robert Geist]] ('''1984'''). ''The Crippled Queen Placement Problem''. [https://dblp.uni-trier.de/db/journals/scp/scp4.html Science of Computer Programming, Vol. 4], No. 3, [https://core.ac.uk/download/pdf/82594002.pdf pdf]
 
* [[Oliver Vornberger]], [[Burkhard Monien]], [[Ewald Speckenmeyer]] ('''1986'''). ''Superlinear Speedup for Parallel Backtracking.'' Technical Report 30, [[Paderborn University]]
 
* [[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''. [[ACM#Communications|Communications of the ACM]], Vol. 31, No. 5, [https://pdfs.semanticscholar.org/da31/cb24574f7c881a5dbf008e52aac7048c9d9c.pdf pdf] » [[Scrabble]]
 
* [[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]]
Line 226: Line 227:
 
* [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]
 
* [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]
 
* [[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]
+
* [https://en.wikipedia.org/wiki/Patrick_Prosser Patrick Prosser] ('''1993'''). ''[https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1467-8640.1993.tb00310.x Hybrid Algorithms for the Constraint Satisfaction Problem]''. [https://en.wikipedia.org/wiki/Computational_Intelligence_(journal) Computational Intelligence], Vol. 9, No. 3
 
* [[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>
 
* [[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>
 
* [[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]
 
* [[Peter Sanders]] ('''1995'''). ''Better Algorithms for Parallel Backtracking''. [http://www.informatik.uni-trier.de/~ley/db/conf/irregular/irregular95.html#HoppS95 IRREGULAR 1995]
 +
* [https://github.com/basilv Basil Vandegriend], [[Joe Culberson]] ('''1998'''). ''[https://www.jair.org/index.php/jair/article/view/10213 The Gn, m Phase Transition is Not Hard for the Hamiltonian Cycle Problem]''. [https://en.wikipedia.org/wiki/Journal_of_Artificial_Intelligence_Research JAIR], Vol. 9, [https://arxiv.org/abs/1105.5443 arXiv:1105.5443] <ref>[https://en.wikipedia.org/wiki/Hamiltonian_path_problem Hamiltonian path problem from Wikipedia]</ref>
 
==2000 ...==
 
==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/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]

Latest revision as of 10:50, 2 May 2020

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

Up one Level