Pattern-Based Constraint Satisfaction and Logic Puzzles
This is to announce the publication of my new book "Pattern-Based Constraint Satisfaction and Logic Puzzles
This book develops a pure logic, pattern-based perspective of solving the finite Constraint Satisfaction Problem (CSP), with emphasis on finding the "simplest" solution.
It is the second, revised and largely extended edition of my previous book, "Constraint Resolution Theories
". It relies on the same generalization to any finite Constraint Satisfaction Problem of the rules I first developed for Sudoku in "The Hidden Logic of Sudoku
". As always in my approach, different ways of reasoning with the constraints are formalised by various families of "resolution rules", each of them carrying its own notion of simplicity.
A large part of this book is devoted to illustrating the power of the approach by applying it to various popular logic puzzles. It provides a unified view of how to model and solve them, even though they involve very different types of constraints: obvious symmetric ones in Sudoku
, non-symmetric but transitive ones (inequalities) in Futoshiki
, topological ones in Map colouring
, either topological or geometric ones in Numbrix
, and even much more complex non-binary arithmetic ones in Kakuro
. It also shows that the most familiar techniques for these puzzles can indeed be understood as mere application-specific presentations of the general rules.
Sudoku is used as the main example throughout the book, making it also an advanced level sequel to "The Hidden Logic of Sudoku
", with: many examples of relationships among different rules and of exceptional situations; comparisons of the resolution potential of various families of rules; detailed statistics of puzzles hardness; analysis of extreme instances, i.e. of instances in T&E(2), and special rules for them.
More information about the book can be obtained at http://www.carva.org/denis.berthier/PBCS
In particular, you can download pdf versions of the Foreword, the Introduction and the Final Remarks.
The book is currently available only with my usual online publisher: Lulu.com (http://www.lulu.com/shop/denis-berthier/pattern-based-constraint-satisfaction-and-logic-puzzles/paperback/product-20516172.html
), but it should be available on Amazon and other distributors in a few weeks.
What I plan to do in this thread is to highlight (shortly - I don't plan to re-write the book) the main advances I made since the publication of The Hidden Logic of Sudoku (Second Edition)