Changes

Jump to: navigation, search

Backtracking

691 bytes added, 10:50, 2 May 2020
no edit summary
<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'''). ''[httphttps://portaldl.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 [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===
* [[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'''). ''[httphttps://portaldl.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 [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
* [[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]
* [[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]]
* [[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]]
* [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]
* [httphttps://wwwen.dcswikipedia.gla.ac.ukorg/%7Epatwiki/ 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]''. [httphttps://wwwen.blackwellpublishingwikipedia.comorg/wiki/Computational_Intelligence_(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]
* [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 ...==
* [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]
* [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:Category:Flora Purim|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}}
'''[[Algorithms|Up one Level]]'''
[[Category:Flora Purim]]

Navigation menu