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.