Pattern-Based Constraint Satisfaction... (2nd & 3rd eds)

Books about Sudoku

Re: Pattern-Based Constraint Satisfaction... (2nd edition)

Postby denis_berthier » Thu May 06, 2021 11:29 am

.
STATISTICAL COMPARISONS OF VARIOUS RATINGS


In my book PBCS2, section 6.6, I wrote: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 no differences.



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
2010 Supporter
 
Posts: 2767
Joined: 19 June 2007
Location: Paris

Re: Pattern-Based Constraint Satisfaction... (2nd edition)

Postby denis_berthier » Tue May 11, 2021 7:25 am

.
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
2010 Supporter
 
Posts: 2767
Joined: 19 June 2007
Location: Paris

Re: Pattern-Based Constraint Satisfaction... (2nd edition)

Postby denis_berthier » Thu Nov 18, 2021 6:17 am

.
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:
PBCS3 wrote:
    – 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.
denis_berthier
2010 Supporter
 
Posts: 2767
Joined: 19 June 2007
Location: Paris


Return to Books