{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:34:38Z","timestamp":1786980878648,"version":"build-2736575974"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,9,22]],"date-time":"2012-09-22T00:00:00Z","timestamp":1348272000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Constraints"],"published-print":{"date-parts":[[2013,1]]},"DOI":"10.1007\/s10601-012-9128-9","type":"journal-article","created":{"date-parts":[[2012,9,21]],"date-time":"2012-09-21T14:25:04Z","timestamp":1348237504000},"page":"7-37","source":"Crossref","is-referenced-by-count":6,"title":["On the hardness of solving edge matching puzzles as SAT or CSP problems"],"prefix":"10.1007","volume":"18","author":[{"given":"Carlos","family":"Ans\u00f3tegui","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ram\u00f3n","family":"B\u00e9jar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C\u00e8sar","family":"Fern\u00e1ndez","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carles","family":"Mateu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,9,22]]},"reference":[{"key":"9128_CR1","unstructured":"Achlioptas, D., Gomes, C., Kautz, H., Selman, B. (2000). Generating satisfiable problem instances. In Proceedings of the AAAI 2000 (pp. 256\u2013261). AAAI Press\/The MIT Press."},{"key":"9128_CR2","doi-asserted-by":"crossref","first-page":"623","DOI":"10.1613\/jair.1681","volume":"24","author":"D Achlioptas","year":"2005","unstructured":"Achlioptas, D., Jia, H., Moore, C. (2005). Hiding truth assignments: two are better than one. Journal of Artifical Intelligence Research, 24, 623\u2013639.","journal-title":"Journal of Artifical Intelligence Research"},{"issue":"7043","key":"9128_CR3","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1038\/nature03602","volume":"435","author":"D Achlioptas","year":"2005","unstructured":"Achlioptas, D., Naor, A., Peres, Y. (2005). Rigorous location of phase transitions in hard optimization problems. Nature, 435(7043), 759.","journal-title":"Nature"},{"issue":"4","key":"9128_CR4","doi-asserted-by":"crossref","first-page":"947","DOI":"10.1090\/S0894-0347-04-00464-3","volume":"17","author":"D Achlioptas","year":"2004","unstructured":"Achlioptas, D., & Peres, Y. (2004). The threshold for random k-sat is $2^k\\log{2}-\\mathcal{O}(k)$ . Journal of the American Mathematical Society, 17(4), 947\u2013973.","journal-title":"Journal of the American Mathematical Society"},{"key":"9128_CR5","unstructured":"Alon, N., & Spencer, J.H. (2000). The probabilistic method (2nd ed.). Discrete Mathematics and Optimization. Wiley Inter-Science."},{"key":"9128_CR6","unstructured":"Ans\u00f3tegui, C., B\u00e9jar, R., Fern\u00e1ndez, C., Gomes, C., Mateu, C. (2011). The impact of balance in a highly structured problem domain. In Proceedings of the AAAI 2006 (pp. 438\u2013443). AAAI Press\/The MIT Press."},{"issue":"5","key":"9128_CR7","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/s10732-010-9146-y","volume":"17","author":"C Ans\u00f3tegui","year":"2011","unstructured":"Ans\u00f3tegui, C., B\u00e9jar, R., Fern\u00e1ndez, C., Gomes, C., Mateu, C. (2011). Generating highly balanced sudoku problems as hard problems. Journal of Heuristics, 17(5), 589\u2013614. doi: 10.1007\/s10732-010-9146-y .","journal-title":"Journal of Heuristics"},{"key":"9128_CR8","unstructured":"Ans\u00f3tegui, C., B\u00e9jar, R., Fern\u00e0ndez, C., Mateu, C. (2008). Edge matching puzzles as hard SAT\/CSP benchmarks. In CP \u201908: proceedings of the 14th international conference on principles and practice of constraint programming. Lecture notes in computer science (Vol. 5202, pp. 560\u2013565). Sydney, Australia: Springer."},{"key":"9128_CR9","first-page":"99","volume":"184","author":"C Ans\u00f3tegui","year":"2008","unstructured":"Ans\u00f3tegui, C., B\u00e9jar, R., Fern\u00e1ndez, C., Mateu, C. (2008). How hard is a commercial puzzle: the Eternity II challenge. Frontiers in Artificial Intelligence and Applications - Artificial Intelligence Research and Development, 184, 99\u2013108.","journal-title":"Frontiers in Artificial Intelligence and Applications - Artificial Intelligence Research and Development"},{"key":"9128_CR10","unstructured":"Ans\u00f3tegui, C., del Val, A., Dot\u00fa, I., Fern\u00e1ndez, C., Many\u00e0, F. (2004). Modelling choices in quasigroup completion: SAT vs CSP. In Proceedings of the AAAI 2004. AAAI Press\/The MIT Press."},{"key":"9128_CR11","doi-asserted-by":"crossref","unstructured":"Ans\u00f3tegui, C., & Many\u00e0, F. (2005). Mapping many-valued CNF formulas to Boolean CNF formulas. In Proceedings of the international symposia on multiple-valued logic (pp. 290\u2013295).","DOI":"10.1109\/ISMVL.2005.23"},{"key":"9128_CR12","doi-asserted-by":"crossref","unstructured":"Atserias, A., Bulatov, A.A., Dalmau, V. (2007). On the power of k-consistency. In 34th International Colloquium Automata, Languages and Programming, ICALP 2007. of Lecture notes in computer science (Vol. 4596, pp. 279\u2013290). Springer.","DOI":"10.1007\/978-3-540-73420-8_26"},{"key":"9128_CR13","doi-asserted-by":"crossref","unstructured":"B\u00e9jar, R., Fern\u00e0ndez, C., Mateu, C., Pascual, N. (2009). Bounding the phase transition on edge matching puzzles. IEEE International Symposium on Multiple-Valued Logic (pp. 80\u201385).","DOI":"10.1109\/ISMVL.2009.55"},{"key":"9128_CR14","first-page":"36","volume":"3","author":"T Benoist","year":"2008","unstructured":"Benoist, T., & Bourreau, E. (2008). Fast global filtering for eternity II. Constraint Programming Letters, 3, 36\u201349.","journal-title":"Constraint Programming Letters"},{"key":"9128_CR15","doi-asserted-by":"crossref","unstructured":"Bessi\u00e8re, C., & R\u00e9gin, J.-C. (1996). MAC and combined heuristics: two reasons to forsake FC (and CBJ?) on hard problems. In Principles and practice of constraint programming (pp. 61\u201375).","DOI":"10.1007\/3-540-61551-2_66"},{"issue":"2\u20133","key":"9128_CR16","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/s10601-006-8059-8","volume":"11","author":"DA Cohen","year":"2006","unstructured":"Cohen, D.A., Jeavons, P., Jefferson, C., Petrie, K.E., Smith, B.M. (2006). Symmetry definitions for constraint satisfaction problems. Constraints, 11(2\u20133), 115\u2013137.","journal-title":"Constraints"},{"key":"9128_CR17","unstructured":"Dechter, R. (2003). Constraint processing. Morgan Kaufmann."},{"issue":"s1","key":"9128_CR18","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s00373-007-0713-4","volume":"23","author":"ED Demaine","year":"2007","unstructured":"Demaine, E.D., & Demaine, M.L. (2007). Jigsaw puzzles, edge matching, and polyomino packing: connections and complexity. Graphs and Combinatorics, 23(s1), 195.","journal-title":"Graphs and Combinatorics"},{"key":"9128_CR19","doi-asserted-by":"crossref","unstructured":"E\u00e9n, N., & Biere, A. (2005). Effective preprocessing in SAT through variable and clause elimination. In Proceedings of SAT 2005 (pp. 61\u201375).","DOI":"10.1007\/11499107_5"},{"key":"9128_CR20","unstructured":"E\u00e9n, N., & S\u00f6rensson, N. (2003). An extensible SAT-solver. In Proceedings of SAT 2003. Lecture notes in computer science (Vol. 2919, pp. 502\u2013518). Springer."},{"key":"9128_CR21","first-page":"1","volume":"2","author":"N E\u00e9n","year":"2006","unstructured":"E\u00e9n, N., & S\u00f6rensson, N. (2006). Translating pseudo-Boolean constraints into SAT. Journal of Satisfiability, 2, 1\u201326.","journal-title":"Journal of Satisfiability"},{"key":"9128_CR22","first-page":"98","volume-title":"Proceedings of the 2006 conference on ECAI 2006: 17th European conference on artificial intelligence, 29 Aug\u20131 Sept 2006, Riva del Garda, Italy","author":"IP Gent","year":"2006","unstructured":"Gent, I.P., Jefferson, C., Miguel, I. (2006). MINION: a fast, scalable, constraint solver. In Proceedings of the 2006 conference on ECAI 2006: 17th European conference on artificial intelligence, 29 Aug\u20131 Sept 2006, Riva del Garda, Italy (pp. 98\u2013102). Amsterdam, The Netherlands, The Netherlands: IOS Press."},{"key":"9128_CR23","doi-asserted-by":"crossref","unstructured":"Gent, I.P., Jefferson, C., Miguel, I. (2006). Watched literals for constraint propagation in Minion. In Principles and practice of constraint programming (pp. 182\u2013197).","DOI":"10.1007\/11889205_15"},{"issue":"1\u20134","key":"9128_CR24","doi-asserted-by":"crossref","first-page":"27","DOI":"10.3233\/SAT190015","volume":"2","author":"H Haanp\u00e4\u00e4","year":"2006","unstructured":"Haanp\u00e4\u00e4, H., J\u00e4rvisalo, M., Kaski, P., Niemel\u00e4, I. (2006). Hard satisfiable clause sets for benchmarking equivalence reasoning techniques. Journal on Satisfiability, Boolean Modeling and Computation, 2(1\u20134), 27\u201346.","journal-title":"Journal on Satisfiability, Boolean Modeling and Computation"},{"key":"9128_CR25","first-page":"263","volume":"14","author":"RM Haralick","year":"1980","unstructured":"Haralick, R.M., & Elliott, G.L. (1980). Increasing tree search efficiency for constraint satisfaction problems. AI Journal, 14, 263\u2013313.","journal-title":"AI Journal"},{"key":"9128_CR26","unstructured":"J\u00e4rvisalo, M. (2006). Further investigations into regular XORSAT. In Proceedings of the AAAI 2006. AAAI Press\/The MIT Press."},{"key":"9128_CR27","unstructured":"Li, C.M., & Anbulagan, A. (1997). Heuristics based on unit propagation for satisfiability problems. In Proceedings of the International Joint Conference on Artif icial Intelligence, IJCAI 97 (pp. 366\u2013371). Morgan Kaufmann."},{"key":"9128_CR28","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1038\/22055","volume":"400","author":"R Monasson","year":"1999","unstructured":"Monasson, R., Zecchinna, R., Kirkpatrick, S., Selman, B., Troyansky, L. (1999). Determining computational complexity from characteristic phase transitions. Nature, 400, 133\u2013137.","journal-title":"Nature"},{"key":"9128_CR29","first-page":"81","volume":"81","author":"P Prosser","year":"1996","unstructured":"Prosser, P. (1996). An empirical study of phase transitions in binary constraint satisfaction problems. AI Journal, 81, 81\u2013109.","journal-title":"AI Journal"},{"key":"9128_CR30","unstructured":"R\u00e9gin, J.-C. (1994). A filtering algorithm for constraints of difference in CSPs. In Proceedings of the AAAI 1994 (pp. 362\u2013367). AAAI Press\/The MIT Press."},{"key":"9128_CR31","unstructured":"R\u00e9gin, J.-C. (1999). The symmetric alldiff constraint. In Proceedings of the sixteenth International Joint Conference on Artificial Intelligence, IJCAI 99 (pp. 420\u2013425). Morgan Kaufmann."},{"key":"9128_CR32","unstructured":"Schaus, P., & Deville, Y. (2008). Hybridization of CP and VLNS for Eternity II. In Quatrime Journes Francophones de Programmation par Contraintes (JFPC\u201908)."},{"key":"9128_CR33","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0004-3702(95)00052-6","volume":"81","author":"B Smith","year":"1996","unstructured":"Smith, B., & Dyer, M. (1996). Locating the phase transition in binary constraint satisfaction problems. Artificial Intelligence, 81, 155\u2013181.","journal-title":"Artificial Intelligence"},{"issue":"5","key":"9128_CR34","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.ipl.2006.04.010","volume":"99","author":"Y Takenaga","year":"2006","unstructured":"Takenaga, Y., & Walsh, T. (2006). Tetravex is NP-complete. Information Processing Letters, 99(5), 171\u2013174.","journal-title":"Information Processing Letters"},{"key":"9128_CR35","unstructured":"Williams, R., Gomes, C.P., Selman, B. (2003). Backdoors to typical case complexity. In IJCAI (pp. 1173\u20131178)."},{"key":"9128_CR36","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1613\/jair.696","volume":"12","author":"K Xu","year":"2000","unstructured":"Xu, K., & Li, W. (2000). Exact phase transition in random constraint satisfaction problems. Journal of Artificial Intelligence Research, 12, 93\u2013103.","journal-title":"Journal of Artificial Intelligence Research"}],"container-title":["Constraints"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-012-9128-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10601-012-9128-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10601-012-9128-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T22:47:20Z","timestamp":1594680440000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10601-012-9128-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,9,22]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,1]]}},"alternative-id":["9128"],"URL":"https:\/\/doi.org\/10.1007\/s10601-012-9128-9","relation":{},"ISSN":["1383-7133","1572-9354"],"issn-type":[{"value":"1383-7133","type":"print"},{"value":"1572-9354","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,9,22]]}}}