Pascal van Hentenryck
Abstract
Logic programming is a convenient tool for stating combinatorial problems due to its nondeterminism and its relational form. It is not surprising that simple and declarative programs can be written for problems like mastermind. However, due to their search strategy, logic languages are also very inefficient for solving the natural formulation of problems. Moving away from this natural formulation leads to much programming effort and to less modifable and extensible programs. This paper shows, on the mastermind example, that it is possible to write very declarative programs which will be executed efficiently by an extended logic programming language. The key idea is to embed consistency techniques inside logic programming. Within this approach, constraints are used actively to prune the search space in an "a priori" way instead of the passive way (for testing values) of usual languages. The resulting program outperforms all the proposed algorithms and achieves a speed-up of 40 over Shapiro's program in the average and a speed-up of 72 on Powers' benchmark.
- Clark, K.L. and Mc Cabe, F. The control facilities of IC-PROLOG. In D. Mitchie, Ed., Expert system in the micro electronic age, Edinburgh University Press, 1979, pp. 122-149.Google Scholar
- Colmerauer, A., Kanoui, H. and Van Caneghem, M. "Prolog, bases theoriques et developments actuels." T.S.I. (Techniques et Sciences Informatiques). 2, 4 (1983), 271-311.Google Scholar
- Dincbas, M. and Lepape, J-P. Metacontrol of Logic Programs in METALOG. Proceedings of the International Conference on Fifth Generation Computer Systems (FGCS'84), ICOT, Tokyo, Japan, November, 1984, pp. 361-370.Google Scholar
- Dincbas, M., Simonis, H. and Van Hentenryck P. Extending Equation Solving and Constraint Handling in Logic Programming. Colloquium on Resolution of equations in Algebraic Structures, Texas, May, 1987.Google Scholar
- Gallaire, H. Logic programming further developments. IEEE Symposium on Logic Programming, Boston, July, 1985, pp. 88-99. Invited paper.Google Scholar
- Haralick, R.M. and Elliot, G.L. "Increasing tree search efficiency for constraint satisfaction problems.". AI 14 (1980), 263-313.Google Scholar
- Mackworth, A.K. "Consistency in network of relations". AI 8, 1 (1977), 99-118.Google Scholar
- Naish, L. Negation and Control in Prolog. Ph.D. Th., University of Melbourne, Australia, 1985.Google Scholar
- Powers, D. "Plying Mastermind More Logically". Sigart Newsletter 89 (1984). 28-32. Google ScholarDigital Library
- Shapiro, E. "Playing Mastermind Logically". Sigart 85 (1983), 28-29. Google ScholarDigital Library
- Sterling, L. and Shapiro, E. The Art of Prolog: Advanced Programming Techniques. MIT Press, 1986. Google ScholarDigital Library
- van Emden, M.H. RELATIONAL PROGRAMMING illustrated by a program for the game of mastermind. CS-78-48, Department of Computer Science, University of Waterloo, Ontario, Canada, 1978.Google Scholar
- Van Hentenryck, P. and Dincbas, M. Domains in Logic Programming. Proceedings of the National Conference on Al (AAAI-86), Philadelphia, USA, August 1986, pp. 759-765.Google Scholar
- Van Hentenryck, P. and Dincbas, M. Forward Checking in Logic Programming. Fourth International Conference on Logic Programming. Melbourne, Australia, May, 1987.Google Scholar
- Van Hentenryck, P. A Framework for Consistency Techniques in Logic Programming. IJCAI-87, Milan, Italy, August, 1987.Google Scholar
- Van Hentenryck, P. Consistency Techniques in Logic Programming. Ph.D. Th., University of Namur (Belgium), July 1987.Google Scholar
Index Terms
- A constraint approach to mastermind in logic programming
Recommendations
Negation and Constraint Logic Programming
Almost all constraint logic programming systems include negation, yet nowhere has a sound operational model for negation in CLP been discussed. The SLDNF approach of only allowing ground negative subgoals to execute is very restrictive in constraint ...
Coinductive constraint logic programming
FLOPS'12: Proceedings of the 11th international conference on Functional and Logic ProgrammingConstraint logic programming (CLP) has been proposed as a declarative paradigm for merging constraint solving and logic programming. Recently, coinductive logic programming has been proposed as a powerful extension of logic programming for handling (...
Constraint Logic Programming with Hereditary Harrop formulas
Constraint Logic Programming (CLP) and Hereditary Harrop formulas (HH) are two well known ways to enhance the expressivity of Horn clauses. In this paper, we present a novel combination of these two approaches. We show how to enrich the syntax and proof ...
Comments