{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T12:28:25Z","timestamp":1773404905924,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540601050","type":"print"},{"value":"9783540494355","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/bfb0015248","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:40:23Z","timestamp":1131864023000},"page":"254-274","source":"Crossref","is-referenced-by-count":8,"title":["All the needles in a haystack: Can exhaustive search overcome combinatorial chaos?"],"prefix":"10.1007","author":[{"given":"J\u00fcrg","family":"Nievergelt","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ralph","family":"Gasser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabian","family":"M\u00e4ser","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Wirth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,9]]},"reference":[{"key":"16_CR1","first-page":"134","volume-title":"Heuristic Programming in Artificial Intelligence 1: the First Computer Olympiad","author":"J. D. Allen","year":"1989","unstructured":"J. D. Allen, A Note on the Computer Solution of Connect-Four, in: Heuristic Programming in Artificial Intelligence 1: the First Computer Olympiad (eds. D.N.L. Levy and D.F. Beal), Ellis Horwood, Chichester, England. 1989, pp. 134\u2013135."},{"key":"16_CR2","volume-title":"Doctoral dissertation","author":"L.V. Allis","year":"1994","unstructured":"L.V. Allis, Searching for Solutions in Games and Artificial Intelligence, Doctoral dissertation, University of Limburg, Maastricht, (1994)."},{"key":"16_CR3","doi-asserted-by":"crossref","unstructured":"K. Appell and W. Haken, The Solution of the Four-Color-Map Problem, Scientific American (Oct. 1977) 108\u2013121.","DOI":"10.1038\/scientificamerican1077-108"},{"key":"16_CR4","unstructured":"D. Avis and K. Fukuda, Reverse Search for Enumeration, Report, U. Tsukuba. Discrete Applied Math. (1992) (to appear)."},{"key":"16_CR5","volume-title":"Winning Ways for your Mathematical Plays","author":"E. Berlekamp","year":"1982","unstructured":"E. Berlekamp, J.H. Conway and R.K. Guy, Winning Ways for your Mathematical Plays, Academic Press, London, 1982."},{"key":"16_CR6","volume-title":"internal report","author":"J. Culberson","year":"1994","unstructured":"J. Culberson and J. Schaeffer, Efficiently Searching the 15-Puzzle, internal report, University of Alberta, Edmonton, Canada, 1994."},{"key":"16_CR7","first-page":"161","volume-title":"Heuristic Programming in Artificial Intelligence 2: the Second Computer Olympiad","author":"R. Gasser","year":"1990","unstructured":"R. Gasser, Applying Retrograde Analysis to Nine Men's Morris, in: Heuristic Programming in Artificial Intelligence 2: the Second Computer Olympiad (eds. D.N.L. Levy and D.F. Beal), Ellis Horwood, Chichester, England. 1990, pp. 161\u2013173."},{"key":"16_CR8","first-page":"180","volume-title":"Heuristic Programming in Artificial Intelligence 3: the Third Computer Olympiad","author":"R. Gasser","year":"1990","unstructured":"R. Gasser, Endgame Database Compression for Humans and Machines, in: Heuristic Programming in Artificial Intelligence 3: the Third Computer Olympiad (eds. H.J. van den Herik and L.V. Allis), Ellis Horwood, Chichester, England. 1990, pp. 180\u2013191."},{"issue":"5","key":"16_CR9","first-page":"314","volume":"17","author":"R. Gasser","year":"1994","unstructured":"R. Gasser, J. Nievergelt, Es ist entschieden: Das Muehlespiel ist unentschieden, Informatik Spektrum 17:5 (1994) 314\u2013317.","journal-title":"Informatik Spektrum"},{"key":"16_CR10","volume-title":"Doctoral dissertation","author":"R. Gasser","year":"1995","unstructured":"R. Gasser, Harnessing Computational Resources for Efficient Exhaustive Search, Doctoral dissertation, ETH Z\u00fcrich, 1995."},{"key":"16_CR11","unstructured":"R. Gasser, J. Waldvogel, Primes in Intervals of Fixed Length, in preparation (1995)."},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0020-0255(92)90070-O","volume":"63","author":"O. Hansson","year":"1992","unstructured":"O. Hansson, A. Mayer and M. Yung, Criticizing Solutions to Relaxed Models Yields Powerful Admissible Heuristics, Information Sciences 63 (1992) 207\u2013227.","journal-title":"Information Sciences"},{"issue":"1","key":"16_CR13","first-page":"29","volume":"9","author":"H.J. Herik van den","year":"1986","unstructured":"H.J. van den Herik and I.S. Herschberg, A Data Base on Data Bases, ICCA Journal 9:1 (1986) 29.","journal-title":"ICCA Journal"},{"key":"16_CR14","doi-asserted-by":"crossref","unstructured":"J. Horgan, The Death of Proof, Scientific American (1993) 74\u201382.","DOI":"10.1038\/scientificamerican1093-92"},{"key":"16_CR15","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0004-3702(75)90019-3","volume":"6","author":"D. E. Knuth","year":"1975","unstructured":"D. E. Knuth and R. W. Moore, An analysis of Alpha-Beta Pruning, Artificial Intelligence 6 (1975) 293\u2013326.","journal-title":"Artificial Intelligence"},{"key":"16_CR16","first-page":"10","volume":"28","author":"H. Kociemba","year":"1992","unstructured":"H. Kociemba, Close to God's Algorithm, Cubism for Fun 28 (1992) 10\u201313.","journal-title":"Cubism for Fun"},{"key":"16_CR17","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/0004-3702(85)90084-0","volume":"27","author":"R.E. Korf","year":"1985","unstructured":"R.E. Korf, Depth-first Iterative Deepening, An Optimal Admissible Tree Search, Artificial Intelligence 27 (1985) 97\u2013109.","journal-title":"Artificial Intelligence"},{"key":"16_CR18","volume-title":"internal report","author":"R. Lake","year":"1994","unstructured":"R. Lake, J. Schaeffer and P. Lu, Solving Large Retrograde Analysis Problems Using a Network of Workstations, internal report, University of Alberta, Edmonton, Canada, 1994."},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, The Traveling Salesman Problem \u2014 A Guided Tour of Combinatorial Optimization, Wiley, 1985.","DOI":"10.2307\/2582681"},{"key":"16_CR20","doi-asserted-by":"crossref","first-page":"6","DOI":"10.2307\/2002562","volume":"7","author":"D. H. Lehmer","year":"1953","unstructured":"D. H. Lehmer, The Sieve Problem for All-Purpose Computers, Mathematical Tables and Aids to Computation 7 (1953) 6\u201314.","journal-title":"Mathematical Tables and Aids to Computation"},{"key":"16_CR21","unstructured":"D. H. Lehmer, The Machine Tools of Combinatorics, in: E. F. Beckenbach (ed.), Applied Combinatorial Mathematics, Wiley, 1964, Chapter 1, pp. 5\u201331."},{"key":"16_CR22","first-page":"55","volume-title":"Heuristic Programming in Artificial Intelligence 2: the Second Computer Olympiad","author":"D. Levy","year":"1991","unstructured":"D. Levy, Nine Men's Morris, Heuristic Programming in Artificial Intelligence 2: the Second Computer Olympiad (eds. D.N.L. Levy and D.F. Beal), Ellis Horwood, Chichester, England. 1991, 55\u201357."},{"key":"16_CR23","doi-asserted-by":"crossref","unstructured":"J. Nievergelt, Experiments in Computational Heuristics, and their Lessons for Software and Knowledge Engineering, Advances in Computers, Vol 37 (M. Yovits, ed.), Academic Press. 1993, pp. 167\u2013205.","DOI":"10.1016\/S0065-2458(08)60405-2"},{"key":"16_CR24","doi-asserted-by":"crossref","unstructured":"J. Nievergelt, N. Deo, Metric Graphs Elastically Embeddable in the Plane, Information Processing Letters (1995) (to appear).","DOI":"10.1016\/0020-0190(95)00103-J"},{"key":"16_CR25","volume-title":"Secrets of Rook Endings 1992, Secrets of Pawnless Endings 1994, Secrets of Minor Piece Endings","author":"J. Nunn","year":"1995","unstructured":"J. Nunn, Secrets of Rook Endings 1992, Secrets of Pawnless Endings 1994, Secrets of Minor Piece Endings, to appear 1995, Batsford Ltd. UK."},{"issue":"4","key":"16_CR26","first-page":"202","volume":"53","author":"O. Patashnik","year":"1980","unstructured":"O. Patashnik, Qubic: 4\u00d74\u00d74 Tic-Tac-Toe, Mathematics Magazine 53:4 (1980) 202\u2013216.","journal-title":"Mathematics Magazine"},{"key":"16_CR27","volume-title":"Heuristics","author":"J. Pearl","year":"1984","unstructured":"J. Pearl, Heuristics, Addison-Wesley Publ. Comp., Reading, MA, 1984."},{"key":"16_CR28","first-page":"127","volume-title":"Machine Intelligence, Vol. 6","author":"I. Pohl","year":"1971","unstructured":"I. Pohl, Bi-Directional Search, Machine Intelligence, Vol. 6 (eds. B. Metzler and D. Michie), American Elsevier, New York. 1971, pp. 127\u2013140."},{"key":"16_CR29","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/S0747-7171(08)80001-6","volume":"10","author":"D. Ratner","year":"1990","unstructured":"D. Ratner and M. Warmuth, Finding a Shortest Solution for the (N x N)-Extension of the 15-Puzzle is Intractable, J. Symbolic Computation 10 (1990) 111\u2013137.","journal-title":"J. Symbolic Computation"},{"key":"16_CR30","unstructured":"G. Reinelt, \u201cTSPLIB\u201d, available on the Worldwide Web (WWW), http:\/\/www.iwr.uni-heidelberg.de\/iwr\/comopt\/soft\/TSPLIB95\/TSPLIB.html"},{"key":"16_CR31","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/0004-3702(92)90074-8","volume":"53","author":"J. Schaeffer","year":"1992","unstructured":"J. Schaeffer, J. Culberson, N. Treloar, B. Knight, P. Lu and D. Szafron, A World Championship Caliber Checkers Program, Artificial Intelligence 53 (1992) 273\u2013289.","journal-title":"Artificial Intelligence"},{"key":"16_CR32","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/BF00127839","volume":"5","author":"L. Stiller","year":"1991","unstructured":"L. Stiller, Group Graphs and Computational Symmetry on Massively Parallel Architecture, The Journal of Supercomputing 5 (1991) 99\u2013117.","journal-title":"The Journal of Supercomputing"},{"key":"16_CR33","volume-title":"Doctoral thesis","author":"T. Stroehlein","year":"1970","unstructured":"T. Stroehlein, Untersuchungen ueber Kombinatorische Spiele, Doctoral thesis, Technische Hochschule M\u00fcnchen, M\u00fcnchen, 1970."},{"key":"16_CR34","unstructured":"B. Sucrow, Algorithmische und Kombinatorische Untersuchungen zum Puzzle von Sam Loyd, Doctoral thesis, University of Essen, 1992."},{"key":"16_CR35","unstructured":"S. Tay, J. Nievergelt, A Minmax Relationship between Embeddable and Rigid Graphs, in preparation (1995)."},{"issue":"3","key":"16_CR36","first-page":"131","volume":"9","author":"K. Thompson","year":"1986","unstructured":"K. Thompson, Retrograde Analysis of Certain Endgames, ICCA Journal 9:3 (1986) 131\u2013139.","journal-title":"ICCA Journal"},{"issue":"1","key":"16_CR37","first-page":"22","volume":"14","author":"K. Thompson","year":"1991","unstructured":"K. Thompson, Chess Endgames Vol. 1, ICCA Journal 14:1 (1991) 22.","journal-title":"ICCA Journal"},{"issue":"3","key":"16_CR38","first-page":"149","volume":"15","author":"K. Thompson","year":"1992","unstructured":"K. Thompson, Chess Endgames Vol. 2, ICCA Journal 15:3 (1992) 149.","journal-title":"ICCA Journal"},{"key":"16_CR39","volume-title":"Theory of Games and Economic Behavior","author":"J. Neumann von","year":"1953","unstructured":"J. von Neumann, O. Morgenstern, Theory of Games and Economic Behavior, Princeton Univ. Press, Princeton, NJ, 1953."},{"key":"16_CR40","volume-title":"Elements of Combinatorial Computing","author":"M. Wells","year":"1971","unstructured":"M. Wells, Elements of Combinatorial Computing, Pergamon Press, Oxford, 1971."},{"key":"16_CR41","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0095-8956(74)90098-7","volume":"16","author":"R.M. Wilson","year":"1974","unstructured":"R.M. Wilson, Graph Puzzles, Homotopy, and the Alternating Group, J. Combinatorial Theory, Series B: 16 (1974) 86\u201396.","journal-title":"J. Combinatorial Theory, Series B"}],"container-title":["Lecture Notes in Computer Science","Computer Science Today"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0015248","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,10]],"date-time":"2020-04-10T20:49:23Z","timestamp":1586551763000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0015248"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540601050","9783540494355"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/bfb0015248","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]}}}