{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:02:24Z","timestamp":1740135744022,"version":"3.37.3"},"reference-count":33,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2017,8,2]],"date-time":"2017-08-02T00:00:00Z","timestamp":1501632000000},"content-version":"unspecified","delay-in-days":32,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2017,7]]},"abstract":"<jats:p>Magic squares, chess-like problems, cryptarithmetic puzzles, and similar classes of problems have been extensively used to challenge human reasoning capabilities. <jats:italic>Lo Shu<\/jats:italic> magic square can be traced back to 650 B.C., the eight-queens problem was proposed in 1848 by the chess player Max Bazzel TWO \u00d7 TWO = THREE puzzle appeared in <jats:italic>Strand Magazine<\/jats:italic> in 1924. These puzzles are nowadays widely used in constraint programming courses. The first programming language provided with constraint modelling primitives (Sketchpad) has been proposed by the Turing award winner Ivan Sutherland in his PhD thesis (1963). Logemann and Loveland, when implementing the Davis\u2013Putnam procedure (Davis and Putnam 1960) for testing the satisfiability of a propositional formula (SAT), devised an algorithm (Davis\u2013Putnam\u2013Logemann\u2013Loveland (DPLL)) that has become the core of all SAT\/and Answer Set Programming solvers (50 years later). It consists in choosing an un-assigned variable, assigning it a value 0 or 1, propagating the chosen value (unit propagation), and proceeding with the alternative value, if the original assignment leads to a contradiction (backtracking). Some years later Waltz (1975) introduced the notion of domain filtering (arc-consistency-based constraint propagation). With this idea the same DPLL scheme can be used for verifying the satisfiability of a constraint satisfaction problem, where the assignment is no longer 0\/1 and the unit propagation is replaced by constraint propagation. For a detailed history of these early years achievements, we refer the reader to the works by Loveland <jats:italic>et al<\/jats:italic>. (2017), Jaffar and Maher (1994), and Freuder and Mackworth (2006).<\/jats:p>","DOI":"10.1017\/s1471068417000199","type":"journal-article","created":{"date-parts":[[2017,8,2]],"date-time":"2017-08-02T04:05:51Z","timestamp":1501646751000},"page":"359-364","source":"Crossref","is-referenced-by-count":0,"title":["Preface"],"prefix":"10.1017","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2052-8593","authenticated-orcid":false,"given":"AGOSTINO","family":"DOVIER","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2017,8,2]]},"reference":[{"doi-asserted-by":"publisher","key":"S1471068417000199_ref32","DOI":"10.1007\/978-3-319-25883-6"},{"unstructured":"van Maaren, H. and Franco J. 2002. SAT Competition. http:\/\/www.satcompetition.org\/","key":"S1471068417000199_ref30"},{"doi-asserted-by":"crossref","unstructured":"Gebser M. , Kaufmann B. and Schaub T. 2009. The conflict-driven answer set solver clasp: Progress report. In Proc. of 10th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2009, Potsdam, Germany, September 14-18, 2009, E. Erdem , F. Lin , and T. Schaub , Eds. Lecture Notes in Computer Science, vol. 5753. Springer, 509\u2013514.","key":"S1471068417000199_ref10","DOI":"10.1007\/978-3-642-04238-6_50"},{"doi-asserted-by":"publisher","key":"S1471068417000199_ref21","DOI":"10.1023\/A:1018930122475"},{"doi-asserted-by":"publisher","key":"S1471068417000199_ref28","DOI":"10.1609\/aimag.v35i2.2539"},{"unstructured":"Dal Pal\u00f9 A. , Dovier A. , Pontelli E. and Rossi G. 2009. Answer set programming with constraints using lazy grounding. In Proc. of 25th International Conference on Logic Programming, ICLP 2009, Pasadena, CA, USA, July 14\u201317, 2009, P. M. Hill and D. S. Warren , Eds. Lecture Notes in Computer Science, vol. 5649. Springer, 115\u2013129.","key":"S1471068417000199_ref4"},{"doi-asserted-by":"publisher","key":"S1471068417000199_ref24","DOI":"10.1109\/12.769433"},{"doi-asserted-by":"publisher","key":"S1471068417000199_ref15","DOI":"10.1145\/1149114.1149117"},{"doi-asserted-by":"publisher","key":"S1471068417000199_ref3","DOI":"10.1016\/j.artint.2015.09.008"},{"doi-asserted-by":"crossref","unstructured":"Stuckey P. J. 1991. Constructive negation for constraint logic programming. In Proc. of the 6th Annual Symposium on Logic in Computer Science (LICS '91), Amsterdam, The Netherlands, July 15\u201318, 1991. IEEE Computer Society, 328\u2013339.","key":"S1471068417000199_ref26","DOI":"10.1109\/LICS.1991.151657"},{"unstructured":"Lierler Y. and Maratea M. 2004. Cmodels-2: Sat-based answer set solver enhanced to non-tight programs. In Proc. of 7th International Conference on Logic Programming and Nonmonotonic Reasoning, LPNMR 2004, Fort Lauderdale, FL, USA, January 6\u20138, 2004, V. Lifschitz and I. Niemel\u00e4 , Eds. Lecture Notes in Computer Science, vol. 2923. Springer, 346\u2013350.","key":"S1471068417000199_ref16"},{"doi-asserted-by":"publisher","key":"S1471068417000199_ref29","DOI":"10.1145\/1461551.1461591"},{"unstructured":"Simons P. 2000. Extending and implementing the stable model semantics. Doctoral dissertation. Report 58, Helsinki University of Technology.","key":"S1471068417000199_ref25"},{"doi-asserted-by":"crossref","unstructured":"Rao P. , Sagonas K. , Swift T. , Warren D. S. and Freire J. 1997. XSB: A system for efficiently computing well-founded semantics. In Proc. of Logic Programming and Nonmonotonic Reasoning\u2014, LNCS, vol. 1265. Springer Verlag, 431\u2013440.","key":"S1471068417000199_ref23","DOI":"10.1007\/3-540-63255-7_33"},{"doi-asserted-by":"publisher","key":"S1471068417000199_ref2","DOI":"10.1017\/S147106840100103X"},{"key":"S1471068417000199_ref17","first-page":"315","volume-title":"Martin Davis on Computability, Computational Logic, and Mathematical Foundations","author":"Loveland","year":"2017"},{"doi-asserted-by":"publisher","key":"S1471068417000199_ref19","DOI":"10.1007\/s10472-009-9116-y"},{"doi-asserted-by":"publisher","key":"S1471068417000199_ref5","DOI":"10.1145\/321033.321034"},{"doi-asserted-by":"publisher","key":"S1471068417000199_ref14","DOI":"10.1016\/0743-1066(94)90033-7"},{"key":"S1471068417000199_ref13","first-page":"441","volume-title":"Logic Programming: Functions, Relations, and Equations","author":"Jaffar","year":"1986"},{"volume-title":"Foundations of Deductive Databases and Logic Programming","year":"1988","author":"Minker","key":"S1471068417000199_ref20"},{"key":"S1471068417000199_ref31","first-page":"19","volume-title":"The Psychology of Computer Vision","author":"Waltz","year":"1975"},{"unstructured":"Baselice S. , Bonatti P. and Gelfond M. 2015. Proc. of the 21st International Conference on Logic Programming, M. Gabbrielli and G. Gupta , Eds. Lecture Notes in Computer Science, vol. 3668, 52\u201366.","key":"S1471068417000199_ref1"},{"unstructured":"9. Dovier A., Formisano A. and Pontelli E. 2005. A comparison of CLP","key":"#cr-split#-S1471068417000199_ref6.1"},{"unstructured":"10. (FD) and ASP solutions to NP-complete problems. In Proc. of 21st International Conference on Logic Programming, ICLP 2005, Sitges, Spain, October 2-5, 2005, M. Gabbrielli and G. Gupta, Eds. Lecture Notes in Computer Science, vol. 3668. Springer, 67-82.","key":"#cr-split#-S1471068417000199_ref6.2"},{"doi-asserted-by":"publisher","key":"S1471068417000199_ref8","DOI":"10.1007\/BF01536399"},{"doi-asserted-by":"crossref","unstructured":"Jaffar J. and Lassez J. 1987. Constraint logic programming. In Conference Record of the 14th Annual ACM Symposium on Principles of Programming Languages, Munich, Germany, January 21\u201323, 1987. ACM, 111\u2013119.","key":"S1471068417000199_ref12","DOI":"10.1145\/41625.41635"},{"unstructured":"Stuckey P. J. 2010. Lazy clause generation: Combining the power of SAT and CP (and MIP?) solving. In Proc. of Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, 7th International Conference, CPAIOR 2010, Bologna, Italy, June 14\u201318, 2010, A. Lodi , M. Milano , and P. Toth , Eds. Lecture Notes in Computer Science, vol. 6140. Springer, 5\u20139.","key":"S1471068417000199_ref27"},{"doi-asserted-by":"publisher","key":"S1471068417000199_ref7","DOI":"10.1016\/S0020-0190(00)00046-6"},{"unstructured":"Gelfond M. and Lifschitz V. 1988. The stable model semantics for logic programming. In Proc. of the 5th International Conference and Symposium on Logic Programming, Seattle, Washington, August 15\u201319, 1988 (2 Volumes), R. A. Kowalski and K. A. Bowen , Eds. MIT press, 1070\u20131080.","key":"S1471068417000199_ref11"},{"doi-asserted-by":"publisher","key":"S1471068417000199_ref9","DOI":"10.1016\/S1574-6526(06)80006-4"},{"volume-title":"The Logic Programming Paradigm: a 25-Year Perspective","year":"1999","author":"Marek","key":"S1471068417000199_ref18"},{"doi-asserted-by":"publisher","key":"S1471068417000199_ref22","DOI":"10.1145\/1217856.1217859"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068417000199","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,17]],"date-time":"2019-04-17T16:06:58Z","timestamp":1555517218000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068417000199\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,7]]}},"alternative-id":["S1471068417000199"],"URL":"https:\/\/doi.org\/10.1017\/s1471068417000199","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"type":"print","value":"1471-0684"},{"type":"electronic","value":"1475-3081"}],"subject":[],"published":{"date-parts":[[2017,7]]}}}