The New Sudoku Players' Forum

[denis_berthier]

The second edition of my last book "Pattern-Based Constraint Satisfaction and Logic Puzzles" has been published.
It is currently available only on Lulu.com:
http://www.lulu.com/shop/denis-berthier/pattern-based-constraint-satisfaction-and-logic-puzzles-second-edition/paperback/product-22268332.html
It will be available from the main book sellers in a few weeks.

[denis_berthier]

What's new in the 2nd edition ?

Apart from local improvements,
– theorem 7.5 has been extended to mention the universality of g-bivalue-chains[2] or g-whips[2] among patterns based on only two CSP-Variables;
– g2-whips have been introduced as an easy special case of g-whips;
– in the results of chapter 11, all the research for new Sudoku puzzles qualifying as “hardest” has been taken into account; the newly found puzzles do not contradict our T&E(2) and B7B conjectures, thus strongly reinforcing them (indeed, no new puzzle has been found to be in B7B);
– in all the non Sudoku CSPs of Part IV, much larger collections of puzzles (at least 500 for each puzzle type) have been used to test the interfacing with CSP-Rules and to ensure a better selection of examples;
– all the Kakuro examples have been changed and examples with g-whips have been added, showing their power and turning Kakuro into the most striking example (as of now) for g-whips;
– chapter 17 has been added; it deals with Slitherlink, a CSP with both non-binary constraints and a global only-one-loop constraint; it introduces the notion of a macro-rule and it proves that most of the well known Slitherlink resolution rules can be seen as macro-rules in W1 (or Wk for some small k); moreover, it shows how CSP-Rules can be used as an assistant theorem prover;
– a short section about CSP-Rules has been added.

See my webpages http://www.carva.org/denis.berthier/PBCS2 for more details.

[denis_berthier]

I've bought the 1st edition. Is it worth buying the second?

That seems to be a constant for any second edition...

For most buyers of the first edition, probably no. But it all depends on what you are interested in and on what "worth" means for you. Don't worry: sales are not my main source of revenue

As suggested by my previous post, the general framework and theory are unchanged.
Since their first elaboration in "The Hidden Logic of Sudoku" (2007) and their generalisation to any finite Constraint Satisfaction Problem in "Constraint Resolution Theories" (20011), they have been successful to deal with very different types of constraints; so there was no reason to change them.
However, there are many local improvements in the writing. As I intended it to be the final edition, I've been still more cautious than before publishing the first. Of course, all the typos or obscurities found by me or signaled by readers of the first edition have been corrected.

As for the main changes, my previous post was almost complete (more detail is available in the Foreword, available on my website).
There are two main main changes:

- the additions in the Kakuro chapter, with much better examples and (IMO) beautiful examples of g-whips; the first edition gave only the detailed theory of g-labels in Kakuro (which is far from obvious) but lacked an example with g-whips; g-whips[2] are ubiquitous in many puzzles; as (apart from x-wings) they lie in a single sector, they are easy to find. Retrospectively, it was a pity not to have such examples in the first edition.

- the new Slitherlink chapter. Slitherlink is known to be a hard kind of puzzle.
I show that, with a good modeling (basically, a good definition of the CSP-Variables), most of the human-solvable puzzles (based on the hardest ones proposed on the most famous Slitherlink websites) can be solved by short whips, plus a single type of rules (Quasi-Loops of varied lengths) to deal with the global only-one-loop constraint. This is a great success for whips, confirming what was already clear from all the other kinds of puzzles studied in the 1st edition.
I also show how most of the "classical" Slitherlink-specific rules are W-macro-rules, i.e. they can be reduced to sequences of short whips (for most of them, sequences of whips[1]); all the reduction proofs are given; they were obtained semi-automatically, using CSP-Rules as an (assistant) theorem prover - also a new aspect wrt the puzzles studied in the first edition.


One of the constant aspects in my approach is the importance of the proper choice of CSP-Variables and the necessity to have some redundancy between "dual" sets of CSP-Variables.
In Sudoku, it started with my introduction of the Extended Sudoku Board (in HLS1), i.e. of the rc, rn, cn and bn spaces, corresponding respectively to CSP-Variables of types rc (the "natural" ones), rn, cn and bn (the additional ones). They allowed to deal with all the Sudoku symmetries in a uniform way and to automatically extend rules known for the rc-space to their "supersymmetric" counterparts.
In Kakuro, I had to introduce CSP-Variables representing the combinations allowed in each sector.
In Numbrix and Hidato, I had to introduce "dual" CSP-Variables, representing the places a given digit can occupy (dual wrt to the "natural" rc ones, representing the digits that can occupy a given place).
In Slitherlink, given the "natural" (N, H V) CSP-Variables representing the numbers of borders of cells and the horizontal and vertical lines, I had to introduce two additional types of CSP-Variables (P, B) representing the points and cell borders (seen as sets of lines). Some day, I may give an example of a full resolution path in the existing Slitherlink thread.

In particular, is there anything new wrt Sudoku?

Globally, nothing fundamentally new.
Sudoku was the first CSP I dealt with, years ago (HLS1 dates back to June 2007). The sections of the book specifically dealing with Sudoku are the result of continuous improvements and extensions over all those years.
The main new thing is the updating of classifications for the hardest puzzles - the main result being that my (now old) T&E(1) and B7B conjectures still hold for 9x9 puzzles.
Notice that, between the two editions, Sudoku solving has been a relatively dormant topic. No new resolution rule has been found. There have been tentatives to define ratings based on the whole resolution path instead of the usual hardest step, but nothing consistent.

[denis_berthier]

Addendum to PBCS2 : updated classification results.

The BpB classification results reported in the tables of section 11.4.3 of PBCS2 are the same as in the first edition. However, I wrote an additional note:

two and a half years after the version of champagne’s meta-collection used in the above tables, its most recent update [2014/09] as of this writing [2015/07] – the result of an intense and systematic search since the first edition of this book – introduced one more puzzle with SER 11.9, nineteen more with SER 11.8 and 108 more with SER 11.7, but all of them can be solved in B6B or lower.

Is there anything new since PBCS2? Several updates of the hardest database have been published, the last one being dated 2019/05. Between these 2014/09 and 2019/05 databases, a few high SER puzzles have appeared: one with SER 11.9, eight with SER 11.8 and nine with SER 11.7. Only one of them is in B7B. All the rest is in B6B or less.
Here's the only new one in B7B (appeared in the 2015/08 database): 5.6...7...1.3.....8...5.9.....1...2.....8.6.7.....2.4.7...9...6.3...42....5......;11.90;1.20;1.20;OW;2015_08;1744614;22;

Conclusion: my very old T&E(2) conjecture still holds and my much stronger B7B conjecture (first published in PBCS1) still holds, making the T&E(2) conjecture extremely unlikely to ever be disproven for 9x9 Sudokus.

[denis_berthier]

As HLS was Sudoku-specific but PBCS applies to any finite CSP, names of various types of chains had to be changed so as to generalise the Sudoku-specific ones.
At the request of readers of HLS, I also re-introduced in CSP-Rules various types of chains that were called 2D-chains in HLS and that I didn't reproduce in PBCS. As "2D-chain" is related to the grid structure of Sudoku, I replaced this name by "typed-chain". All the names in PBCS are thus simpler and can be applied to any CSP.

Code: Select all

Name in HLS:        Name in PBCS:          Remarks:

xy5-chain           biv-chain-rc[5]   
hxy-uu5-chain       biv-chain-uu[5]        uu = rn, cn or bn
nrc5-chain          biv-chain[5]   

xyz6-chain          z-chain-rc[6]
hxyz-uu6-chain      z-chain-uu[6]          uu = rn, cn or bn
nrcz6-chain         z-chain[6]

xyt-rc6-chain       t-whip-rc[6]   
hxyt-uu6-chain      t-whip-uu[6]           uu = rn, cn or bn
nrct6-chain         t-whip[6]              t-whips are slightly more general than nrct-chains

xyzt-rc8-chain      whip-rc[8]             whips-rc are slightly more general than xyzt-chains
hxyzt-uu8-chain     whip-uu[8]             uu = rn, cn or bn; whips-uu are slightly more general than xyzt-uu-chains
nrczt8-chain        whip[8]                whips are slightly more general than nrczt-chains

[denis_berthier]

All books available as pdfs
All my books and articles related to Pattern-Based CSP solving and its applications to logic games are now freely available as pdfs on ResearchGate: https://www.researchgate.net/profile/Denis_Berthier/research
This includes the following:

Books:

<> Pattern-Based Constraint Satisfaction and Logic Puzzles (Second Edition)
A pure logic, pattern-based perspective of solving finite Constraint Satisfaction Problems, with applications to varied logic puzzles.
Book published by "Lulu.com Publishers" (July 2015)
568 pages, ISBN 978-1-326-35064-2
This is the second, revised edition of "Pattern-Based Constraint Satisfaction and Logic Puzzles" (see below). It also includes an additional chapter dedicated to the Slitherlink puzzle, involving both non-binary and non-local constraints.

<> Pattern-Based Constraint Satisfaction and Logic Puzzles (First Edition)
A pure logic, pattern-based perspective of solving finite Constraint Satisfaction Problems, with applications to varied logic puzzles.
Book published by "Lulu.com Publishers" (Novembre 2012)
484 pages, ISBN 978-1-291-20339-4
This is the second, revised and largely extended edition of "Constraint Resolution Theories".
This book now includes several concrete applications to logic puzzles involving very different types of constraints: Sudoku, N-Queens, Futoshiki, Kakuro (or Cross Sums), Map colouring, Numbrix©, Hidato©, ...

<> Constraint Resolution Theories
A pure logic, pattern-based perspective of solving finite Constraint Satisfaction Problems.
Book published by "Lulu.com Publishers" (October 2011), 312 pages, ISBN 978-1-4478-6888-0

<> The Hidden Logic of Sudoku (Second Edition)
A new conceptual framework for solving Sudoku puzzles with pure logic.
Second, extended edition.
Book published by "Lulu.com Publishers" (Second Edition: November 2007)
416 p., ISBN 978-1-84799-214-7

<> The Hidden Logic of Sudoku (first edition)
A new conceptual framework for solving Sudoku puzzles with pure logic.
Book published by "Lulu.com Publishers" (May 2007)
384 p., ISBN 978-1-84753-472-9


International conferences:

<> "Unbiased Statistics of a CSP - A Controlled-Bias Generator", International Joint Conferences on Computer, Information, Systems Sciences and Engineering (CISSE 09), December 4-12, 2009, Springer. pdf preprint. Published as a chapter of the book Innovations in Computing Sciences and Software Engineering, Khaled Elleithy Editor, pp. 11-17, Springer, 2010, ISBN 97890481911133.

<> "From Constraints to Resolution Rules, Part II: chains, braids, confluence and T&E", International Joint Conferences on Computer, Information, Systems Sciences and Engineering (CISSE 08), December 5-13, 2008, Springer. pdf preprint. Published as a chapter of the book Advanced Techniques in Computing Sciences and Software Engineering, Khaled Elleithy Editor, pp. 171-176, Springer, 2010, ISBN 9789094136599.

<> "From Constraints to Resolution Rules, Part I: Conceptual Framework", International Joint Conferences on Computer, Information, Systems Sciences and Engineering (CISSE 08), December 5-13, 2008, Springer. pdf preprint. Published as a chapter of the book Advanced Techniques in Computing Sciences and Software Engineering, Khaled Elleithy Editor, pp. 165-170, Springer, 2010, ISBN 9789094136599.

[denis_berthier]

Basic User Manual for CSP-Rules-V2.1

As a supplement to the previous list of publications, there is now a "Basic User Manual for CSP-Rules-V2.1" available:

- either as part of the CSP-Rules package on GitHub: https://github.com/denis-berthier/CSP-Rules-V2.1
- or alone on Research Gate: https://www.researchgate.net/publication/343737968_Basic_User_Manual_for_CSP-Rules-V21

In addition to being a user manual, it includes a few things that might have appeared in [PBCS], if I had had the time and the will to write a third edition:

- a few symbolico-graphical representations for whips, partial-whips and t-whips and a few informal definitions easier to understand than the formal ones given in [PBCS]. However, [PBCS] remains the real reference.

- a section on typed-chains, one for their application in Sudoku (thus making the link between [PBCS] and [HLS]) and one in Kakuro. See my already existing posts here about typed-chains.

- the introduction of extended Quasi-Loops in Slitherlink, a very easy to find and use pattern. For already posted examples, see the Slitherlink section of this forum.

[denis_berthier]

In a single sentence, of all the ideas introduced in your books and implemented in CSP-Rules/SudoRules, which would you name as the most innovative

wow, wow: a single sentence? That's much too easy. Indeed, I can answer with a single character. But I'll have to first list some contenders.

Contender #1 : the whole framework of epistemic logic, reducible to intuitionnistic logic, with a formal definition of candidates, resolution rules (with precise conditions sufficient to prove their conclusion generically, once and for all, without any additional ad hoc reasoning in each instantiation), resolution theories, resolution paths within these theories, all this allowing to prove precise results. Not sure it's a main contender, as all the rest can be understood informally without it, but it remains the fundamental theoretical background for all the rest.

Contender #2 : the view of a pattern, especially a chain pattern, as a "static" pattern visible on the current resolution state (i.e. PM); this view was since the beginning and still is in a radical opposition to the classical view of a chain as a "chain of inferences". Of course, a "static" chain pattern can be the support of inferences, but it is not, in and of itself, a chain of inferences. See #3 to #5 for very concrete consequences of this.

Contender #3 : the idea of the z- and t-candidates in chains. However, in isolation, this is not enough to make it the main innovative idea: in a sense, T&E implicitly uses z- and t- candidates; similarly, Sudoku Explainer implicitly uses z- and t- candidates. The innovative idea is that such candidates are not part of my chains. This is justified because z- and t- candidates have no impact on the possibilities of extending a partial-chain. A practical consequence is, any whip/braid... can be drawn exactly as a bivalue-chain with no added, useless complications.

Contender #4 : some specific types of chains: whips, g-whips, braids, g-braids; the precise definition of T&E; the clear relationship between T&E, braids, whips or between gT&E, g-braids, g-whips. Such chains have very specific properties wrt to the vague "contradiction chains [of inferences]" and saying that they can be reduced to such chains is utter nonsense.

Contender #5 : the definition of the complexity of a pattern as the number of CSP-Variables its definition involves. This applies consistently to Subsets, any types of chains, any exotic patterns...
This definition relies on the previous 4 points, it can be formulated in pure logic terms, which guarantees the essential property that the associated ratings are invariant under isomorphism.
Notice that this point is what distinguishes most radically the various ratings defined in [PBCS] from the "number of nodes" used in Sudoku Explainer and other systems based on "(forcing) contradiction chains [of inferences]". This is also what makes any claim that whips or braids can be reduced to such chains or forcing nets utter nonsense.

Contender #6 : the various theorems about several resolution theories having the confluence property. These theorems allow to find the simplest solution after following a single resolution path. This is the most important result in practice and they justify the simplest-first strategy.`

Contender #7 : the introduction of additional CSP-Variables. In Sudoku, this appears as the super-symmetric view, in which all the types of CSP-Variables (rc-, rn-, cn, and bn-) are considered on the same footing.


This is just a quick list of contenders, without thinking too much about it. With more time, I should be able to find more. But let's do with this.
Notice that all these ideas were already in [HLS, 2007].


Now my answer to the question in a single character, as promised : 5.

[denis_berthier]

.
How to start a chain pattern

In [PBCS], all my definitions of chain patterns (except bivalue-chains) start from their target z. There is a good reason for this: it makes the definitions simpler.

Erroneously based on this, some people keep repeating that to start a whip (let's take whips to make what follows definite), one has to "try" all the candidates as possible targets - i.e. that the starting point of finding a whip is a candidate. Nothing could be farther from the real practice of solving puzzles with whips - at least according to what I hear from readers of PBCS who do practice them.

One has to understand that PBCS is not a tutorial on Sudoku solving. It is a logical presentation of a general resolution framework, of various types of resolution rules and of their resolution power. Even if part of the book consists of applying this to a lot of different logical puzzles, by showing how to define them so that they fit in the general framework, it doesn't say much about how to find the chain patterns in real cases.

As the graphico-symbolic representations I recently added to the CSP-Rules Basic User Manual should clearly show, the real starting point for a whip/braid... is a partial-whip[1] (and the real starting point for a g-whip/g-braid... is a partial-g-whip[1]). These two patterns considerably restrict the number of candidates that could be used as potential targets.

As I've always said, whips, g-whips, braids... are patterns in exactly the same sense as Subsets are. They don't make any assumption. They don't start with any hypothesis that some candidate might be a target. They start by observing a well defined pattern (a partial-whip[1] or a partial-g-whip[1]) in the current resolution state, materialised in Sudoku as a PM. (And they continue by identifying a longer pattern...).
And these two starting patterns are almost as simple as the simplest pattern after Singles, a pattern known under various names: whip[1] / intersection / pointing + claiming / alignments.... Indeed, for people who like almost-something patterns, they ARE almost-intersections.
.

[RichardGoodrich]

As HLS was Sudoku-specific but PBCS applies to any finite CSP, names of various types of chains had to be changed so as to generalise the Sudoku-specific ones.
At the request of readers of HLS, I also re-introduced in CSP-Rules various types of chains that were called 2D-chains in HLS and that I didn't reproduce in PBCS. As "2D-chain" is related to the grid structure of Sudoku, I replaced this name by "typed-chain". All the names in PBCS are thus simpler and can be applied to any CSP.

Code: Select all

Name in HLS:        Name in PBCS:          Remarks:

xy5-chain           biv-chain-rc[5]   
hxy-uu5-chain       biv-chain-uu[5]        uu = rn, cn or bn
nrc5-chain          biv-chain[5]   

xyz6-chain          z-chain-rc[6]
hxyz-uu6-chain      z-chain-uu[6]          uu = rn, cn or bn
nrcz6-chain         z-chain[6]

xyt-rc6-chain       t-whip-rc[6]   
hxyt-uu6-chain      t-whip-uu[6]           uu = rn, cn or bn
nrct6-chain         t-whip[6]              t-whips are slightly more general than nrct-chains

xyzt-rc8-chain      whip-rc[8]             whips-rc are slightly more general than xyzt-chains
hxyzt-uu8-chain     whip-uu[8]             uu = rn, cn or bn; whips-uu are slightly more general than xyzt-uu-chains
nrczt8-chain        whip[8]                whips are slightly more general than nrczt-chains

DB, Appreciate having this here in your post. I have seen it somewhere else in your works, but don't remember where?

[denis_berthier]

Hi Richard,
I published it in the Basic User Manual of CSP-Rules ([BUM]).