{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T20:41:40Z","timestamp":1775680900224,"version":"3.50.1"},"reference-count":139,"publisher":"Elsevier","isbn-type":[{"value":"9780444527264","type":"print"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1016\/s1574-6526(06)80008-8","type":"book-chapter","created":{"date-parts":[[2008,2,26]],"date-time":"2008-02-26T16:51:39Z","timestamp":1204044699000},"page":"85-134","source":"Crossref","is-referenced-by-count":65,"title":["Backtracking Search Algorithms"],"prefix":"10.1016","member":"78","reference":[{"key":"10.1016\/S1574-6526(06)80008-8_bib1","series-title":"Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming","first-page":"35","article-title":"Extending forward checking","author":"Bacchus","year":"2000"},{"key":"10.1016\/S1574-6526(06)80008-8_bib2","series-title":"Proceedings of the Eighteenth National Conference on Artificial Intelligence","first-page":"613","article-title":"Enhancing Davis Putman with extended binary clause reasoning","author":"Bacchus","year":"2002"},{"key":"10.1016\/S1574-6526(06)80008-8_bib3","series-title":"Proceedings of the First International Conference on Principles and Practice of Constraint Programming","first-page":"292","article-title":"On the forward checking algorithm","author":"Bacchus","year":"1995"},{"key":"10.1016\/S1574-6526(06)80008-8_bib4","series-title":"Looking forward in constraint satisfaction algorithms","author":"Bacchus","year":"1999"},{"key":"10.1016\/S1574-6526(06)80008-8_bib5","series-title":"Proceedings of the First International Conference on Principles and Practice of Constraint Programming","first-page":"258","article-title":"Dynamic variable ordering in CSPs","author":"Bacchus","year":"1995"},{"key":"10.1016\/S1574-6526(06)80008-8_bib6","series-title":"Proceedings of the Eleventh International Conference on Principles and Practice of Constraint Programming","first-page":"732","article-title":"Evolving variable-ordering heuristics for constrained optimisation","author":"Bain","year":"2005"},{"key":"10.1016\/S1574-6526(06)80008-8_bib7","article-title":"Intelligent Backtracking on Constraint Satisfaction Problems: Experimental and Theoretical Results","author":"Baker","year":"1995","journal-title":"PhD thesis, University of Oregon"},{"key":"10.1016\/S1574-6526(06)80008-8_bib8","series-title":"Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming","first-page":"489","article-title":"Using randomization and learning to solve hard real-world instances of satisfiability","author":"Baptista","year":"2000"},{"key":"10.1016\/S1574-6526(06)80008-8_bib9","series-title":"Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems","author":"Baptiste","year":"2001"},{"key":"10.1016\/S1574-6526(06)80008-8_bib10","series-title":"Proceedings of the Thirteenth National Conference on Artificial Intelligence","first-page":"298","article-title":"A complexity analysis of space-bounded learning algorithms for the constraint satisfaction problem","author":"Bayardo","year":"1996"},{"key":"10.1016\/S1574-6526(06)80008-8_bib11","series-title":"Proceedings of the Second International Conference on Principles and Practice of Constraint Programming","first-page":"46","article-title":"Using CSP look-back techniques to solve exceptionally hard SAT instances","author":"Bayardo","year":"1996"},{"key":"10.1016\/S1574-6526(06)80008-8_bib12","series-title":"Proceedings of the Fourteenth National Conference on Artificial Intelligence","first-page":"203","article-title":"Using CSP look-back techniques to solve real-world SAT instances","author":"Bayardo","year":"1997"},{"key":"10.1016\/S1574-6526(06)80008-8_bib13","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1613\/jair.1410","article-title":"Towards understanding and harnessing the potential of clause learning","volume":"22","author":"Beame","year":"2004","journal-title":"J. of Artificial Intelligence Research"},{"key":"10.1016\/S1574-6526(06)80008-8_bib14","series-title":"Recent Advances in Constraints, Lecture Notes in Artificial Intelligence, Vol. 3419","article-title":"Trying again to fail first","author":"Beck","year":"2005"},{"key":"10.1016\/S1574-6526(06)80008-8_bib15","series-title":"Nonserial Dynamic Programming","author":"Bertel\u00e8","year":"1972"},{"key":"10.1016\/S1574-6526(06)80008-8_bib16","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1016\/S0004-3702(02)00263-1","article-title":"On forward checking for non-binary constraint satisfaction","volume":"141","author":"Bessi\u00e8re","year":"2002","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib17","series-title":"Proceedings of the Second International Conference on Principles and Practice of Constraint Programming","first-page":"61","article-title":"MAC and combined heuristics: Two reasons to forsake FC (and CBJ?) on hard problems","author":"Bessi\u00e8re","year":"1996"},{"key":"10.1016\/S1574-6526(06)80008-8_bib18","series-title":"Proceedings of the Fifteenth National Conference on Artificial Intelligence","first-page":"319","article-title":"Generalizing partial order and dynamic backtracking","author":"Bliek","year":"1998"},{"key":"10.1016\/S1574-6526(06)80008-8_bib19","series-title":"Proceedings of the 16th European Conference on Artificial Intelligence","first-page":"146","article-title":"Boosting systematic search by weighting constraints","author":"Boussemart","year":"2004"},{"key":"10.1016\/S1574-6526(06)80008-8_bib20","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1145\/359094.359101","article-title":"New methods to color the vertices of a graph","volume":"22","author":"Br\u00e9laz","year":"1979","journal-title":"Comm. ACM"},{"key":"10.1016\/S1574-6526(06)80008-8_bib21","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1109\/TPAMI.1982.4767250","article-title":"An empirical comparison of backtracking algorithms","volume":"4","author":"Brown","year":"1982","journal-title":"IEEE PAMI"},{"key":"10.1016\/S1574-6526(06)80008-8_bib22","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/0020-0190(81)90074-0","article-title":"Solving combinatorial search problems by intelligent backtracking","volume":"12","author":"Bruynooghe","year":"1981","journal-title":"Information Processing Letters"},{"key":"10.1016\/S1574-6526(06)80008-8_bib23","series-title":"Proceedings of the Eleventh International Conference on Logic Programming","first-page":"369","article-title":"Improved CLP scheduling with task intervals","author":"Caseau","year":"1994"},{"key":"10.1016\/S1574-6526(06)80008-8_bib24","series-title":"Proceedings of the Seventh International Conference on Principles and Practice of Constraint Programming","first-page":"408","article-title":"Formal models of heavy-tailed behavior in combinatorial search","author":"Chen","year":"2001"},{"key":"10.1016\/S1574-6526(06)80008-8_bib25","article-title":"A Theoretical Comparison of Selected CSP Solving and Modeling Techniques","author":"Chen","year":"2000","journal-title":"PhD thesis, University of Alberta"},{"key":"10.1016\/S1574-6526(06)80008-8_bib26","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1613\/jair.788","article-title":"Conflict-directed backjumping revisited","volume":"14","author":"Chen","year":"2001","journal-title":"J. of Artificial Intelligence Research"},{"key":"10.1016\/S1574-6526(06)80008-8_bib27","series-title":"Proceedings of the Eighth International Conference on Principles and Practice of Constraint Programming","first-page":"124","article-title":"Amplification of search performance through randomization of heuristics","author":"Cicirello","year":"2002"},{"key":"10.1016\/S1574-6526(06)80008-8_bib28","doi-asserted-by":"crossref","first-page":"36","DOI":"10.2307\/2273702","article-title":"The relative efficiency of propositional proof systems","volume":"44","author":"Cook","year":"1979","journal-title":"J. Symbolic Logic"},{"key":"10.1016\/S1574-6526(06)80008-8_bib29","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/0004-3702(89)90080-5","article-title":"An optimal k-consistency algorithm","volume":"41","author":"Cooper","year":"1989","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib30","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1145\/368273.368557","article-title":"A machine program for theoremproving","volume":"5","author":"Davis","year":"1962","journal-title":"Comm. ACM"},{"key":"10.1016\/S1574-6526(06)80008-8_bib31","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1145\/321033.321034","article-title":"A computing procedure for quantification theory","volume":"7","author":"Davis","year":"1960","journal-title":"J. ACM"},{"key":"10.1016\/S1574-6526(06)80008-8_bib32","series-title":"Proceedings of the Eleventh International Joint Conference on Artificial Intelligence","first-page":"290","article-title":"A comparison of ATMS and CSP techniques","author":"de Kleer","year":"1989"},{"key":"10.1016\/S1574-6526(06)80008-8_bib33","series-title":"Proceedings of the Fifth National Conference on Artificial Intelligence","first-page":"178","article-title":"Learning while searching in constraint satisfaction problems","author":"Dechter","year":"1986"},{"key":"10.1016\/S1574-6526(06)80008-8_bib34","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/0004-3702(90)90046-3","article-title":"Enhancement schemes for constraint processing: Backjumping, learning, and cutset decomposition","volume":"41","author":"Dechter","year":"1990","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib35","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(87)90002-6","article-title":"Network-based heuristics for constraint satisfaction problems","volume":"34","author":"Dechter","year":"1988","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib36","series-title":"Proceedings of the Eighth International Conference on Principles and Practice of Constraint Programming","first-page":"525","article-title":"The adaptive constraint engine","author":"Epstein","year":"2002"},{"key":"10.1016\/S1574-6526(06)80008-8_bib37","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0004-3702(70)90003-2","article-title":"REF-ARF: A system for solving problems stated as procedures","volume":"1","author":"Fikes","year":"1970","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib38","article-title":"Improvements to Propositional Satisfiability Search Algorithms","author":"Freeman","year":"1995","journal-title":"PhD thesis, University of Pennsylvania"},{"key":"10.1016\/S1574-6526(06)80008-8_bib39","doi-asserted-by":"crossref","first-page":"958","DOI":"10.1145\/359642.359654","article-title":"Synthesizing constraint expressions","volume":"21","author":"Freuder","year":"1978","journal-title":"Comm. ACM"},{"key":"10.1016\/S1574-6526(06)80008-8_bib40","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1145\/322290.322292","article-title":"A sufficient condition for backtrack-free search","volume":"29","author":"Freuder","year":"1982","journal-title":"J. ACM"},{"key":"10.1016\/S1574-6526(06)80008-8_bib41","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1145\/4221.4225","article-title":"A sufficient condition for backtrack-bounded search","volume":"32","author":"Freuder","year":"1985","journal-title":"J. ACM"},{"key":"10.1016\/S1574-6526(06)80008-8_bib42","series-title":"Proceedings of the Ninth International Joint Conference on Artificial Intelligence","first-page":"1076","article-title":"Taking advantage of stable sets of variables in constraint satisfaction problems","author":"Freuder","year":"1985"},{"key":"10.1016\/S1574-6526(06)80008-8_bib43","series-title":"Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence","first-page":"563","article-title":"Generalizing inconsistency learning for constraint satisfaction","author":"Freuder","year":"1995"},{"key":"10.1016\/S1574-6526(06)80008-8_bib44","series-title":"Proceedings of the Twelfth National Conference on Artificial Intelligence","first-page":"294","article-title":"Dead-end driven learning","author":"Frost","year":"1994"},{"key":"10.1016\/S1574-6526(06)80008-8_bib45","series-title":"Proceedings of the Twelfth National Conference on Artificial Intelligence","first-page":"301","article-title":"In search of the best search: An empirical evaluation","author":"Frost","year":"1994"},{"key":"10.1016\/S1574-6526(06)80008-8_bib46","series-title":"Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence","first-page":"572","article-title":"Look-ahead value ordering for constraint satisfaction problems","author":"Frost","year":"1995"},{"key":"10.1016\/S1574-6526(06)80008-8_bib47","series-title":"Proceedings Twelfth Annual Allerton Conference on Circuit and System Theory","first-page":"866","article-title":"A constraint satisfaction method for inference making","author":"Gaschnig","year":"1974"},{"key":"10.1016\/S1574-6526(06)80008-8_bib48","series-title":"Proceedings of the Second Canadian Conference on Artificial Intelligence","first-page":"268","article-title":"Experimental case studies of backtrack vs. Waltz-type vs. new algorithms for satisficing assignment problems","author":"Gaschnig","year":"1978"},{"key":"10.1016\/S1574-6526(06)80008-8_bib49","series-title":"Proceedings of the 10th European Conference on Artificial Intelligence","first-page":"31","article-title":"Dual viewpoint heuristics for binary constraint satisfaction problems","author":"Geelen","year":"1992"},{"key":"10.1016\/S1574-6526(06)80008-8_bib50","series-title":"Proceedings of the Second International Conference on Principles and Practice of Constraint Programming","first-page":"179","article-title":"An empirical study of dynamic variable ordering heuristics for the constraint satisfaction problem","author":"Gent","year":"1996"},{"issue":"4","key":"10.1016\/S1574-6526(06)80008-8_bib51","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1023\/A:1011454308633","article-title":"Random constraint satisfaction: Flaws and structure","volume":"6","author":"Gent","year":"2001","journal-title":"Constraints"},{"key":"10.1016\/S1574-6526(06)80008-8_bib52","series-title":"Proceedings of the Thirteenth National Conference on Artificial Intelligence","first-page":"246","article-title":"The constrainedness of search","author":"Gent","year":"1996"},{"key":"10.1016\/S1574-6526(06)80008-8_bib53","series-title":"Proceedings of the Fifth International Conference on Principles and Practice of Constraint Programming","first-page":"480","article-title":"CSPlib: A benchmark library for constraints","author":"Gent","year":"1999"},{"key":"10.1016\/S1574-6526(06)80008-8_bib54","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1613\/jair.1","article-title":"Dynamic backtracking","volume":"1","author":"Ginsberg","year":"1993","journal-title":"J. of Artificial Intelligence Research"},{"key":"10.1016\/S1574-6526(06)80008-8_bib55","series-title":"Proceedings of the Eighth National Conference on Artificial Intelligence","first-page":"210","article-title":"Search lessons learned from crossword puzzles","author":"Ginsberg","year":"1990"},{"key":"10.1016\/S1574-6526(06)80008-8_bib56","series-title":"Proceedings of the Second Workshop on Principles and Practice of Constraint Programming","first-page":"243","article-title":"GSAT and dynamic backtracking","author":"Ginsberg","year":"1994"},{"key":"10.1016\/S1574-6526(06)80008-8_bib57","doi-asserted-by":"crossref","first-page":"516","DOI":"10.1145\/321296.321300","article-title":"Backtrack programming","volume":"12","author":"Golomb","year":"1965","journal-title":"J. ACM"},{"key":"10.1016\/S1574-6526(06)80008-8_bib58","series-title":"Constraint and Integer Programming: Toward a Unified Methodology","first-page":"233","article-title":"Randomized backtrack search","author":"Gomes","year":"2004"},{"key":"10.1016\/S1574-6526(06)80008-8_bib59","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s10601-005-2807-z","article-title":"Statistical regimes across constrainedness regions","volume":"10","author":"Gomes","year":"2005","journal-title":"Constraints"},{"key":"10.1016\/S1574-6526(06)80008-8_bib60","series-title":"Proceedings of the Third International Conference on Principles and Practice of Constraint Programming","first-page":"121","article-title":"Heavy-tailed distributions in combinatorial search","author":"Gomes","year":"1997"},{"key":"10.1016\/S1574-6526(06)80008-8_bib61","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1023\/A:1006314320276","article-title":"Heavy-tailed phenomena in satisfiability and constraint satisfaction problems","volume":"24","author":"Gomes","year":"2000","journal-title":"J. of Automated Reasoning"},{"key":"10.1016\/S1574-6526(06)80008-8_bib62","series-title":"Proceedings of the Fifteenth National Conference on Artificial Intelligence","article-title":"Boosting combinatorial search through randomization","author":"Gomes","year":"1998"},{"key":"10.1016\/S1574-6526(06)80008-8_bib63","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1016\/0004-3702(80)90051-X","article-title":"Increasing tree search efficiency for constraint satisfaction problems","volume":"14","author":"Haralick","year":"1980","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib64","article-title":"Nonsystematic backtracking search","author":"Harvey","year":"1995","journal-title":"PhD thesis, Stanford University"},{"key":"10.1016\/S1574-6526(06)80008-8_bib65","series-title":"Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence","first-page":"607","article-title":"Limited discrepancy search","author":"Harvey","year":"1995"},{"key":"10.1016\/S1574-6526(06)80008-8_bib66","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1007\/BF02430364","article-title":"Testing heuristics: We have it all wrong","volume":"1","author":"Hooker","year":"1996","journal-title":"Journal of Heuristics"},{"key":"10.1016\/S1574-6526(06)80008-8_bib67","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1007\/BF00881805","article-title":"Branching rules for satisfiability","volume":"15","author":"Hooker","year":"1995","journal-title":"Journal of Automated Reasoning"},{"key":"10.1016\/S1574-6526(06)80008-8_bib68","article-title":"Heavy-tailed behaviour in randomised systematic search algorithms for SAT","author":"Hoos","year":"1999"},{"key":"10.1016\/S1574-6526(06)80008-8_bib69","series-title":"Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence","first-page":"1167","article-title":"A structure-based variable ordering heuristic for SAT","author":"Huang","year":"2003"},{"key":"10.1016\/S1574-6526(06)80008-8_bib70","series-title":"Proceedings of the Eleventh International Conference on Principles and Practice of Constraint Programming","first-page":"328","article-title":"Search heuristics and heavy-tailed behaviour","author":"Hulubei","year":"2005"},{"key":"10.1016\/S1574-6526(06)80008-8_bib71","series-title":"Proceedings of the Eleventh International Conference on Principles and Practice of Constraint Programming","first-page":"343","article-title":"2-way vs. d-way branching for CSP","author":"Hwang","year":"2005"},{"key":"10.1016\/S1574-6526(06)80008-8_bib72","year":"1998","journal-title":"ILOG S. A. ILOG Solver 4.2 user's manual"},{"key":"10.1016\/S1574-6526(06)80008-8_bib73","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/S0004-3702(02)00400-9","article-title":"Hybrid backtracking bounded by tree-decomposition of constraint networks","volume":"146","author":"J\u00e9gou","year":"2003","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib74","series-title":"Proceedings of the Nineteenth National Conference on Artificial Intelligence","first-page":"167","article-title":"QuickXplain: Preferred explanations and relaxations for over-constrained problems","author":"Junker","year":"2004"},{"key":"10.1016\/S1574-6526(06)80008-8_bib75","series-title":"Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming","first-page":"249","article-title":"Maintaining arc-consistency within dynamic backtracking","author":"Jussien","year":"2000"},{"key":"10.1016\/S1574-6526(06)80008-8_bib76","series-title":"Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming","first-page":"317","article-title":"Counting-based look-ahead schemes for constraint satisfaction","author":"Kask","year":"2004"},{"key":"10.1016\/S1574-6526(06)80008-8_bib77","series-title":"Proceedings of the Twentieth National Conference on Artificial Intelligence","first-page":"390","article-title":"Generalized nogoods in CSPs","author":"Katsirelos","year":"2005"},{"key":"10.1016\/S1574-6526(06)80008-8_bib78","series-title":"Proceedings of the Eighteenth National Conference on Artificial Intelligence","first-page":"674","article-title":"Dynamic restart policies","author":"Kautz","year":"2002"},{"key":"10.1016\/S1574-6526(06)80008-8_bib79","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1016\/S0004-3702(96)00027-6","article-title":"A theoretical evaluation of selected backtracking algorithms","volume":"89","author":"Kondrak","year":"1997","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib80","series-title":"Proceedings of the Thirteenth National Conference on Artificial Intelligence","first-page":"286","article-title":"Improved limited discrepancy search","author":"Korf","year":"1996"},{"key":"10.1016\/S1574-6526(06)80008-8_bib81","series-title":"Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming","first-page":"291","article-title":"Boosting search with variable elimination","author":"Larrosa","year":"2000"},{"key":"10.1016\/S1574-6526(06)80008-8_bib82","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0004-3702(78)90029-2","article-title":"A language and a program for stating and solving combinatorial problems","volume":"10","author":"Lauriere","year":"1978","journal-title":"Artficial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib83","series-title":"Proceedings of the Seventh International Conference on Theory and Applications of Satisfiability Testing (SAT2004)","first-page":"321","article-title":"Fifty-five solvers in Vancouver: The SAT 2004 competition","author":"Le Berre","year":"2004"},{"key":"10.1016\/S1574-6526(06)80008-8_bib84","series-title":"Proceedings of the Sixteenth IEEE International Conference on Tools with Artificial Intelligence","first-page":"549","article-title":"Backjump-based techniques versus conflict-directed heuristics","author":"Lecoutre","year":"2004"},{"key":"10.1016\/S1574-6526(06)80008-8_bib85","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S0166-218X(02)00408-0","article-title":"On the limit of branching rules for hard random unsatisfiable 3-SAT","volume":"130","author":"Li","year":"2003","journal-title":"Discrete Applied Mathematics"},{"key":"10.1016\/S1574-6526(06)80008-8_bib86","series-title":"Proceedings of the Sixteenth IEEE International Conference on Tools with Artificial Intelligence","first-page":"542","article-title":"Guiding real-world SAT solving with dynamic hypergraph separator decomposition","author":"Li","year":"2004"},{"key":"10.1016\/S1574-6526(06)80008-8_bib87","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/S0004-3702(99)00097-1","article-title":"On the complexity of choosing the branching literal in DPLL","volume":"116","author":"Liberatore","year":"2000","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib88","series-title":"Proceedings of the Second Israel Symposium on the Theory of Computing and Systems","article-title":"Optimal speedup of Las Vegas algorithms","author":"Luby","year":"1993"},{"key":"10.1016\/S1574-6526(06)80008-8_bib89","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","article-title":"Consistency in networks of relations","volume":"8","author":"Mackworth","year":"1997","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib90","series-title":"Proceedings of the Fifth International Joint Conference on Artificial Intelligence","first-page":"598","article-title":"On reading sketch maps","author":"Mackworth","year":"1977"},{"key":"10.1016\/S1574-6526(06)80008-8_bib91","article-title":"Optimal basic block instruction scheduling for multiple-issue processors using constraint programming","author":"Malik","year":"2005"},{"key":"10.1016\/S1574-6526(06)80008-8_bib92","series-title":"Proceedings of the International Conference on Computer-Aided Design","first-page":"220","article-title":"GRASP \u2014 a new search algorithm for satisfiability","author":"Marques-Silva","year":"1996"},{"key":"10.1016\/S1574-6526(06)80008-8_bib93","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1016\/0020-0255(79)90023-9","article-title":"Relational consistency algorithms and their application in finding subgraph and graph isomorphisms","volume":"19","author":"McGregor","year":"1979","journal-title":"Inform. Sci."},{"key":"10.1016\/S1574-6526(06)80008-8_bib94","series-title":"Proceedings of the Fourteenth National Conference on Artificial Intelligence","first-page":"185","article-title":"Bayes networks for estimating the number of solutions to a CSP","author":"Meisels","year":"1997"},{"key":"10.1016\/S1574-6526(06)80008-8_bib95","series-title":"Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence","first-page":"1382","article-title":"Interleaved depth-first search","author":"Meseguer","year":"1997"},{"key":"10.1016\/S1574-6526(06)80008-8_bib96","series-title":"Proceedings of the 13th European Conference on Artificial Intelligence","first-page":"239","article-title":"Interleaved and discrepancy based search","author":"Meseguer","year":"1998"},{"key":"10.1016\/S1574-6526(06)80008-8_bib97","series-title":"Proceedings of the Eighth International Conference on Principles and Practice of Constraint Programming","first-page":"1","article-title":"Reduced cost-based ranking for generating promising subproblems","author":"Milano","year":"2002"},{"key":"10.1016\/S1574-6526(06)80008-8_bib98","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF00143877","article-title":"Automatically configuring constraint satisfaction programs: A case study","volume":"1","author":"Minton","year":"1996","journal-title":"Constraints"},{"key":"10.1016\/S1574-6526(06)80008-8_bib99","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/0004-3702(92)90007-K","article-title":"Minimizing conflicts: A heuristic repair method for constraint satisfaction and scheduling problems","volume":"58","author":"Minton","year":"1992","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib100","series-title":"Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming","first-page":"555","article-title":"Resolution and constraint satisfaction","author":"Mitchell","year":"2003"},{"key":"10.1016\/S1574-6526(06)80008-8_bib101","series-title":"Proceedings of the 8th European Conference on Artificial Intelligence","first-page":"651","article-title":"Good old discrete relaxation","author":"Mohr","year":"1988"},{"key":"10.1016\/S1574-6526(06)80008-8_bib102","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","article-title":"Networks of constraints: Fundamental properties and applications to picture processing","volume":"7","author":"Montanari","year":"1974","journal-title":"Inform. Sci."},{"key":"10.1016\/S1574-6526(06)80008-8_bib103","series-title":"Proceedings of 39th Design Automation Conference","article-title":"Chaff: Engineering an efficient SAT solver","author":"Moskewicz","year":"2001"},{"key":"10.1016\/S1574-6526(06)80008-8_bib104","doi-asserted-by":"crossref","first-page":"188","DOI":"10.1111\/j.1467-8640.1989.tb00328.x","article-title":"Constraint satisfaction algorithms","volume":"5","author":"Nadel","year":"1989","journal-title":"Computational Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib105","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/S0004-3702(83)80008-3","article-title":"Consistent-labeling problems and their algorithms: Expected-complexities and theory-based heuristics","volume":"21","author":"Nudel","year":"1983","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib106","series-title":"Proceedings of the Sixth International Conference on Principles and Practice of Constraint Programming","first-page":"337","article-title":"A hybrid search architecture applied to hard random 3-SAT and low-autocorrelation binary sequences","author":"Prestwich","year":"2000"},{"key":"10.1016\/S1574-6526(06)80008-8_bib107","series-title":"Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence","first-page":"262","article-title":"Domain filtering can degrade intelligent backtracking search","author":"Prosser","year":"1993"},{"key":"10.1016\/S1574-6526(06)80008-8_bib108","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1111\/j.1467-8640.1993.tb00310.x","article-title":"Hybrid algorithms for the constraint satisfaction problem","volume":"9","author":"Prosser","year":"1993","journal-title":"Computational Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib109","article-title":"MAC-CBJ: Maintaining arc consistency with conflict-directed back-jumping","author":"Prosser","year":"1995","journal-title":"Research Report 177, University of Strathclyde"},{"key":"10.1016\/S1574-6526(06)80008-8_bib110","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/S0004-3702(83)80007-1","article-title":"Search rearrangement backtracking and polynomial average time","volume":"21","author":"Purdom","year":"1983","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib111","series-title":"Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming","first-page":"557","article-title":"Impact-based search strategies for constraint programming","author":"Refalo","year":"2004"},{"key":"10.1016\/S1574-6526(06)80008-8_bib112","article-title":"Non-systematic Search and No-good Learning","author":"Richards","year":"1998","journal-title":"PhD thesis, Imperial College"},{"key":"10.1016\/S1574-6526(06)80008-8_bib113","series-title":"CP03 Workshop on User-Interaction in Constraint Satisfaction (UICS'03)","first-page":"31","article-title":"Challenging explanations for global constraints","author":"Rochart","year":"2003"},{"key":"10.1016\/S1574-6526(06)80008-8_bib114","series-title":"Artificial Intelligence II, Methodology, Systems, Applications, Proc. AIMSA'86","first-page":"173","article-title":"Empirical study of some constraint satisfaction algorithms","author":"Rosiers","year":"1987"},{"key":"10.1016\/S1574-6526(06)80008-8_bib115","series-title":"Proceedings of the Eighth International Conference on Principles and Practice of Constraint Programming","first-page":"573","article-title":"Restart policies with dependence among runs: A dynamic programming approach","author":"Ruan","year":"2002"},{"key":"10.1016\/S1574-6526(06)80008-8_bib116","series-title":"Proceedings of the 11th European Conference on Artificial Intelligence","first-page":"125","article-title":"Contradicting conventional wisdom in constraint satisfaction","author":"Sabin","year":"1994"},{"key":"10.1016\/S1574-6526(06)80008-8_bib117","series-title":"Proceedings of the Third International Conference on Principles and Practice of Constraint Programming","first-page":"167","article-title":"Understanding and improving the MAC algorithm","author":"Sabin","year":"1997"},{"key":"10.1016\/S1574-6526(06)80008-8_bib118","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1142\/S0218213094000108","article-title":"Nogood recording for static and dynamic constraint satisfaction problems","volume":"3","author":"Schiex","year":"1994","journal-title":"International Journal on Artificial Intelligence Tools"},{"key":"10.1016\/S1574-6526(06)80008-8_bib119","series-title":"Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence","first-page":"646","article-title":"Sparse constraint graphs and exceptionally hard problems","author":"Smith","year":"1995"},{"key":"10.1016\/S1574-6526(06)80008-8_bib120","series-title":"Proceedings of the 13th European Conference on Artificial Intelligence","first-page":"249","article-title":"Trying harder to fail first","author":"Smith","year":"1998"},{"key":"10.1016\/S1574-6526(06)80008-8_bib121","series-title":"Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence","first-page":"311","article-title":"Value ordering for finding all solutions","author":"Smith","year":"2005"},{"key":"10.1016\/S1574-6526(06)80008-8_bib122","series-title":"Proceedings of the Eleventh National Conference on Artificial Intelligence","first-page":"139","article-title":"Slack-based heuristics for constraint satisfaction scheduling","author":"Smith","year":"1993"},{"key":"10.1016\/S1574-6526(06)80008-8_bib123","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1007\/BFb0015252","article-title":"The OZ programming model","author":"Smolka","year":"1995","journal-title":"Lecture Notes in Computer Science 1000"},{"key":"10.1016\/S1574-6526(06)80008-8_bib124","doi-asserted-by":"crossref","first-page":"135","DOI":"10.1016\/0004-3702(77)90029-7","article-title":"Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis","volume":"9","author":"Stallman","year":"1977","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S1574-6526(06)80008-8_bib125","doi-asserted-by":"crossref","first-page":"464","DOI":"10.1147\/rd.314.0464","article-title":"Efficient search techniques\u2014an empirical study of the N-queens problem","volume":"31","author":"Stone","year":"1987","journal-title":"IBM J. Res. and Develop."},{"key":"10.1016\/S1574-6526(06)80008-8_bib126","series-title":"Proceedings of the AI and Simulated Behaviour Conference","first-page":"203","article-title":"An attempt to map the performance of a range of algorithm and heuristic combinations","author":"Tsang","year":"1995"},{"key":"10.1016\/S1574-6526(06)80008-8_bib127","series-title":"Cliques, Coloring, and Satisfiability: Second DIMACS Implementation Challenge","first-page":"559","article-title":"Satisfiability testing with more reasoning and less guessing","author":"Van Gelder","year":"1996"},{"key":"10.1016\/S1574-6526(06)80008-8_bib128","series-title":"Constraint Satisfaction in Logic Programming","author":"Van Hentenryck","year":"1989"},{"key":"10.1016\/S1574-6526(06)80008-8_bib129","series-title":"Proceedings of the IEEE Quantitative Evaluation of Systems (QEST 2004)","first-page":"195","article-title":"Analysis and algorithms for restart","author":"van Moorsel","year":"2004"},{"key":"10.1016\/S1574-6526(06)80008-8_bib130","series-title":"Proceedings of the 12th GI\/ITG Conference on Measuring, Modelling and Evaluation of Computer and Communication Systems","first-page":"155","article-title":"Meeting deadlines through restart","author":"van Moorsel","year":"2004"},{"key":"10.1016\/S1574-6526(06)80008-8_bib131","series-title":"Proceedings of the Australian Conference on AI","first-page":"340","article-title":"An evaluation of probabilistic value-ordering heuristics","author":"Vernooy","year":"1999"},{"key":"10.1016\/S1574-6526(06)80008-8_bib132","series-title":"Proceedings of the Eleventh International Conference on Principles and Practice of Constraint Programming","first-page":"712","article-title":"Factor analytic studies of CSP heuristics","author":"Wallace","year":"2005"},{"key":"10.1016\/S1574-6526(06)80008-8_bib133","series-title":"Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence","first-page":"1388","article-title":"Depth-bounded discrepancy search","author":"Walsh","year":"1997"},{"key":"10.1016\/S1574-6526(06)80008-8_bib134","series-title":"Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence","first-page":"1172","article-title":"Search in a small world","author":"Walsh","year":"1999"},{"key":"10.1016\/S1574-6526(06)80008-8_bib135","series-title":"Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence","first-page":"1173","article-title":"Backdoors to typical case complexity","author":"Williams","year":"2003"},{"key":"10.1016\/S1574-6526(06)80008-8_bib136","series-title":"Proceedings of the Eighth National Conference on Artificial Intelligence","first-page":"46","article-title":"Some applications of graph bandwidth to constraint satisfaction problems","author":"Zabih","year":"1990"},{"key":"10.1016\/S1574-6526(06)80008-8_bib137","article-title":"Randomisation and restarts","author":"Zhan","year":"2001","journal-title":"MSc thesis, University of York"},{"key":"10.1016\/S1574-6526(06)80008-8_bib138","series-title":"Proceedings of International Symposium on AI and Math","article-title":"A random jump strategy for combinatorial search","author":"Zhang","year":"2002"},{"key":"10.1016\/S1574-6526(06)80008-8_bib139","series-title":"Proceedings of the International Conference on Computer-Aided Design","first-page":"279","article-title":"Efficient conflict driven learning in a boolean satisfiability solver","author":"Zhang","year":"2001"}],"container-title":["Foundations of Artificial Intelligence","Handbook of Constraint Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1574652606800088?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S1574652606800088?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T02:54:54Z","timestamp":1761620094000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S1574652606800088"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9780444527264"],"references-count":139,"URL":"https:\/\/doi.org\/10.1016\/s1574-6526(06)80008-8","relation":{},"ISSN":["1574-6526"],"issn-type":[{"value":"1574-6526","type":"print"}],"subject":[],"published":{"date-parts":[[2006]]}}}