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.

[Edit] Note: the first edition was announced here: http://forum.enjoysudoku.com/pattern-based-constraint-satisfaction-and-logic-puzzles-t30774.html
[Edit2] Note: the third edition is announced here: http://forum.enjoysudoku.com/pattern-based-constraint-satisfaction-2nd-edition-t32567-13.html

[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]).

[denis_berthier]

.
STATISTICAL COMPARISONS OF VARIOUS RATINGS

In 10,000 puzzles tested, only 20 (0.2%) have different W and B ratings. Moreover, the maximum length of whips in a single resolution path using only loopless whips and obtained by the “simplest first” strategy is a good approximation of both the W and B ratings.

This post will make this old result more precise and extend it to more ratings.
As in the above results of [PBCS], whips and g-whips are supposed to be loopless (i.e. simpler than if not — which makes the results still more interesting). [Loopless would be a meaningless condition for braids.]

The collection used for the following results is made of the first 21,375 puzzles in my controlled-bias collection of 5,926,343 minimal puzzles. It is itself a controlled-bias collection. It is thus less biased than the top-down collection used for the comparison in [PBCS]. But the same results hold.

Details (in particular, the detailed lists of all the ratings and the detailed differences between them) can be found in the Examples/Sudoku-examples/cbg-000 folder of CSP-Rules-V2.1 on GitHub (https://github.com/denis-berthier/CSP-Rules-V2.1).
This cbg-000 collection can then become a reference for any quick statistical comparison with any other ratings.
(The full collection of 5,926,343 minimal controlled-bias puzzles is also on GitHub — https://github.com/denis-berthier/Controlled-bias_Sudoku_generator_and_collection — but it has only the W ratings).


1) COMPARISONS INVOLVING NO SUBSETS:

W vs B:
Note that one must always have W ≥ B
In reality, there are only 65 differences, i.e. a proportion of 0,30% differences.
And there are only 4 cases with difference > 1 (0,019%) and none with difference > 2.


W vs gW
Note that one must always have W ≥ gW
In reality, there are only 48 differences, i.e. a proportion of 0,22% differences.
And there are only 5 cases with difference > 1 (0,023%) and only one with difference > 2.


W vs FW:
Note that one must always have W ≥ FW
In reality, there are only 7 differences, i.e. a proportion of 0,03% differences.
And there is only 1 case with difference 2 (0,005%) and no case with difference > 2.



2) COMPARISONS INVOLVING SUBSETS BUT NO FINNED FISH

W vs S+W:
Note that one must always have W ≥ S+W
In reality, there are only 18 differences, i.e. a proportion of 0,084% differences
And there are only 2 cases with difference >1 (0,009%) and only one with difference > 2.


gW vs S+gW:
Note that one must always have gW ≥ S+gW
In reality, there are only 16 differences, i.e. a proportion of 0,075% differences
And there is only 1 case with difference > 1 (0,0047%) and none with difference > 2.

The differences are the same as before (W vs S+W), minus two cases (#41 and #2862).
For all these differences (i.e. not including the above 2), W = gW. The 'W vs gW' and 'W vs S+W' differences are "quasi-independent".


S+W vs gW:

Note that there is no a priori relation between S+W and gW.
In reality, there are only 62 differences, i.e. a proportion of 0,29% differences.
And there are only 6 cases with difference > 1 (0,028%) and only 2 with difference > 2.


S+W vs S+gW:
Note that one must always have S+W ≥ S+gW
In reality, there are only 47 differences, i.e. a proportion of 0,22% differences
And there are only 4 cases with difference > 1 (0,019%) and no case with difference > 2.


W vs S+gW:
Note that one must always have W ≥ S+gW
In reality, there are only 62 differences, i.e. a proportion of 0,29% differences.
Notice that delta(W, gW) = 48, delta(gW, S+gW) = 16 and delta(W, S+gW) = 62.
delta(W, S+gW) is almost equal to delta(W, gW) + delta(gW, S+gW) = 64.
This confirms the quasi-independence of the S and g differences.

There are only 6 cases with difference > 1 (0,028%) and none with difference > 2.



3) COMPARISONS INVOLVING SUBSETS AND FINNED FISH

S+W vs SFin+W:
Note that one must always have S+W ≥ SFin+W
In reality, there are no differences.


S+gW vs SFin+gW:
Note that one must always have S+gW ≥ SFin+gW
In reality, there are no differences.



4) WARNING

As any statistical results, the above ones are valid only in random collections with the same distribution as the controlled-bias one. I think they can be extended with little change to any unbiased collection.
However, I have proven in [PBCS] that there are 2.5477*10^25 non isomorphic minimal Sudoku puzzles (with 0.065% relative error) — a huge number that leaves a lot of possibilities to find exceptional cases wrt any statistical result.
In particular, it is not difficult to find handmade collections of puzzles that have lots of Subsets and for which the proportion of differing W and S+W ratings is larger.
Similarly, it is not difficult to find collections of puzzles with much larger mean difficulty than in a random one. The longer the length of whips/braids necessary to solve a puzzle, the more the proportion of differing W and B ratings will grow.
Finally, it is not difficult to find exceptional puzzles where the difference between the ratings is much larger than 2.

[denis_berthier]

.
ADDITIONAL STATISTICAL COMPARISONS OF VARIOUS RATINGS

4) COMPARISIONS INVOLVING EXOTIC PATTERNS
Here, exotic pattern means generic ones (oddagon) and Sudoku-specific ones (sk-loop, J-Exocet)

W vs Exo+W:
Note that one must always have W ≥ Exo+W
In reality, there are no differences. None of the above exotic patterns changes anything in the ratings.



5) COMPARISONS INVOLVING UNIQUENESS
Here, Uniqueness means UR1, UR2, UR2b, UR3, UR4 and BUG+1 (see e.g. Hodoku for the definitions).
First notice that, due to non-confluence of the rules for Uniqueness, they have to be applied as soon as they are available. This gives them the best possible chances of appearing in a resolution path - probably much more than their complexity should really allow.

But their rating doesn't have to be 0.
For URs, it is naturally 4 (because they rely on 4 CSP-Variables).
For BUG+1, it's more arbitrary, as it can rely on any number of bivalue cells, but I shall consider it uses at least 5 cells (a clear under-rating in most cases). In all the cases in this cbg000 file, it is applied after W4 and it appears in the U+W ratings file as 4+BUG.

W vs U+W:
Note that one must always have W ≥ U+W
In reality, there are only 8 differences, i.e. a proportion of 0,27% differences.
There are only 3 cases with difference > 1 (0,014%) and 2 cases with difference > 2 (0,0094%).

I've proposed case #4918 (W10; U+W4) in the Puzzles section: http://forum.enjoysudoku.com/cbg-4918-8-3-t39022.html

[denis_berthier]

.
The third edition of my book "Pattern-Based Constraint Satisfaction and Logic Puzzles" has been published.
As usual, there is a softcover version:
https://www.lulu.com/en/en/shop/denis-berthier/pattern-based-constraint-satisfaction-and-logic-puzzles-third-edition/paperback/product-q7269p.html?page=1&pageSize=4
But, at the request of a few readers who wanted to buy it as a gift, I also made a hardcover version:
https://www.lulu.com/en/en/shop/denis-berthier/pattern-based-constraint-satisfaction-and-logic-puzzles/hardcover/product-gkv2rd.html?page=1&pageSize=4

The book is currently available only on Lulu Press, but will soon be available from the main vendors (except the hardcover version on Amazon).

What’s new in this Third Edition
As always in any new edition, a few typos are corrected and there are a few local changes intended to make the text clearer when necessary.
A change that is not inside the book itself but is worth noting is the existence of a public version of the companion software: CSP-Rules V2.1, now freely available on GitHub, together with a detailed Basic User Manual for CSP-Rules-V2.1. The reader of the present book can now check all the resolution paths and try alternative ones by making his own selections of resolution rules.
However, the main changes in this third edition are additions. As I write in section 0.7:

– section 1.5.2 adds a few remarks on our view of AI and constructive modelling; this is of course related to our original modelling approach of Sudoku and to the way we extended its basic xy-chains into generic whips, braids and other chain rules;
– section 4.6 is split from the previous section and it adds the notion of “blocked” behaviour (as a local micro-strategy) for resolution rules;
– section 5.12 [Appendix 5A, “Typed chains and the 2D-chains of HLS”] re-introduces in the general formalism of the present book the 2D-chains formerly introduced in HLS (in the restricted context of Sudoku); they were not repeated in PBCS1 or PBCS2 because we had no purpose of including all that was already published in HLS; but many readers wanted to know how they fitted in the general framework of PBCS; a table shows the correspondences between the Sudoku-specfic names in HLS and the generic names adopted here; notice that typed chains are also present in CSP-Rules V2.1.
– section 5.13 [Appendix 5B, “A symbolico-graphical representation of chain rules”] is an answer to some readers request of a less formal presentation of the main chain patterns; it is also present in the Basic User Manual; the reader should be aware that graphics can help understand but cannot replace a precise definition.
– section 5.14 [Appendix 5C, “How to start looking for a chain pattern”] is also an answer to some readers request; it shows that the starting point of a chain is always a very simple pattern; but it should remain clear that the present book is not intended as a tutorial on how to use in practice the chains it introduces.
– section 5.15 [Appendix 5D, “The most distinctive feature of all our chains”] is an important addition, intended to make still more explicit two essential points of our “philosophy” of chains as logical patterns: a chain is a continuous sequence of candidates (of course, with additional conditions specific to the type of chain) and it has an intrinsic length defined as the number of CSP-Variables involved in its definition; this is in strong contrast to the traditional view of a chain as a chain or network of inferences with complexity defined by the number of “nodes” (i.e. of inference steps) it involves; the difference is particularly noticeable in chains with z- and/or t- candidates; our definition of length is in perfect agreement with our view that such candidates are not part of the chains; it is also what allows to give a pure logic definition of chains.
– section 6.6 [“How well the W rating approximates the B (and many other) rating(s)”] is an extension of the corresponding short section in PBCS2, with the resolution power of many patterns compared to whips; it justifies why whips are given a central place in our approach.
– section 12.5 [“Requirements on the number of steps”] deals with several additional requirements one can put on the number of steps in a resolution path; such requirements have become familiar in the Sudoku community; they go much beyond the fundamental “pattern based” requirement adopted in this book; we show that there are ways to use resolution rules to deal with them; we also show that requirements on the number of steps can only be reasonable if they take into account the ratings obtained by the simplest-first strategy, i.e. if they put an a priori bound (not too much higher than the rating) on the length of chains; as this is more a matter of coding procedures using resolution rules in various T&E-ish ways than of defining and studying such rules, we leave most of this topic to the Basic User Manual for CSP-Rules-V2.1.
– section 17.10.2 [“Extended Quasi-Loops”] describes a useful generalisation of Quasi-Loops in Slitherlink.

Note that I have published all this somewhere on this forum before.

[Edit] finally, they also sell the hardcover version on Amazon.

[denis_berthier]

.
The 3rd edition of my book "Pattern-Based Constraint Satisfaction and Logic Puzzles" is now available as a free pdf:
- either on Researchgate: https://www.researchgate.net/publication/356313228_Pattern-Based_Constraint_Satisfaction_and_Logic_Puzzles_Third_Edition
- or on GitHub: https://github.com/denis-berthier/CSP-Rules-V2.1 (see the "Publications" folder)

[Edit]: the link to ResearchGate was broken. It should work now.
.