Sudoku Players' Forum (clone)

.
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

.
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
.

.
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
.

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

.
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 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.
.

.
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.
.

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 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.

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

François.

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,
I just sent you (5 minutes ago) an email to your old address and an empty email.
F.

DEFISE wrote:Denis,
I just sent you (5 minutes ago) an email to your old address and an empty email.
F.

It (I mean the empty email) works. Can you try with the SHC (or only the 1 or 2 modified files)?

Denis,
OK I have just tried it.
F.

.
Hi François
Thanks
This time, I received it and it works. I have no idea of what happened the previous days (maybe a problem with iCloud but I've found no reference to any).

I plan to extend my gB calculations to a few more "small" collections - but not to the whole cbg one.