A constraint approach to mastermind in logic programming

✍ Scribed by van Hentenryck, Pascal

• Book ID: 126953031
• Publisher: Association for Computing Machinery
• Year: 1988
• Weight: 490 KB
• Volume: 103
• Category: Article
• ISSN: 0163-5719
• DOI: 10.1145/44418.44421

✦ Synopsis

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.