Pr. Denis Berthier Publishes a New Book on Pattern-Based Solving of Logic Puzzles and Other Constraint Satisfaction Problems

Share Article

Pr. Denis Berthier publishes “Pattern-Based Constraint Satisfaction and Logic Puzzles." He generalizes the pattern-based resolution method introduced in “The Hidden Logic of Sudoku,” to any finite Constraint Satisfaction Problem, with emphasis on finding the simplest “pure logic” solution. It provides a concrete unified perspective of solving various familiar logic puzzles defined by very different types of constraints.

In “Pattern-Based Constraint Satisfaction and Logic Puzzles," different general ways of reasoning with the constraints are formalised by corresponding families of resolution rules, independently of the nature of the constraints. Each of these families carries its own notion of simplicity and it allows to define a “simplest-first” strategy that leads to the simplest solution after exploring only one resolution path.

In order to illustrate as simply as possible the high resolution potential of the method, a large part of “Pattern-Based Constraint Satisfaction and Logic Puzzles” is devoted to showing how it applies to typical popular logic puzzles, with detailed examples. It provides a unified view of how to model and solve them, in spite of the fact that they involve very different types of constraints: symmetric ones in Sudoku, non-symmetric but transitive ones (inequalities) in Futoshiki, topological ones in Map colouring, topological or geometric ones in Numbrix® and Hidato®, and even more complex non-binary arithmetic ones in Kakuro.

Because Sudoku has been for years the most studied case of a finite CSP, it is submitted to a detailed analysis, constituting an advanced level sequel to “The Hidden Logic of Sudoku” with: examples relative to relationships among rules, statistics and classification results for the main rating, scope comparisons for various families of rules and analysis of extremely hard instances.

“Pattern-Based Constraint Satisfaction and Logic Puzzles” is intended both for amateurs of logic puzzles (who may discover new facets of their favorite puzzles and a systematic approach to their solution) and for teachers or students of Logic or AI (who will appreciate the strict logical foundations and the precise definitions, and may use them as a background for projects in AI or computer science).

About the author: Pr. Denis Berthier teaches Logic, Artificial Intelligence and Epistemology of Information Technologies at the French “Institut Mines-Télécom”. Both a researcher and an engineer, he graduated from Ecole Polytechnique, Paris, France. This is his fifth book.

Practical informations: “Pattern-Based Constraint Satisfaction and Logic Puzzles” has been published by Lulu.com (http://www.lulu.com), the world's fastest-growing provider of print-on-demand books.

Share article on social media or email:

View article via:

Pdf Print

Contact Author

Denis Berthier

(+33) 01 45 43 62 15
Email >
Visit website