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 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.
Last edited by denis_berthier on Mon Mar 28, 2022 1:33 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 3967
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: 3967
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.

[Edit] finally, they also sell the hardcover version on Amazon.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Wed Feb 09, 2022 6:31 am

.
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.
.
Last edited by denis_berthier on Sun Aug 13, 2023 10:24 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Thu Aug 11, 2022 3:49 am

.
ONE MORE COMPARISON OF RATINGS in cbg-000
Remember that cbg-000 consists of 21375 puzzles.

Let me first recall the result:
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.

New result:
FW vs F3W:
F3W is computed by using the 3-value relation and the OR3-Forcing-Whips
(plus, of course, the 2-value relation and the OR2-Forcing-Whips)

Note that one must always have FW ≥ F3W
In reality, there are only 31 differences, i.e. a proportion of 0.15 % differences.
And there are only 2 cases with difference ≥ 2 (0,009 %) and 1 case (0,005 %) with difference > 2 .

Note that these differences occur in puzzles for which W = FW. So that, when we compare directly W and F3W, we get:
Note that one must always have W ≥ F3W
In reality, there are only 38 differences, i.e. a proportion of 0.18 % differences.
And there are only 3 cases with difference ≥ 2 (0,014 %) and 2 cases (0,01 %) with difference > 2 .

My global conclusion about using Forcing-Whips based on trivalue cells is the same as about using Forcing-Whips based on bivalue cells: not worth the extra complexity.

Detailed results (i.e. the F3W ratings and the list of puzzles with FW ≠ F3W) are published on GitHub: https://github.com/denis-berthier/CSP-Rules-Examples

[Edit]: corrected percentages
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Sat Jul 15, 2023 6:25 am

.
There's no fourth edition of [PBCS], but the new version of the CSP-Rules user manual ("User Manual and Research Notes for CSP-Rules", [UMRN]) may be of interest to the readers of [PBCS].

One point that might have deserved an update in [PBCS] is section 11.4. My conjectures that all the 9x9 Sudoku puzzles were at most in T&E(2) and more specifically in B7B have been contradicted (after decades of intensive search for "hardest" puzzles) when I found that mith's Loki puzzle was not in T&E(2). However the analyses presented in section 11.4 for the puzzles known at that time remain valid.
I've also proven that all the known puzzles in T&E(3) have the tridagon pattern and are indeed in T&E(W2, 2) - which requires very specific analyses. Including all the necessary material in [PBCS] would have required adding too many pages.


With respect to [PBCS], [UMRN] has new generic ORk-chain rules (already introduced in previous versions of the user manual). They can make use of application-specific ORk-relations; they are intended for use with exotic patterns (such as tridagon or other impossible patterns) that allow to conclude on the existence of some ORk-relation between candidates. As these chains are straightforward extensions of the chains introduced in [PBCS], based on the same chaining principles, I thought it was more convenient not to overload [PBCS] with them.
These chains have also been discussed on this forum: http://forum.enjoysudoku.com/ork-forcing-whips-ork-contrad-whips-and-ork-whips-t40189.html

With respect to previous versions of the "Basic User Manual" or of the "Augmented User Manual", [UMRN] has two chapters that are more akin to research notebooks than to a user manual. They are:
- about the tridagon pattern, the Trid-ORk-chains and the classification results of T&E(3) puzzles obtained with them,
- about eleven's 630 impossible patterns, how to concretely use such a large number of patterns for solving puzzles, and about additional classification results of T&E(3) puzzles obtained when using them.
Part of this material has already been published on this forum, in several threads:
- http://forum.enjoysudoku.com/the-tridagon-rule-t39859.html
- http://forum.enjoysudoku.com/how-to-deal-with-large-numbers-of-patterns-t40889.html

[UMRN] is available:
- in print form, on Lulu.com : https://www.lulu.com/shop/denis-berthier/user-manual-and-research-notebooks-for-csp-rules/paperback/product-74jkdq.html?page=1&pageSize=4
- in pdf form, on ResearchGate: https://www.researchgate.net/publication/372364607_User_Manual_and_Research_Notebooks_for_CSP-Rules
.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Mon Dec 04, 2023 10:11 am

.
I made a major update of the controlled bias Sudoku generator and collection on GitHub: https://github.com/denis-berthier/Controlled-bias_Sudoku_generator_and_collection used to produce the statistical results in chapter 6 of [PBCS].
The update consists of three main changes:

1) a structural change: instead of global big collections of 5,926,343 puzzles and ratings, there are now 129 independent "small" collections. Each collection is a controlled bias collection (of about 21,000 or 85,000 puzzles). This will make it easier to use smaller collections than the global one. Instead of the large collections, there are now Unix scripts to assemble them from small collections. (My apologies to Windows users, but I'm not a Windows expert and it seems that the elementary "cat" command in Unix has no simple equivalent in Windows. Contact me if you need the large collections and don't know how to assemble them.)

2) the addition of a file showing how to use SudoRules to re-do the computations for correlation or unbiased distributions . Those are the functions used to produce the statistical results in [PBCS]. (I have taken this opportunity to make a few changes in the names of the SudoRules statistical functions in order to make them more consistent. This cannot change their results. I still have to document these functions in the user manual.)

3) an extension of the contents: for each small controlled-bias collection <xxx>, there are now 8 files, all with the same length:
- <xxx>-puzzles.txt contains the puzzles in the collection;
- <xxx>-nb-clues.txt contains their numbers of clues;
- <xxx>-nb-cands-after-BRT.txt contains their numbers of candidates after BRT; (this is new)
- <xxx>-nb-cands-after-W1.txt contains their numbers of candidates after W1; (this is new)
- <xxx>-W-ratings.txt contains their W ratings;
- <xxx>-gW-ratings.txt contains their W ratings;
- <xxx>-B-ratings.txt contains their B ratings; (this is new)
- <xxx>-SER.txt contains their SER ratings; (this is new for the last half of the collection)
- <xxx>-FPGXnoU.txt contains their SER ratings computed with the faster version FPGX, with rules for uniqueness disabled; (this is new)

All the nb-clues, nb-cands-after-BRT, nb-cands-after-W1 and W-ratings have been computed with the current version of SudoRules.
All the B ratings have been computed with the current version of SHC.


Note that none of the above changes anything about the results related to the W rating and its distribution, the unbiased distribution of the number of clues or the estimated number of Sudoku puzzles published in [PBCS].
However the additional data for some of the ratings allow to have more precise comparisons and correlations results for them. See some forthcoming posts for details.

[Edit:] add the gW ratings
.
Last edited by denis_berthier on Fri Jan 05, 2024 5:38 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Thu Dec 07, 2023 4:59 am

.
The miracle of whips
Long ago, I've written about the "miracle of whips": although whips are structurally and computationally much simpler than braids, they have almost the same resolution power at any length. Said otherwise, although whips satisfy the continuity condition (they are true chains, while braids only satisfy “braided-continuity”) and although whips require in the mean exploring “exponentially” (wrt length) fewer partial chains for solving a puzzle, (both properties making them much easier to use for human solvers), the values of the W and B ratings are "almost always" the same.
This is the reason why I've always considered braids as the right theoretical tool (because the Bn resolution theories have the confluence property and because of the T&E vs braids theorem) and whips as a nicer practical tool for human solvers.

The above claim was originally based on the controlled-bias cbg000 collection of 21,375 puzzles:
denis_berthier wrote: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.

At a time when nobody else studied large collections of puzzles, 21,375 seemed large and it didn't seem necessary to invoke the full controlled-bias collection of 5,926,343 puzzles and to spend huge computation time on its B ratings with SudoRules.

Now that the B ratings have been computed for the whole collection (using the faster SHC), I can give much more precise results. Notice that they don't change significantly but they strengthen the previous ones (available in [PBCS], chapter 6). Of course, one must still have W ≥ B for any puzzle.

For the 5,926,343 controlled-bias puzzles, there are only 15,238 differences (0.257 %) between W and B, including:
– 14,574 cases of difference = 1 (0.25 %);
– 625 cases of difference = 2 (0.011 %);
– 35 cases of difference = 3;
– 3 cases of difference = 4;
– 1 cases of difference = 5;
only 664 cases of difference > 1 (0.011 %, i.e. one puzzle in ten thousand);
only 39 cases of difference > 2 (0.00066 %, i.e. less than seven puzzles in one million).
.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Fri Dec 15, 2023 9:10 am

.
One more point that can be investigated on the full controlled-bias collection is the impact of uniqueness on the SE rating.
As the SER and FPGXnoU (fast version of PGXplainer, with rules for uniqueness disabled - i.e. with option -M) ratings have been computed for the whole CB collection, one can estimate the impact of the uniqueness rules on SER (forgetting rare cases where SER ≠ PGX)

There are:
366671 differences (6.19%)
290490 differences > 0.1 (4.90%)
280724 differences > 0.2 (4.74%)
270355 differences > 0.3 (4.56%)
Those are upper bounds for differences due to uniqueness.

Note that this is much more than differences between the W and the W+U ratings (0.27%), reported in a previous post for cbg000.


Moreover, while one had W ≥ W+U in all the cases, one can find very rare cases with SER > FPGXnoU.
This means that although one adds rules (for uniqueness) to FPGX (wrt FPGXnoU), the resulting rating is higher.
In the whole collection, there are 186 cases (0.00003 %) with SER > FPGXnoU.
Here are the 5 such cases where the difference is > 0.3. (I also checked that in these cases SER = FPGX, so that the difference can only be due to uniqueness.)

Code: Select all
#1192670; SER = FPGX = 8.8; FPGXnoU = 8.4; diff = 0.4
.....6.......891..7.9...........394.51.9..8.3.38.24.....52..4..6...7..9........5. 387373

#1284282; SER = FPGX = 8.8; FPGXnoU = 8.4; diff = 0.4
........9457........937..4...........159....89.8.4.16..6.....9......5...83...1.52 94624

#1990228; SER = FPGX = 7.2; FPGXnoU = 6.8; diff = 0.4
1.....7.945.1..2..6.8.7..........193..9...4...4.....253.27......8.5........26.3.. 26 649538

#2273360; SER = FPGX = 7.2; FPGXnoU = 6.8; diff = 0.4
..3.5..8.4....9.2..8...2.1426.....3.57..........6....5...86...7...2.14.8.......6. 25 41660

#4904804; SER = FPGX = 7.2; FPGXnoU = 6.8; diff = 0.4
1.3..6.........326.....2........1....3..7...291..4.6...9.8....176..1..95....9.27. 26   241358
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Fri Jan 05, 2024 5:52 am

denis_berthier wrote:.
STATISTICAL COMPARISONS OF VARIOUS RATINGS
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.

W vs gW:
Note that one should 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.


Following the computation of all the gW ratings with SudoRules (thus using 5,926,343 minimal puzzles instead of only 21,375), the above results can be made slightly more precise:

12752 differences (0.215 %)
12749 positive differences
3 negative differences


12114 cases with diff = 1
635 cases with diff = 2
68 cases with diff = 3
6 cases with diff = 4
2 cases with diff = 5
1 cases with diff = 6
That is:
494 cases with diff > 1 (0.0107 % - i.e. 1 in 10,000)
77 cases with diff > 2 (0.00130 % - i.e. 1.3 in 100,000)


The 3 cases (i.e. 5 in 10,000,000) with diff = -1 are due to the non confluence of the g-whip[n] resolution theories. It is one of the new results that were not available in the smaller collection: an estimate of the frequency of non confluence for the gWn.
#1072535: W = 5; gW = 6; diff = -1
#3791115: W = 7; gW = 8; diff = -1
#4117915: W = 5; gW = 6; diff = -1

Reminder: in CSP-Rules, whips or g-whips are loopless.
.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

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

Postby denis_berthier » Sun Jan 14, 2024 8:01 am

.
One of the comparisons that were still missing is those involving the gB ratings. The main reason was gB ratings take a long time to compute.
I've just published on GitHub (https://github.com/denis-berthier/CSP-Rules-Examples) the gB ratings for the cbg-000 collection of 21,375 controlled-bias minimal puzzles.

The conclusions are similar to those in previous posts with the W and B ratings.

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


2) B vs gB:
Note that one must always have B ≥ gB
In reality, there are only 32 differences, i.e. a proportion of 0,15 % differences.
And there are only 2 cases with difference > 1 (0,01%), including only 1 with difference > 2.
.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

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

Postby DEFISE » Tue Jan 16, 2024 10:50 am

Hi Denis,
Last thursday (January 11) I send you a mail fixing the bug in SHC1 for calculate gB-ratings. Did you receive it ?

François.
DEFISE
 
Posts: 270
Joined: 16 April 2020
Location: France

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

Postby denis_berthier » Tue Jan 16, 2024 10:53 am

DEFISE wrote:Hi Denis,
Last thursday (January 11) I send you a mail fixing the bug in SHC1 for calculate gB-ratings. Did you receive it ?
François.


Hi François,
Nice to hear of you. No, I didn't receive it. Can you send it again? Thanks.

Note 1: for the gB results in my previous post about the "small" cbg-000 collection, the bug (a memory overflow problem) didn't manifest itself in SHC1, so that I could check the SudoRules and SHC results were identical for gB on this collection. As before for the B ratings, this provides a cross validation of SudoRules and SHC for gB-ratings.

Note 2: gB ratings are not currently part of the public version of SHC.
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

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

Postby DEFISE » Tue Jan 16, 2024 11:43 am

Ok, so you haven't made the correction.
I just sent you again my email of January 11th.

François.
DEFISE
 
Posts: 270
Joined: 16 April 2020
Location: France

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

Postby denis_berthier » Tue Jan 16, 2024 12:17 pm

DEFISE wrote:Ok, so you haven't made the correction.
I just sent you again my email of January 11th.
François.

The correction was not needed for cbg-000. But the memory overflow problem appears in the next small collection (cbg-001). I don't plan to compute the gB ratings for the whole collection of 6M, but maybe a few 100,000s for more precise results. gB computations take too much time with SudoRules, so I'll do it only if I get a working version of SHC for gB.

There must be some problem with one of our mailboxes, because 30 mins after your above post, I haven't yet received your email (and I checked the spam). The last email I have from you is from Jan. 2
Can you try again, with my old address? Can you also try to send an almost empty email, to see if there's a problem of data size?
denis_berthier
2010 Supporter
 
Posts: 3967
Joined: 19 June 2007
Location: Paris

Next

Return to Books

cron