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.