The Hidden Logic of Sudoku

A new conceptual framework for solving Sudoku puzzles with pure logic

 
Denis Berthier

First edition: May 2007

Second edition: November 2007




Online Supplements


Rating rules / puzzles. Ordering the rules.






© Denis Berthier. All the material in this page and the pages it gives access to are the property of the author and may not be re-published or re-posted without his prior written permission.




1) INTRODUCTION - MOTIVATIONS

Several ratings of rules or puzzles are known and they generally lead to different classifications of puzzles. (I'm not speaking here of the commercial classifications into 4 or 5 levels, which bear only on the simplest puzzles, even when they are called diabolical).
Comparison of different ratings can't therefore be done on a puzzle by puzzle basis. It can only be statistical.

The various ratings can also suggest different classifications of the resolution rules.

The ratings initially considered here are (this list can eventually be extended):
NRCZT-rating
SER-rating
SUEX9-rating
SUEXT-rating
GSF-Q1-rating


The purpose of this page is thus multiple. It aims at least at:
- assembling in a single place a precise definition of each rating (or pointers to such definitions);
- giving references to where and how each of these ratings can be computed;
- providing software so that anyone can compare for himself the various ratings on large collections of puzzles;
- providing large collections of puzzles that can be used as references for such comparisons;
- evaluating the statistical complexity of rules (mean value analysis) and, for rules depending on some parameters, how this complexity varies with these parameters
(examples of possible parameters: length for chains, maximum ALS size for chains with ALS, ...);
- analysing the consequences on rules classification.



1.1) CORRELATION COEFFICIENT OF TWO RATINGS

The main and simplest statistical tool for comparing two ratings is their correlation coefficient.
Given a collection of N puzzles and several rating functions, each of these rating functions is a statistical variable and it can be seen as a vector in R^N.
The (linear) correlation coefficient between two statistical variables has a value between -1 and +1. It is the cosine of the angle between the two associated vectors in R^N.

A correlation coefficient whose absolute value is greater than 0.8 is generally considered high.
A correlation coefficient whose absolute value is smaller than 0.5 is generally considered low (which means that there is no meaningful correlation between the two variables - the angle between the two vectors representing the two variables in R^N is > 45°).


1.2) PSEUDO-CODE FOR COMPUTING THE CORRELATION COEFFICIENTS

Suppose we have two statistical variables X and Y depending on the puzzle P under consideration (e.g. X = the NRCZT-rating of P and Y = the SER rating of P).
Suppose we have a sequence of n puzzles.
Suppose, for definitness, that the X and Y variables corresponding to this sequence are respectively in x-file and y-file, with one value per line in each file.
The following algorithm (in its standard iterative form) gives the correlation coefficient r between X and Y:

(deffunction correlation (?x-file ?y-file ?n)
   (open ?x-file "x-file" "r")
   (open ?y-file "y-file" "r")
   
   i = 1
   EX = 0
   EY = 0
   EX2 = 0
   EY2 = 0
   EXY = 0
   
   while i < (n + 1) do
      ;; get the i-th element in x-file:
      xi = eval (readline "x-file")
      ;; get the i-th element in y-file:
      yi = eval (readline "y-file")
      ;; here I use "eval" to indicate a cast (if necessary) to the proper type (integer, float,...)
      EX = EX + (xi - EX) / i
      EY = EY + (yi - EY)  / i
      EX2 = EX2 + (xi^2 - EX2) / i
      EY2 = EY2 +(yi^2 - EY2) / i
      EXY = EXY + ((xi * yi) - EXY) / i
      i = i + 1
   next i
   
   VX = EX2 - EX^2
   VY = EY2 - EY^2
   CovXY= EXY - EX * EY
   r = CovXY / [sqrt (VX) * sqrt (VY)]
   ;; if you also want to compute the regression line Y = a X + b, add the following two lines:
   ;a = CovXY / VX
   ;b = EY - a * EX
   (close "x-file")
   (close "y-file")
   ;; print whatever you want: r, a , b
   return r
)


Now, if you want to compute the correlation between X and a function f of Y,  just replace
yi = eval (readline "y-file")
within the "while" loop, by
yi = f (eval (readline "y-file"))

E.g., if X= Level and Y = Time (resp. Memory), you may want to check if there is a correlation between X and log(Y), corresponding to an exponential increase of computation times (resp. memory requirements) with respect to levels - or a correlation between X and Y^(1/4) corresponding to a polynomial (x^4) increase of computation times (resp. memory requirements) with respect to levels.


Such computations should always be interpreted with some care and should not be extrapolated beyond the range of the data. For instance, if the levels of all the puzzles in the collection have a range between 1 and 7, it is impossible to make a difference between an exponential behaviour and a polynomial behaviour in x^6 or x^7 (say for computation times or memory requirements).



1.3) MEAN DISTANCE OF A RATING FROM ALL THE OTHERS
Whereas the correlation coefficient allows comparisons between two ratings, the mean distance from a rating to all the others allows to evaluate its compatibilty with them.
Its geometrical meaning is a mean distance in space R^N between the unit vectors associated to each rating. (Lengths are discarded, everything is brougth to the unit sphere in R^N. This rescaling allows to eliminate meaningless differences between different ratings).







2) DEFINITION OF A FEW RATINGS

2.1) THE NRCZT-RATING

Of course, I'll be concerned with the NRCZT-rating, among others, so let me remind its definition.
It is mainly based on nrczt-whips.
Rules are classified in levels according to the number of cells they rely on. There is thus one and only one parameter and the classification is very simple. More precisely:
Definition: let Ln be the following sets of resolution rules:
L0: only elementary constraints propagation (no unsolved puzzle can be solved here)
L1_0: Naked and Hidden Singles
L1: elementary interactions between rows/columns and blocks (equivalent to nrczt-whips[1] - see subsumption  page)
L2: Naked, Hidden and Super-Hidden Pairs + nrczt-whip[2]
L3: Naked, Hidden and Super-Hidden Triplets + nrczt-whip[3]
L4: Naked, Hidden and Super-Hidden Quads + nrczt-whip[4]
L5: nrczt-whip[5]
For n > 4: Ln: nrczt-whip[n], where n is the length of the whip (remember that the length of a whip is the number of rc, rn, cn or bn cells on which it resides).

Let T(Ln) be the set of resolution rules at levels from 0 to n, e.g. T(Ln) = L0 + L1_0 + L1 + ... Ln.
T(Ln) is a set of resolution rules (i.e. a resolution theory - for these notions, see my book or the page on resolution rules).

Now, define Ln as the set of puzzles for which there is a constructive proof of their solution within T(Ln) but not within T(Ln-1).
The Ln stratification of puzzles is thus purely logical, by definition. It doesn't depend in any way on any solver.

Specialisations of NRCZT whips can be used in the resolution paths (nrc, nrcz, nrct or any of their 2D counterparts, but this does not change the levels defined here).


What can be said of the T(Ln)?
- they are a sequence of logical theories of increasing strength;
- each of them is invariant under symmetry and supersymmetry; this entails that the Ln stratification is invariant under symmetry;
- none of them is complete; i.e. none of them can solve any valid puzzle with a unique solution; (notice that this is the case for any currently known set of resolution rules);
- nevertheless, L7 is enough to solve 99,99% of the minimal puzzles and in 10,000,000 puzzles randomly generated with different types of generators, none was found that couldn't be classified.





2.2) REFERENCES OR DEFINITIONS FOR THE OTHER RATINGS

This is a copy of a post from Mike Barker on the Sudoku Player's Forum:

-------------------------------------------------------------------------------------
Here are links to some of the codes for rating puzzles. In addition to Sudoku Explainer, suexratt, and GSF's solver, I've included Ruud's and Havard's solvers which also can also rate puzzles. I haven't used these, but for the other three I've shown the command line I've used. Note I've written code to reduce the full output to SE to just the ratings values. I'm not sure its necessary.

Nicolas Juillerat's Sudoku Explainer at http://diuf.unifr.ch/people/juillera/Sudoku/Sudoku.html
java -cp SudokuExplainer.jar diuf.sudoku.test.Tester sudoku.txt result.txt

Guenter Stertenbrink's (dukuso) http://magictour.free.fr/suexratt.exe
suexratt sudoku.txt 10000 2 > rate_ST.out

Glenn Fowler's (gsf) Solver at http://www.research.att.com/~gsf/sudoku/
gsf -H -q1 -f"%6r %v" sudokus.out > rate_GSF.out
or
gsf -q"FNBTHW-G" -Z"FNBTHWP*" -B -M- -R"P0*1000+P2+(P8>1?10000:0)" -f"%r" sudoku.txt > rate_GSF.out

Ruud's Sudocue at http://www.sudocue.net/download.php

Havard Graff's Sudoku Assistenten at http://www.sudoku.frihost.net/

Also here's a summary of how I believe SE rates puzzles. I've enclosed those ratings I haven't reproduced in "[]". There are probably some that are missing, for example, chains with more or fewer "nodes" (my term) than I've shown and I'm not sure of the "node" count or how "nodes" are calculated (they are a combination of the number of if,then statements and the number of chains). Note that UR's and BUG's probably are rated higher than they should be based on difficulty and a limitation of SE is that it doesn't used finned fish, grouped strong links, ALS, or AHS so some puzzles get rated higher than I would think they should be

Code:
 1.0 Single
 1.2 Hidden Single in box
 1.5 Hidden Single in line
 1.7 Direct Pointing
 1.9 Direct Claiming
 2.0 Direct Hidden Pair
 2.3 Naked Single
 2.5 Direct Hidden Triplet
 2.6 Pointing
 2.8 Claiming
 3.0 Naked Pair
 3.2 X-Wing
 3.4 Hidden Pair
 3.6 Naked Triplet
 3.8 Swordfish
 4.0 Hidden Triplet
 4.2 XY-Wing
 4.3 [Direct Hidden Quad]
 4.4 XYZ-Wing
 4.5 UR Types 1 or 2 or 4 or 3 w/ hidden pair
 4.6 UR Type 3 w/ naked pair or hidden triplet
     UL Types 1 or 2 or 4 or 3 w/ hidden pair (6 cells)
 4.69 UL Type 3 w/ a naked pair or hidden triplet (6 cells)
 4.7 UR Type 3 w/ naked triplet or hidden quad
     UL Types 1 or 2 or 4 or 3 w/ hidden pair (8 cells)
 4.8 UR Type 3 w/ naked quad
     UL Type 3 w/ naked triplet [or hidden quad] (6 cells)
     UL Type 3 w/ naked pair or hidden triplet (8 cells)
 4.89 UL Type 3 w/ naked quad (6 cells)
 4.9 [UL Type 3 w/ naked triplet or hidden quad (8 cells)]
 5.0 Naked Quad or UL 1 or 2 or 4 (>=10 cells)
 5.1 UL Type 3 w/ naked pair (>=10 cells)
 5.2 Jellyfish
 5.3 Unknown
 5.4 Hidden Quad
 5.5 Unknown
 5.6 BUG Type 1
 5.7 BUG Type 2 or 4
 5.8 BUG Type 3 w/ naked pair
 5.9 BUG Type 3 w/ naked triplet
 6.0 BUG Type 3 w/ naked quad
 6.1 BUG Type 3 w/ naked quint
 6.2 Aligned Pair Exclusion
 6.3 Unknown
 6.4 Unknown
 6.5 Bidirectional X-Cycle or Bidirectional Y-Cycle (1-4 nodes)
 6.6 Turbot Fish
     Forcing X-chain or Bidirectional Y-Cycle (5-6 nodes)
 6.69 Forcing X-Chain (7-8 nodes)
 6.7 Bidirectional Y-cycle (7-8 nodes)
 6.8 Forcing X-Chain or Bidirectional Y-cycle (9-12 nodes)
 6.9 Forcing X-Chain or Bidirectional Y-cycle (13-16 nodes)
 7.0 Bidirectional Y-cycle (17-24 nodes)
     Forcing Chain or Bidirectional Cycle (1-4 nodes)
 7.1 Forcing Chain or Bidirectional Cycle (5-6 nodes)
 7.2 Forcing Chain or Bidirectional Cycle (7-8 nodes)
 7.3 Forcing Chain or Bidirectional Cycle (9-12 nodes)
 7.4 Forcing Chain (13-16 nodes)
 7.5 Forcing Chain (17-24 nodes)
     Aligned Triplet Exclusion
 7.6 Forcing Chain (25-36 nodes)
     Nishio Forcing Chain (5-6 nodes)
 7.7 Nishio Forcing Chain (7-8 nodes)
 7.8 Nishio Forcing Chain (9-12 nodes)
 7.9 Nishio Forcing Chain (13-16 nodes)
 8.0 Nishio Forcing Chain (17-24 nodes)
 8.1 Nishio Forcing Chain (25-36 nodes)
 8.2 Multiple (7-8 nodes) Region Forcing Chains
 8.3 Multiple (9-12 nodes) Cell/Region Forcing Chains
 8.4 Multiple (13-16 nodes) Cell/Region Forcing Chains
 8.5 Multiple (17-24 nodes) Cell/Region Forcing Chains
 8.6 Multiple (25-36 nodes)
     Dynamic (5-6 nodes) Cell/Region Forcing Chains
 8.7 Dynamic (7-8 nodes) Cell/Region Forcing Chains
 8.8 Dynamic (9-12 nodes) CRCD Forcing Chains
 8.9 Dynamic (13-16 nodes) CRCD Forcing Chains
 9.0 Dynamic (17-24 nodes) CRCD Forcing Chains
 9.1 Dynamic (25-36 nodes) CRCD Forcing Chains
 9.2 Dynamic (37-48 nodes) CRCD Forcing Chains
 9.3 Dynamic (49-72 nodes)
     Dynamic + (9-12 nodes) CRCD Forcing Chains
 9.4 Dynamic (73-96 nodes)
     Dynamic + (13-16 nodes) CRCD Forcing Chains
 9.5 Dynamic + (17-24 nodes) CRCD Forcing Chains
 9.6 Dynamic + (25-36 nodes) CRCD Forcing Chains
 9.7 Dynamic + (37-48 nodes) CRCD Forcing Chains
 9.8 Dynamic + (49-72 nodes) CRCD Forcing Chains
 9.9 Dynamic + (73-96 nodes) CRCD Forcing Chains
10.0 Dynamic + (97-144 nodes)
     Dynamic + Forcing Chains (17-24 nodes) CRCD Forcing Chains
10.1 Dynamic + (145-192 nodes)
     Dynamic + Forcing Chains (25-36 nodes) CRCD Forcing Chains
10.2 Dynamic + Forcing Chains (37-48 nodes) CRCD Forcing Chains
10.3 Dynamic + Forcing Chains (49-72 nodes) CRCD Forcing Chains
10.4 Dynamic + Forcing Chains (73-96 nodes) CRCD Forcing Chains
10.5 Dynamic + Forcing Chains (97-144 nodes) CRCD Forcing Chains
10.6 Dynamic + Forcing Chains (145-192 nodes) CRCD Forcing Chains
10.7 Dynamic + Forcing Chains (193-288 nodes) CRCD Forcing Chains
10.8 Dynamic + Forcing Chains (289-384 nodes) CRCD Forcing Chains
10.9 Dynamic + Multiple Forcing Chains (73-96 nodes) CRCD Forcing Chains
11.0 Dynamic + Multiple Forcing Chains (97-144 nodes) CRCD Forcing Chains
11.1 Dynamic + Multiple Forcing Chains (145-192 nodes) CRCD Forcing Chains
11.2 Dynamic + Multiple Forcing Chains (193-288 nodes) CRCD Forcing Chains
11.3 Dynamic + Multiple Forcing Chains (289-384 nodes) CRCD Forcing Chains
11.4 Dynamic + Multiple Forcing Chains (385-576 nodes) CRCD Forcing Chains
11.4 [Dynamic + Dynamic Forcing Chains (73-96 nodes) Region/Contradiction Forcing Chains]
11.5 [Dynamic + Dynamic Forcing Chains (97-144 nodes) Region Forcing Chains]
11.6 [Dynamic + Dynamic Forcing Chains (145-192 nodes) Cell Forcing Chains]
11.7 [Dynamic + Dynamic Forcing Chains (193-288 nodes) Double Forcing Chains]

CRCD=Cell/Region/Contradiction/Double
UL=Unique Loop
UR=Unique Rectangle
BUG=Bivalue Universal Grave


-------------------------------------------------------------------------------------









3) FIRST RESULTS

3.1) FIRST CORRELATION RESULTS

In the following preliminary results:
-- the sudogen0 collection of 10,000 puzzles has been used. It is a collection of 10.000 minimal puzzles, randomly generated with the suexg generator.
-- I used only the first 1.000 puzzles
-- this is a joint work with Mike Barker. He provided all the SER, SUEX9, SUEXT and GSF-Q1 ratings used for the comparisons.

Correlation coefficients:
NRCZT vs SER: 0.89
NRCZT vs SUEX9: 0.73
NRCZT vs SUEXT: 0.77
NRCZT vs GSF-Q1: 0.70

SER vs SUEX9: 0.70
SER vs SUEXT: 0.68
SER vs GSF-Q1: 0.69

SUEX9 vs SUEXT: 0.88
SUEX9 vs GSF-Q1: 0.75

SUEXT vs GSF-Q1: 0.64


Although the GSF-Q1 rating remains a little apart from the others, it is not as bad as the limited set Unsolvables33 suggested.

Mean distances:
This analysis can be completed by computing the mean distance of each rating to the other 4. The shorter the distance, the closer the rating to others:

NRCZT-rating: 0.678
SER-rating: 0.721
SUEX9-rating: 0.682
SUEXT-rating: 0.716
GSF-Q1-rating: 0.780



These correlation results are valid for the nrczt levels from 1 to 7. This corresponds to 99.9 % of the random minimal puzzles and, likely, to normal human solving capabilities. I think they are interesting in this context.
Studying higher levels would require much larger random collections, in which sufficiently many puzzles at these higher levels would be present. Anyway, elementary statistics may not be a very appropriate tool for studying such extreme cases.




3.2) HOW MANY CHAINS ARE THERE?

Given a partial chain of length n and of a given type (xy, nrc, hxyt, nrczt,...), it may in general be extended to the right into several chains of the same type and of length n+1. The number of chains of a given type may thus grow exponentially with the length. But, as there can't be chains of length > 81 (if we don't admit inner loops), there has to be a bound to the exponential growth.

The question of counting the chains is important in rating the puzzles, because the difficulty of finding useful chains is related to their length, of course, but also to how many (useless) chains of a given length there are.
Unfortunately, it is impossible to compute the number of chains a priori: worst case analysis suggests exponential growth, while a priori mean case analysis is impractical.
Here are the results of an experimental mean case analysis based on the 10,000 random minimal puzzles of the Sudogen0 collection, using the nrczt sets of rules and levels defined in the first post.

More precisely, here are the correlation coefficients between the nrczt-ratings and the number of chains (or the indicated function of it):

nrczt-rating vs number of chains: 0.54, no meaningful correlation

nrczt-rating vs log(number of chains): 0.96, very strong correlation

nrczt-rating vs sqr2(number of chains): 0.85
nrczt-rating vs sqr4(number of chains): 0.93
nrczt-rating vs sqr6(number of chains): 0.95
nrczt-rating vs sqr8(number of chains): 0.95

here, sqrn(x) is x^(1/n)


These results are valid for nrczt-levels ranging from 1 to 7 (i.e. with chains of length 1 to 7, enough to solve 99.9% of the minimal puzzles).
As explained in a previous post, in this range, it is impossible to discriminate between exponential or polynomial (x^6 or x^8) growth of the number of chains with length. But in any case, this shows a fast growth of the number of (useful or useless) chains with their length.
Remember that these results are only valid statistically and that there may be large differences between two puzzles at the same level.




3.3) COMMENTS

1) First, it is important to recall that these statistical results cover the whole range of puzzles that a human player can solve and they are likely to go much beyond normal human capabilities.

2) The NRCZT-rating is a natural one, based on a single and very simple parameter: the size of the hardest pattern (in the NRCZT set of rules) necessary to solve a puzzle. It satisfies all the good properties one can hope for a rating:
- purely logical definition, based on the concept of a resolution rule, whose conclusion can only be the assertion of a value or the elimination of candidates - i.e. the concrete elementary steps of any human solver;
- implementation independence (as a result of the previous property);
- invariance under elementary symmetries (permuting rows, columns, ...) and under logical supersymmetries;
- it applies to almost all the puzzles;
- it could be extended to the few puzzles resisting nrczt-whip rules by adding a penalty for the intrusion of Trial and Error; I don't know yet what'd be the best form for this penalty, but it should introduce a clear discontinuity in the rating;
- finally, due to the fast growth in complexity with level, all the levels are clearly separated.

3) In the purely logical NRCZT-rating, apparently only the length of the longest pattern necessary to solve a puzzle is taken into account. But, as this rating guarantees that the puzzle can't be solved with shorter patterns, it implicitly takes all the shorter patterns into account. As a result, any compliant implementation will have to explore all the patterns of smaller length; it will thus implicitly take into account all the alternative possible choices at lower levels.

4) As the NRCZT-rating is reasonably well correlated with the other usual ratings (SER, SUEX9, SUEXT and GSF-Q1), these results also indicate that the length of the longest chain necessary to solve a puzzle is statistically the main parameter of its difficulty, whichever rating we consider (and whichever types of chains, among the current ones, it uses).
Of course, this result can't be extended to puzzles beyond the classification, such as the very rare minimal puzzles (fewer than 1 in 10,000,000) which require T&E, nets or second order patterns.

5) Do these statistical results reflect the ratings of the puzzles aimed at human solvers, typically those published in the newspapers or on web forums?
I don't know how these puzzles are created/selected and I haven't made any statistical analysis on this, but if I was a puzzle creator, I would choose puzzles that need relatively long chains (because it is more fun) but for which the number of partial useless chains is limited (because finding the good ones would otherwise exceed human capabilities) - unless I chose to emphasise some specific pattern, e.g. fish for fish addicts. I would thus create very biased samples. I conjecture this is somehow what puzzle creators do.

6) Can the NRCZT-rating be refined so as to take into account individual deviations from mean behaviour at each level?
There is an obvious possibility: indicating the number of partial chains, e.g., taking examples from the first puzzles in Sudogen0: L1-412, L3-4014, L4-47155, L2-492, L6-141739, L2-1276, L2-1243, L4-42482, L1-494, L2-4064, L1-507, L1-477, L1-492, L4-11313,...
There is an obvious second possibility: introducing sublevels for specialised cases of nrczt-whips (such as nrc, nrct, ...)




3.4) ADDITIONAL CORRELATION RESULTS: NRCZT vs SER vs RUUD's Rank

With the full collection of 10,000 random minimal puzzles in Sudogen0, the correlation coefficient between the NRCZT-ratings and the SER-ratings is 0.895.
(it was 0.885 with the first 1,000; this difference is within normal bounds for such computations).


Ruud has ordered his top10000 list according to decreasing difficulty, based on tabling.
The question naturally arises: is this ordering correlated with other ratings of puzzles?
I computed the SER ratings of all the puzzles in this list: they vary between 4.6 and 9.3.
I then correlated this with the rank in the list (call it RuudRank).
The correlation coefficient I got is -0.206, which means that there is no meaningful correlation.

As the complexities of the puzzles could decrease sub-linearly with their rank in the list, I also tried to correlate SER
- with log(RuudRank) and I got -0.23
- with sqr(RuudRank) and I got -0.22

(All these coefficients are negative, which is normal as the complexity is supposed to be decreasing in Ruud's list).

All these results mean that there is no meaningful correlation between RuudRank, based on tabling, and the SER ranking.
This is interesting, as we have seen that the usual other rankings are strongly correlated.






3.5) CORRELATION RESULTS FOR GSF'S COLLECTION

The collection referred to here is not the last extended file but the version that contained 4820 puzzles. I didn't take the last version because it contains many puzzles for which the SER and SER-times are not computed (I guess this is what the value 0 means)
gsf provides the Q1, SER and XR ratings and the Q1 computation times (he also provides the SER computation times, but their format is not useable without transformation: e.g. 1h4m6s).

--------------------------------------------------------------------------------

SER vs Q1 : 0.41
SER vs sqr(Q1) : 0.53
SER vs sqr4(Q1) : 0.62
SER vs sqr6(Q1) : 0.65
SER vs sqr8(Q1) : 0.67
SER vs sqr16(Q1) : 0.69
SER vs log(Q1) : 0.72

This shows that SER is not correlated to Q1 but to log(Q1)
This is indeed the impression I had but this is now confirmed by statistics.

--------------------------------------------------------------------------------

XR vs Q1 : 0.66
XR vs sqr(Q1) : 0.73
XR vs sqr4(Q1) : 0.77
XR vs sqr6(Q1) : 0.77
XR vs sqr8(Q1) : 0.77
XR vs sqr16(Q1) : 0.77
XR vs log(Q1) : 0.77

This shows that XR is less correlated to Q1 than to sqr4(Q1),..., sqr16(Q1) or log(Q1)

--------------------------------------------------------------------------------

ER vs XR : 0.64
ER vs sqr(XR) : 0.73
ER vs sqr4(XR) : 0.78
ER vs sqr6(XR) : 0.80
ER vs sqr8(XR) : 0.81
ER vs sqr16(XR) : 0.82
ER vs log(XR) : 0.83

This shows that ER is less correlated to XR than to sqr4(XR),..., sqr16(XR) or log(XR)

--------------------------------------------------------------------------------
Comments:

We can ask: how is it possible that SER is correlated to log(Q1), XR is correlated to log(Q1) and SER is more correlated to log(XR) than to XR?
Don't forget that we are in a high dimensional space (here R^4820) and there are many ways several unit vectors can be close to each other.

The Q1 scaling is best considered as exponential wrt to the other usual scalings.

--------------------------------------------------------------------------------

Finallly, what can be said of the computation times?

Q1-times vs Q1 : 0.38
Q1-times vs log(Q1) : 0.23
As Q1-times may be 0, one can't compute Q1 vs log(Q1-times), but
Q1 vs sqr16(Q1-times) : 0.50

There doesn't seem to be any correlation between Q1 and Q1-times. But this may be due to the imprecision in Q1-times (the unit is the second and many values are 0).





3.6) Q2 vs Q1

Anyway, here are the correlation results for this new list (8152 puzzles).

1) For the whole list
Q2 vs Q1 : 0.41
At first sight, I was very surprised that the correlation is so weak. On second thoughts, I remembered that:
- 46% of the minimal puzzles can be solved with Singles
- 77,7% can be solved with Singles + elementary interactions
One can therefore understand that adding elementary interactions to prune the search tree can change it so drastically for all the puzzles.

2) For the sublist of the (4849) puzzles for which the ER is computed:

Q2 vs Q1 : 0.67 (I have no explanation why the correlation is higher for this sublist - maybe, gsf could explain it based on the reasons why he didn't compute the ER for the other puzzles and which kind of new bias this introduced)

Q1 vs SER : 0.41
Q2 vs SER : 0.40

log(Q2) vs SER : 0.67
log(Q1) vs SER : 0.72

which shows that Q2 behaves globally as Q1 wrt SER.






3.7) REMARKS ON RATINGS

We can observe that no universal rating has yet been devised and I think this will remain the case for a long time.

I think we should ask a few basic questions. I'll leave most of them open.

1) What general purpose do we assign to a rating?
Should it be able to rate all the puzzles? Why?
Should it be able to rate all the puzzles that can currently be solved by a "normal" human player?
Or do we want only a rating for the most common puzzles, from easy to diabolical - for commercial purposes?
On the contrary, do we want a specific rating for exceptionally hard puzzles - for research purposes?
(In this open list, where do we put SER? Commercial? I mean: its declared validity is universal, but isn't its real validity limited to commercial puzzles?)


2) Shall we be happy if the rating satisfies its general purpose or, in addition, should it be based on well defined general principles?
This isn't only rethorical. A rating may be useful even if it isn't based on clearly defined principles but on experience with resolution. Isn't this the case for SER?


3) In the second case, what constraints do we impose on the rating? E.g.:
- do we want the rating to be invariant under permutations of rows, columns, floors and towers and under row/column symmetry (SER doesn't even satisfy this very minimal requirement);
- do we want it to be invariant under supersymmetry (so that e.g. fish=naked set of the same size);
- on the contrary, do we want it to be closer to human perception (which would make it a very hard research topic in our current state of knowledge)?


4) Should the rating be based on a well defined backbone?
I mean: as any rating has to be based on a particular set of rules, can we choose a basic set of rules (e.g. some fixed type of chains of increasing length) that will serve as a backbone and define a scale for the rating, all the other rules being then integrated within this hierarchy.
That's how I've proceeded for the NRCZT-rating.
Notice that we have no result on a potential rating based on AICs with ALSs. Such AICs could have been the backbone of SER but, instead, they are given arbitrary values and are arbitrarily mixed with lots of other unrelated patterns.


5) Given two ratings as above, with different backbones, how do they compare?
We've seen that, for non exceptionally hard puzzles, the most common ratings are reasonably well (but not strongly) correlated.


6) How do we assess the validity of a rating?
As there is no universal rating, this is impossible in an absolute sense. One may compare a rating with one's intuitions, but the result is very likely to be different for different persons.
However, given several formal ratings based on different approaches, if they are strongly correlated, it is likely that they all capture some important aspects of the puzzles. This is some statistical cross validity check.
Of course, statistical cross validity itself has limited validity. But the clearer the basic principles of each rating the better we can analyse the discrepancies between the ratings on particular puzzles.


7) When a new resolution rule appears (e.g. Steve's), how can it be taken into account in the existing ratings?
It can easily be observed that the addition of a really new resolution rule radically modifies any rating - in the sense that it reverses the relative places of many puzzles.
But a single resolution rule with no parameter can hardly be the basis for a new rating if it is not itself included in a broader parameterised set of rules. As of now, what such a set should be for Steve's pattern remains unclear as it is only inherent to the exceptionally symmetric EM family.


8) Human vs computer solving and rating

One common feature of existing ratings is that they are produced by a computer, based on fixed set of rules.
A human solver can dynamically combine the resolution rules from a given fixed set (e.g. using my partial chains theorems, if the set is NRCZT). In the 7th post of this page: http://www.sudoku.com/boards/viewtopic.php?t=5600&start=135, I've given an example of a manual solution, with the insertion of a remote pairs chain within an nrczt-chain.
Unfortunately, allowing such dynamic combinations in a solver/rater would make it very inefficient - increasing exponentially the number of patterns to be analysed in a systematic way.

The problem is that human solvers may have shortcuts to detect very special cases of general patterns whereas, as long as we have no idea of what is so easily detected by a human solver, we have no choice but having our solvers check all the cases.

This adds one more general question to my previous list: do we care about the computation times?





4) NEW EXTENDED STATISTICAL RESULTS

In this section, I'll report my new results using a collection of 1,000,000 puzzles: sudogen0_1M (an extension of the above mentioned sudogen_0 collection).

sudogen0_1M is a random sample of 1,000,000 different independent minimal puzzles generated with the suexg program (with seed 0). More on it in the second subsection.


4.1) STATISTICAL RESULTS

Using this extended sudogen0_1M collection, I computed the following variables for all the puzzles in it: the NRCZT-ratings, the SER ratings, the number of clues, the number of partial nrczt-chains.

4.1.1) Correlation coefficients:

NRCZT vs SER : 0.895
This confirms what I had already shown with the first 10,000 puzzles in the collection: although the SER and NRCZT ratings are based on very different sets of rules, they are very strongly correlated. It suggests that they capture some intrinsic complexity of the puzzles.

NRCZT vs log(#chains) : 0.946
This confirms that the maximum length of chains necessary to solve it is statistically a very good indicator for the complexity of a puzzle: the more useless partial chains there are, the harder it is to find the useful ones. The number of useless partial chains increases exponentially with the length of the longer chain necessary to solve the puzzle (in the range of validity of these results : 1 to 10).

NRCZT vs #clues : 0.115
SER vs #clues : 0.121
This gives a precise meaning to what was already intuitively known concerning the number of clues: it has no significant impact on the complexity of minimal puzzles.


4.1.2) Number of puzzles per number of clues and mean number of clues: (all the puzzles in the collection have between 20 and 30 clues).

nb-clues   nb-puzzles
  20         44
  21         2,428
  22         34,548
  23         172,512
  24         342,335
  25         297,838
  26         122,116
  27         25,315
  28         2,686
  29         168
  30         10


mean number of clues for minimal puzzles in Sudogen0_1M = 24.38
standard deviation = 1.12

This shows that puzzles with less than 20 or more than 30 clues are extremely rare - in frequency. (Notice however that, in numbers, as there are billions of billions of minimal puzzles, "extremely rare" may still mean thousands or millions - we already know more than 64,000 17-clue puzzles).
Most of the puzzles have between 23 and 26 clues.




4.1.3) The SER in the collection varies upto 9.2. It is very difficult to randomly generate puzzles with SER > 9.2.


4.1.4) Number of puzzles per NRCZT-level :


Level    Number     Total
1_0      417,624      417,624
1          120,618      538,242
2          138,371      676,613
3          168,562      845,175
4          122,946      968,121
5          24,187        992,308
6          5,511          997,819
7          1,514          999,333
8          473            999,806
9          130            999,936
10         38             999,974
11         15             999,989
12         9              999,998
13         2              1,000,000
14         0    

This confirms that:
- more than 99% of the minimal puzzles can be solved with whips of length 5 or less;
- more than 99.9% of the minimal puzzles can be solved with whips of length 7 or less;
- "almost all" the puzzles can be solved with nrczt-whips of length 13 or less (exceptions are less than one in a million).

Of course, such statistical results can't say anything about extreme cases with very low probability (e.g. cases with very special symmetries, such as the EasterMonster family).




4.2) THE SUDOGEN0_1M COLLECTION

sudogen0_1M is a random sample of 1,000,000 different independent minimal puzzles generated with the suexg program (with seed 0).

suexg is a free program developed by Guenter Stertenbrink........ aka dukuso at Magictour (thanks Coloin for the exact name). Generating 1,000,000 minimal puzzles takes only a few hours, even on an old micro-computer.
There are several versions of it. For definiteness, a copy of the exact version I use is available here.

Ever since I started being interested in Sudoku, I've used the "small" sudogen0 collection with 10,000 puzzles, but I've now extended it to 1,000,000. The reason is that hard puzzles are very rare (in frequency) and the higher we want to go into the complexity hierarchy (as reflected, say, by the NRCZT-level) the more puzzles we need to analyse.

Now, the question that naturally arises is: how random is the "large" sudogen0_1M collection? This is a major question, because randomness is what allows to extend the results in the above subsection from the sudogen0_1M collection to the full set of all the minimal puzzles.

"Real randomness" can rarely be fully proven, but good indicators of randomness can be checked.

The first thing that can be checked is that all the puzzles are different. This is relatively easy to do.
Another thing one might want to check is that no two of them are essentially equivalent. I haven't done this, first because it would have been one more long computation and secondly because it isn't really relevant here: we are dealing with minimal puzzles and not with equivalence classes of such puzzles. Anyway, in terms of proportions, even if a few puzzles were essentially equivalent, this wouldn't change the results. If anyone has a fast checker of essential-equivalence, he can do it. Also, as Coloin pointed out to me in a mail after I published these results, the probability of two puzzles being essentially equivalent in a 1,000,000-puzzle random sequence is very low.

The second thing one is expecting from a random collection is the independence of the puzzles in it. As usual, independence of a sequence of non-numerical variables (the puzzles) can be tested indirectly through the (normalised) auto-correlation function of one (or more) numerical function(s) of this variable.
The numerical functions of the puzzles I'll consider here are:
- the number of clues
- the NRCZT rating
- the SER (Sudoku Explainer Rating)

What is the (normalised) auto-correlation function? Its k-th value (which is a number between -1 and +1) measures the degree of correlation between any element in the sequence and the element k places after it. (You can check the precise definition in any textbook on statistics of sequences).
How did I compute it? I used the Matlab software, with the exact function: xcorr(x, maxlag,'unbiased'); here "maxlag" is a parameter allowing to specify that we don't take into account values of k (beyond maxlag) that would rely on too few puzzles; I chose maxlag = 990,000; x is the vector representing the sequence of values of the function we want to check.

Now for the results:
Apart for k=0, which must always give 1, the maximum absolute values for the correlation function were:
- for the number of clues: 0,041
- for the SER: 0,037
- for the NRCZT: 0,039
All these values are very small. All these sequences of variables are white noise.

Conclusion: wrt to all the above criteria, the sudogen0_1M sequence has null auto-correlation.

In order to allow anyone to check these results and complete them with his own, here are the full lists of puzzles and results:
- list of the 1,000,000 puzzles in the sudogen0_1M collection, gziped version (24.2 Mb)
- list of the 1,000,000 solution grids (gziped version, 34.1 Mb)
- list of their numbers of clues (2.9 Mb),
- list of their SER (3.8 Mb),
- list of their NRCZT ratings (2.7 Mb).





4.3) OTHER COLLECTIONS AND CLASSIFICATION RESULTS

Additional results and comparisons between random puzzles generators are available in the classification page.







5) HOW HARD IS IT TO PROVE THAT A PUZZLE HAS NO SOLUTION?


It can be as hard as finding a solution.
The following puzzle with a wrong clue was provied by Coloin.

000001200
031040050
607500800
700000100
050000060
009000003
002007304
070090080
004800000

wrong clue at r2c3

I get the following resolution path, which shows that proving invalidity can be very far from obvious if one doesn't use T&E. Here an nrczt-whip[8] is necessary. The NRCZT rating of this invalid puzzle is thus NRCZT8.


(solve ".....12...31.4..5.6.75..8..7.....1...5.....6...9.....3..2..73.4.7..9..8...48.....")
*****  SudoRules version 13.7wter  *****
000001200031040050607500800700000100050000060009000003002007304070090080004800000
interaction column c7 with block b6 for number 4 ==> r6c8 <> 4, r4c8 <> 4
hidden-pairs-in-a-column c8{n3 n4}{r1 r3} ==> r3c8 <> 9, r3c8 <> 1
hidden-single-in-block b3 ==> r3c9 = 1
hidden-pairs-in-a-column c8{n3 n4}{r1 r3} ==> r1c8 <> 9, r1c8 <> 7
nrct-chain[2]  r8n1{c4 c1} - c2n1{r9 r6} ==> r6c4 <> 1
nrc-chain[3]  r3n9{c6 c2} - b1n2{r3c2 r2c1} - r2n8{c1 c6} ==> r2c6 <> 9
nrczt-whip[3]  r2n8{c6 c1} - r7n8{c1 c2} - r6n8{c2 .} ==> r4c6 <> 8, r5c6 <> 8
nrczt-whip[4]  r7c4{n6 n1} - c8n1{r7 r9} - c2n1{r9 r6} - r6n6{c2 .} ==> r4c4 <> 6
nrc-chain[5]  r5c3{n3 n8} - c9n8{r5 r4} - b6n5{r4c9 r6c7} - r8c7{n5 n6} - c3n6{r8 r4} ==> r4c3 <> 3
interaction row r4 with block b5 for number 3 ==> r5c6 <> 3, r5c5 <> 3, r5c4 <> 3
nrct-chain[5]  r8c7{n6 n5} - b6n5{r6c7 r4c9} - c9n8{r4 r5} - r5c3{n8 n3} - r8c3{n3 n6} ==> r8c9 <> 6, r8c6 <> 6, r8c4 <> 6
nrct-chain[5]  r8c9{n2 n5} - r8c7{n5 n6} - r8c3{n6 n3} - r5c3{n3 n8} - c9n8{r5 r4} ==> r4c9 <> 2
nrczt-whip[7]  r4c8{n2 n9} - r7c8{n9 n1} - r7c4{n1 n6} - r7c5{n6 n5} - c6n5{r9 r6} - c6n8{r6 r2} - c6n6{r2 .} ==> r4c6 <> 2
nrczt-whip[8]  r7c4{n6 n1} - r8n1{c4 c1} - r5n1{c1 c5} - r9n1{c5 c8} - c8n7{r9 r6} - c5n7{r6 r1} - b2n8{r1c5 r2c6} - b2n6{r2c6 .} ==> r6c4 <> 6
nrczt-whip[6]  r6c8{n2 n7} - r6c4{n7 n4} - r5c6{n4 n9} - r3n9{c6 c2} - c2n2{r3 r4} - r4n4{c2 .} ==> r6c5 <> 2, r6c6 <> 2
nrczt-whip[7]  r6c8{n7 n2} - r6c4{n2 n4} - r4n4{c6 c2} - c2n2{r4 r3} - r3n9{c2 c6} - r5c6{n9 n2} - c1n2{r5 .} ==> r6c7 <> 7, r6c5 <> 7
nrczt-whip[7]  r8n1{c1 c4} - r7c4{n1 n6} - r7c5{n6 n5} - c5n1{r7 r5} - c5n7{r5 r1} - b2n8{r1c5 r2c6} - b2n6{r2c6 .} ==> r6c1 <> 1
nrczt-whip[6]  c3n6{r4 r8} - r8c7{n6 n5} - r6c7{n5 n4} - r6c1{n4 n2} - r6c8{n2 n7} - r6c4{n7 .} ==> r4c3 <> 8
singles ==> r4c3 = 6, r8c7 = 6
nrc-chain[3]  c2n6{r9 r7} - r7c4{n6 n1} - r8n1{c4 c1} ==> r9c2 <> 1
nrc-chain[5]  b6n5{r6c7 r4c9} - b6n8{r4c9 r5c9} - r5c3{n8 n3} - r8c3{n3 n5} - r7n5{c1 c5} ==> r6c5 <> 5
nrct-chain[5]  b4n1{r6c2 r5c1} - r5n3{c1 c3} - c3n8{r5 r1} - b1n5{r1c3 r1c1} - c1n4{r1 r6} ==> r6c2 <> 4
nrczt-whip[5]  r6c8{n2 n7} - r6c4{n7 n4} - r6c1{n4 n8} - r7n8{c1 c2} - c2n1{r7 .} ==> r6c2 <> 2
nrc-chain[3]  r3n9{c6 c2} - c2n2{r3 r4} - r4c8{n2 n9} ==> r4c6 <> 9
nrczt-whip[5]  r2n8{c6 c1} - r7n8{c1 c2} - b7n6{r7c2 r9c2} - c6n6{r9 r6} - c6n8{r6 .} ==> r2c6 <> 2
nrc-chain[2]  r2n2{c4 c1} - c2n2{r3 r4} ==> r4c4 <> 2
nrc-chain[5]  r2n2{c4 c1} - c2n2{r3 r4} - r4c8{n2 n9} - r7c8{n9 n1} - r7c4{n1 n6} ==> r2c4 <> 6
nrct-chain[4]  c5n7{r5 r1} - b2n8{r1c5 r2c6} - r2n6{c6 c9} - r2n7{c9 c7} ==> r5c7 <> 7
xyzt-chain[5]  r5c7{n4 n9} - r4c8{n9 n2} - r6c8{n2 n7} - r6c4{n7 n2} - r5c6{n2 n4} ==> r5c4 <> 4
nrczt-whip[5]  r4c8{n2 n9} - r5c7{n9 n4} - r5c6{n4 n9} - r3n9{c6 c2} - c2n2{r3 .} ==> r4c5 <> 2
nrczt-whip[2]  r2n2{c1 c4} - b5n2{r5c4 .} ==> r5c1 <> 2
nrct-chain[4]  b4n2{r6c1 r4c2} - r4c8{n2 n9} - r5c7{n9 n4} - b4n4{r5c1 r6c1} ==> r6c1 <> 8
naked-triplets-in-a-row r6{c1 c4 c8}{n2 n4 n7} ==> r6c7 <> 4
singles ==> r6c7 = 5, r5c7 = 4
hidden-pairs-in-a-block b4{r4c2 r6c1}{n2 n4} ==> r4c2 <> 8
naked-triplets-in-a-row r6{c1 c4 c8}{n2 n4 n7} ==> r6c6 <> 4
naked-pairs-in-a-column c6{r2 r6}{n6 n8} ==> r9c6 <> 6
nrc-chain[4]  r8c3{n3 n5} - r7n5{c1 c5} - r4n5{c5 c6} - c6n4{r4 r8} ==> r8c6 <> 3
nrct-chain[4]  c7n9{r2 r9} - c8n9{r9 r4} - r4n2{c8 c2} - c1n2{r6 r2} ==> r2c1 <> 9
nrc-chain[5]  r4c9{n8 n9} - r4c8{n9 n2} - c2n2{r4 r3} - r2c1{n2 n8} - c6n8{r2 r6} ==> r4c5 <> 8
hidden-single-in-row r4 ==> r4c9 = 8
xyzt-chain[5]  r7c4{n1 n6} - r7c5{n6 n5} - r4c5{n5 n3} - r3c5{n3 n2} - r9c5{n2 n1} ==> r8c4 <> 1
singles ==> r8c1 = 1, r6c2 = 1
interaction row r6 with block b5 for number 8 ==> r5c5 <> 8
nrc-chain[3]  c4n1{r5 r7} - r7c8{n1 n9} - r4n9{c8 c4} ==> r5c4 <> 9
nrc-chain[4]  c4n1{r5 r7} - r7c8{n1 n9} - b6n9{r4c8 r5c9} - r5c6{n9 n2} ==> r5c4 <> 2
nrc-chain[4]  r4c2{n4 n2} - r4c8{n2 n9} - b5n9{r4c4 r5c6} - r3n9{c6 c2} ==> r3c2 <> 4
singles ==> r3c8 = 4, r1c8 = 3
nrc-chain[3]  r1n4{c1 c2} - r4c2{n4 n2} - r3c2{n2 n9} ==> r1c1 <> 9
interaction column c1 with block b7 for number 9 ==> r9c2 <> 9
naked-single ==> r9c2 = 6
interaction column c1 with block b7 for number 9 ==> r7c2 <> 9
naked-single ==> r7c2 = 8
nrc-chain[4]  r7n5{c1 c5} - r4c5{n5 n3} - c4n3{r4 r8} - b7n3{r8c3 r9c1} ==> r9c1 <> 5
nrc-chain[3]  b9n5{r9c9 r8c9} - b7n5{r8c3 r7c1} - c1n9{r7 r9} ==> r9c9 <> 9
nrc-chain[4]  r9c7{n7 n9} - b7n9{r9c1 r7c1} - b7n5{r7c1 r8c3} - b9n5{r8c9 r9c9} ==> r9c9 <> 7
naked-pairs-in-a-block b9{r8c9 r9c9}{n2 n5} ==> r9c8 <> 2
interaction column c8 with block b6 for number 2 ==> r5c9 <> 2
interaction row r5 with block b5 for number 2 ==> r6c4 <> 2
nrc-chain[3]  c6n9{r3 r5} - b5n2{r5c6 r5c5} - r3c5{n2 n3} ==> r3c6 <> 3
r5c1 = 3,singles ==> r3c5 = 3, r4c5 = 5, r7c1 = 5, r8c3 = 3, r9c1 = 9, r9c7 = 7, r2c7 = 9, r9c8 = 1, r7c8 = 9, r4c8 = 2, r6c8 = 7, r5c9 = 9, r5c6 = 2, r3c6 = 9, r3c2 = 2, r2c1 = 8, r1c3 = 5, r1c1 = 4, r6c1 = 2, r1c2 = 9, r2c6 = 6, r1c4 = 7, r2c4 = 2, r8c4 = 4
GRID 0 HAS NO SOLUTION : NO CANDIDATE FOR RN-CELL r6n4
LEVEL = NRCZT8, MOST COMPLEX RULE = NRCZT8



Still harder examples can be found here.






**************






6) pNRCZT, THE PURE NRCZT RATING

At the beginning of this page, I have considered the NRCZT rating, based on the rules defined in my book and in various pages here. Remember that this rating is based on 5 different families of rules:
1) ECP (elementary constraints propagation)
2) NS+HS (naked and hidden singles)
3) basic interaction rules
4) subset rules (basic naked, hidden and super-hidden rules for pairs, triplets and quadruplets)
5) the xy to nrczt family
(see the aforementioned post for details)


Apart from the families 1 and 2, for which it is difficult to imagine that they would not be included in any set of resolution rules, there remains 3 families of rules based on different "logics", i.e. that are usually based on different kinds of proofs.
When I defined the NRCZT rating, I knew that most rules in family 4 are subsumed by nrczt-chains, but I didn't know yet that family 3 is completely subsumed by nrczt-chain[´] (indeed equivalent to it).
With this new knowledge and with an additional knowledge about what "most" means in the previous sentence, it is now natural to define a priori the following pNRCZT or pure NRCZT rating.


Rules allowed at the different levels of the pNRCZT rating:
pNRCZT0: ECP (no unsolved puzzle can be solved at this level)
pNRCZT1_0 : NS + HS
pNRCZT1: rules for nrczt-whips of length 1 (equivalent to rules for elementary interactions)
pNRCZT2 :rules for nrczt whips of length 2
....
pNRCZTn :rules for nrczt whips of length n


Let T(pNRCZTn) be the first order logic theory with the set of rules in pNRCZTn
What I said of the T(NRCZTn) can be repeated here for the T(pNRCZTn):
- they are a sequence of logical theories of increasing strength;
- each of them is invariant under symmetry and supersymmetry; this entails that the pNRCZTn stratification and the pNRCZT rating are invariant under symmetry;
- none of them is complete; i.e. none of them can solve any valid puzzle with a unique solution; (notice that this is the case for any currently known set of resolution rules);
- nevertheless, pL7 is enough to solve 99,99% of the minimal puzzles and in 10,000,000 puzzles randomly generated with different types of gener   tors, none was found that couldn't be classified.


The pNRCZT rating:
- has well defined groundings in first order logic,
- is defined in a purely logical way, independent of any implementation and of any solver,
- is invariant under symmetry (legal permutations of rows, columns, floors, towers, row-column symmetry),
- is based on a single homogeneous family of fully super-symmetric rules, the rules for nrczt chains and lassos (apart from basic constraints propagation and singles), which are the most general first order chain rules,
- is naturally defined by a single parameter: the length of the longest nrczt chain or lasso necessary to solve a puzzle,
- is able to rate almost all the minimal puzzles.
Notice that (see above) it is also able to rate the difficulty of proving that an invalid puzzle has no solution.

The pNRCZT rating is a priori always larger than the NRCZT rating. But, the pNRCZT rating differs from the NRCZT rating in less than 1/1,000 cases. As a result:
All the correlation results above for the NRCZT rating remain unchanged for the pNRCZT rating.
Using one rating instead of the other in correlation studies is empirically justified on a statistical basis.
The reason is that the proportion of puzzles for which the two ratings are different is so small that it can't change the correlations.

The present definition has a very practical impact: a new solver/rater could be written, that contains only nrczt-chain rules and is optimised for them (which is not the case for SudoRules).


There is also a more theoretical interest in the pNRCZT rating: it defines a very homogeneous scale along which any new resolution rule can be measured.
For instance, somehow reversing things with respect to to the original NRCZT rating, we can now ask questions such as: what is the impact of adding the (naked, hidden and super-hidden) subset rules in the pure nrczt hierarchy (thus getting the previously defined - should I say impure? - NRCZT rating)? And we can answer that the impact is very small (i.e. pNRCZT = NRCZT for more than 99.9% of the minimal puzzles).




The detailed classification results of the full sudogen0 random collection of 10,000 minimal puzzles for the pNRCZT rating are available here.

Number of puzzles by level:

pNRCZT1_0: 4247
pNRCZT1: 1135
pNRCZT2: 1408
pNRCZT3: 1651
pNRCZT4: 1248
pNRCZT5: 240
pNRCZT6: 56
pNRCZT7: 10
pNRCZT8: 2
pNRCZT9: 1
pNRCZT10: 1
pNRCZT11: 0
pNRCZT12: 1






7) The B-NRCZT and the pB-NRCZT RATINGS

As a result of the introduction of nrczt-braids, one can introduce a new rating, the pB-NRCZT rating ("pure B-NRCZT rating). It is defined in a way similar to the previous p-NRCZT rating, but with nrczt-braids replacing nrczt-whips.
Rules allowed at the different levels of the pB-NRCZT rating:
pB-NRCZT0: ECP (no unsolved puzzle can be solved at this level)
pB-NRCZT1_0 : NS + HS
pB-NRCZT1: rules for nrczt braids of length 1 (equivalent to elementary interactions)
....
pB-NRCZTn : rules for nrczt-braids of length n

It can be shown that it has all the good properties of one can expect from a rating.
The pB-NRCZT rating:
- is defined in a purely logical way, independent of any solver;
- is invariant under symmetry and supersymmetry;
- is based on theories with the confluence property.


Moreover, as a result of the theorem on T&E vs nrczt-braids, we can say precisely for which puzzles the B-NRCZT rating can be computed: exactly for those that are solvable by T&E(ECP+NS+HS) - a condition very easy to check by a very simple program, and which covers almost all the random puzzles.


As for the whips, the B-NRCZT rating can also be defined as above, by allowing the same subset rules at levels 2 to 4.
The B-NRCZT rating:
- is defined in a purely logical way, independent of any solver;
- is invariant under symmetry and supersymmetry;
- is based on theories with the confluence property.




6.1) CLASSIFICATION OF PUZZLES ACCORDING TO THE B-NRCZT AND THE pB-NRCZT RATINGS

After a few optimisations on memory and computation time in their Sudoules implementation, I can now run the braid rules on the full sudogen0 collection (10,000 random minimal puzzles).

It appears that, if braids are given lower priority than whips of the same length but still higher prioriry than longer whips (a natural combination of options that reflects their slightly greater structural complexity), braids appear much more rarely than whips in the resolution paths.

The B-NRCZT rating is a priori always smaller than the NRCZT rating.
But, it also appears that, for almost all the random puzzles, the B-NRCZT rating is equal to the NRCZT-rating. They differ in less than 2 / 1,000 of the cases.
More precisely, only 19 puzzles among the 10,000 in sudogen0 have a different (of course, smaller) B-NRCZT rating.
Eighteen of these cases have B-NRCZT = NRCZT - 1 and one case has B-NRCZT = NRCZT - 2.

As a result, all the correlation and classification results that were given for the NRCZT-rating can be straightforwardly transferred to the B-NRCZT-rating and either of them can be chosen for statistical studies.
As solutions based on whips are easier to compute than solutions allowing braids, one can say that the NRCZT rating is a good approximation of the B-NRCZT rating.


Similarly, the pB-NRCZT is a priori always smaller than pNRCZT.
In practice, pB-NRCZT is smaller than pNRCZT in only 17 cases in 10,000. And in all these cases, the difference is only 1.
One can say that the NRCZT rating is a good approximation of the B-NRCZT rating.


The detailed classification results of the full sudogen0_1M random collection of 1,000,000 minimal puzzles for the NRCZT rating are available here.
The detailed classification results of the full sudogen0 random collection of 10,000 minimal puzzles for the p-NRCZT rating are available here.
The detailed classification results of the full sudogen0 random collection of 10,000 minimal puzzles for the pB-NRCZT rating are available here.




6.2) EXAMPLES

Here is an example of a puzzle (sudogen0 #4177) with NRCZT-rating = 8 but B-NRCZT-rating = 7.

+------+-------+-------+
| x 9 1 | x x 7 | 3 x x |
| x 2 7 | x 5 x | 6 x x |
| 5 x x | x 4 x | x x x |
+------+-------+-------+
| x x x | x x 9 | x x 5 |
| x 7 x | 2 x x | x 4 x |
| 9 x x | 5 x x | 2 1 x |
+------+-------+-------+
| 1 4 x | x 9 x | x 2 x |
| 7 x x | 1 x 2 | x x x |
| x 3 x | x x x | x x x |
+------+-------+-------+


(solve ".91..73...27.5.6..5...4.........9..5.7.2...4.9..5..21.14..9..2.7..1.2....3.......")

The two resolution paths start in the same obvious way :

singles ==> r1c8 = 5, r3c9 = 2, r1c5 = 2, r5c3 = 5, r8c2 = 5, r4c2 = 1, r5c5 = 1
interaction column c7 with block b9 for number 4 ==> r9c9 <> 4, r8c9 <> 4
hidden-single-in-a-row ==> r8c7 = 4
interaction column c3 with block b4 for number 4 ==> r4c1 <> 4
nrczt-whip[2]  c5n3{r6 r8} - c8n3{r8 .} ==> r4c4 <> 3
nrc-chain[5]  c4n9{r3 r2} - r2c8{n9 n8} - r1c9{n8 n4} - c1n4{r1 r2} - b1n3{r2c1 r3c3} ==> r3c4 <> 3
nrczt-whip[4]  c5n3{r6 r8} - c4n3{r7 r2} - c1n3{r2 r4} - c8n3{r4 .} ==> r5c6 <> 3
 

At this point, the PM is:


+--------------------------+------------------------------+-----------------------------+
| 468     9       1             | 68       2            7          | 3         5          48          |
| 348     2       7             | 389      5           138      | 6         89        1489      |
| 5       68      368          | 689      4           1368    | 1789   789       2           |
+--------------------------+------------------------------+------------------------------+
| 2368    1       23468    | 4678    3678     9          | 78        3678    5            |
| 368     7       5             | 2          1          68         | 89        4          3689      |
| 9         68      3468      | 5          3678    3468     | 2          1          3678      |
+---------------------------+-----------------------------+------------------------------+
| 1         4       68           | 3678    9          3568     | 578       2          3678     |
| 7         5       689         | 1          368      2           | 4           3689    3689     |
| 268     3       2689       | 4678    678      4568     | 15789   6789    16789   |
+---------------------------+-----------------------------+------------------------------+


The resolution path with whips continues (using SudoRules version 13.7wter):
A: nrczt-whip[7]  r4c7{n8 n7} - r7c7{n7 n5 n8*} - r9n5{c7 c6} - r9n4{c6 c4} - c4n7{r9 r7 r4#1} - c9n7{r7 r9 r4#1 r6#1} - r9n1{c9 . c7*} ==> r9c7 <> 8
nrct-chain[8]  r5c7{n9 n8} - r4c7{n8 n7} - r7c7{n7 n5} - r9n5{c7 c6} - b8n4{r9c6 r9c4} - c4n7{r9 r7} - c4n3{r7 r2} - c4n9{r2 r3} ==> r3c7 <> 9

;;; 2 chains of length 8 appear here:
nrct-chain[8]  r5c7{n9 n8} - r4c7{n8 n7} - r7c7{n7 n5} - r9n5{c7 c6} - b8n4{r9c6 r9c4} - c4n7{r9 r7} - c4n3{r7 r2} - c4n9{r2 r3} ==> r3c7 <> 9
nrct-chain[8]  r5c7{n9 n8} - r4c7{n8 n7} - r3c7{n7 n1} - r9n1{c7 c9} - c9n7{r9 r7} - c4n7{r7 r9} - b8n4{r9c4 r9c6} - r9n5{c6 c7} ==> r9c7 <> 9
hidden-single-in-column c7 ==> r5c7 = 9
nrct-chain[6]  b1n3{r3c3 r2c1} - r2n4{c1 c9} - c9n1{r2 r9} - c9n9{r9 r8} - b7n9{r8c3 r9c3} - c3n2{r9 r4} ==> r4c3 <> 3
nrczt-whip[6]  r2n4{c1 c9} - r1c9{n4 n8} - r2c8{n8 n9} - r3n9{c8 c4} - r3n8{c4 c6} - r5n8{c6 .} ==> r2c1 <> 8
nrczt-whip[6]  b1n3{r3c3 r2c1} - r2n4{c1 c9} - c9n1{r2 r9} - c9n9{r9 r8} - r8c3{n9 n8} - r7c3{n8 .} ==> r3c3 <> 6
nrczt-whip[6]  r2c1{n4 n3} - r3c3{n3 n8} - r7c3{n8 n6} - r8c3{n6 n9} - c9n9{r8 r9} - c9n1{r9 .} ==> r2c9 <> 4
hidden-singles ==> r1c9 = 4, r2c1 = 4, r3c3 = 3
nrczt-whip[4]  r5c6{n8 n6} - r3c6{n6 n1} - c7n1{r3 r9} - r9n5{c7 .} ==> r9c6 <> 8
nrczt-whip[4]  r5c6{n6 n8} - r3c6{n8 n1} - c7n1{r3 r9} - r9n5{c7 .} ==> r9c6 <> 6
nrczt-whip[5]  r5c6{n6 n8} - r3c6{n8 n1} - c7n1{r3 r9} - r9n5{c7 c6} - c6n4{r9 .} ==> r6c6 <> 6
nrczt-whip[5]  b4n3{r5c1 r4c1} - c8n3{r4 r8} - c5n3{r8 r6} - r6n7{c5 c9} - r6n6{c9 .} ==> r5c1 <> 6
nrczt-whip[5]  r5c6{n8 n6} - r3c6{n6 n1} - c7n1{r3 r9} - r9n5{c7 c6} - c6n4{r9 .} ==> r6c6 <> 8
nrct-chain[5]  b4n2{r4c1 r4c3} - c3n4{r4 r6} - r6c6{n4 n3} - c5n3{r4 r8} - c8n3{r8 r4} ==> r4c1 <> 3
hidden-single-in-block b4 ==> r5c1 = 3
nrc-chain[3]  r5n8{c6 c9} - r4c7{n8 n7} - r6n7{c9 c5} ==> r6c5 <> 8
nrczt-whip[5]  c3n4{r4 r6} - r6c6{n4 n3} - c5n3{r6 r8} - c5n8{r8 r9} - b7n8{r9c3 .} ==> r4c3 <> 8
nrczt-whip[5]  c4n4{r4 r9} - r9c6{n4 n5} - c7n5{r9 r7} - r7n7{c7 c9} - r6n7{c9 .} ==> r4c4 <> 7
interaction column c4 with block b8 for number 7 ==> r9c5 <> 7
nrc-chain[4]  r6c6{n3 n4} - c4n4{r4 r9} - b8n7{r9c4 r7c4} - c4n3{r7 r2} ==> r2c6 <> 3
singles ==> r2c4 = 3, r3c4 = 9
naked-triplets-in-a-column c6{r2 r3 r5}{n8 n1 n6} ==> r7c6 <> 8, r7c6 <> 6
nrc-chain[2]  c2n6{r6 r3} - c6n6{r3 r5} ==> r6c5 <> 6
nrc-chain[3]  c9n1{r9 r2} - r2c6{n1 n8} - r5n8{c6 c9} ==> r9c9 <> 8
nrczt-whip[3]  b7n6{r9c3 r9c1} - c8n6{r9 r8} - c5n6{r8 .} ==> r4c3 <> 6
nrc-chain[4]  r4c7{n7 n8} - r5n8{c9 c6} - r2c6{n8 n1} - r3n1{c6 c7} ==> r3c7 <> 7
hidden-single-in-block b3 ==> r3c8 = 7
naked-quads-in-a-row r9{c1 c3 c8 c5}{n6 n2 n9 n8} ==> r9c9 <> 9, r9c9 <> 6, r9c4 <> 8, r9c4 <> 6
nrc-chain[4]  r4n7{c7 c5} - r6c5{n7 n3} - c6n3{r6 r7} - r7n5{c6 c7} ==> r7c7 <> 7
xyzt-chain[4]  r7c7{n8 n5} - r7c6{n5 n3} - r8c5{n3 n6} - r9c5{n6 n8} ==> r7c4 <> 8
interaction block b8 with column c5 for number 8 ==> r4c5 <> 8
nrc-chain[4]  r4n2{c1 c3} - r4n4{c3 c4} - c4n8{r4 r1} - r1n6{c4 c1} ==> r4c1 <> 6
interaction block b4 with row r6 for number 6 ==> r6c9 <> 6
nrc-chain[4]  r4c1{n8 n2} - b7n2{r9c1 r9c3} - r9n9{c3 c8} - r2c8{n9 n8} ==> r4c8 <> 8
nrc-chain[4]  r9c6{n5 n4} - r9c4{n4 n7} - r7n7{c4 c9} - r7n3{c9 c6} ==> r7c6 <> 5
singles
GRID 0 SOLVED. LEVEL = NRCZT8, MOST COMPLEX RULE = NRCT8
691827354
427351689
583946172
214679835
375218946
968534217
146793528
759182463
832465791



The resolution path with braids continues (using SudoRules version 13.7wbisB2):
A' : nrczt-braid[6] r9n5{c7 c6} - r9n4{c6 c4} - r4c7{n8 n7} - c4n7{r4 r7 r9#2} - c9n7{r6 r9 r7#4} - r9n1{c9 . c7*} ==> r9c7 <> 8
;;; This is the most interesting part, where we can see a braid[6] replacing the whip[7] above

;;; after that, the two resolution paths diverge and can't be compared, but all the whips and braids have now a length strictly smaller than 7
nrczt-braid-cn[6] n6{r3c4 r3c6} - {n6 n8}r3c2 - {n6 n8}r7c3 - {n6 n8}r5c6 - n8{r1c1 r4c1} - {n8r3c7 .} ==> r7c4 <> 6
nrczt-whip-cn[5] n4{r4c3 r4c4} - n4{r9c4 r9c6} - n5{r9c6 r7c6} - n6{r7c6 r7c9} - {n6r9c8 .} ==> r4c3 <> 6
;;; braids of length 7 appear here:
nrczt-braid-rn[7] n3{r5c1 r2c1} - n4{r2c1 r2c9} - n1{r2c9 r9c9} - n2{r4c3 r9c3} - n9{r9c3 r8c3} - n9{r2c9 r5c9} - {n3r5c9 .} ==> r4c3 <> 3
nrczt-braid-cn[7] n4{r6c6 r6c3} - n3{r6c3 r3c3} - {n8 n6}r5c6 - {n8 n1}r3c6 - n1{r3c7 r9c7} - n5{r9c7 r9c6} - {n4r9c6 .} ==> r6c6 <> 8, r6c6 <> 6
nrct-chain[5] n2{r4c1 r4c3} - n4{r4c3 r6c3} - {n4 n3}r6c6 - n3{r6c5 r8c5} - n3{r8c8 r4c8} ==> r4c1 <> 3
nrczt-whip-cn[6] n7{r6c9 r6c5} - n7{r9c5 r9c4} - n4{r9c4 r4c4} - {n4 n3}r6c6 - n3{r7c6 r7c4} - {n3r8c5 .} ==> r7c9 <> 7
nrc-chain[4] {n9 n8}r5c7 - {n8 n7}r4c7 - n7{r6c9 r9c9} - n1{r9c9 r9c7} ==> r9c7 <> 9
nrc-chain[4] n5{r7c7 r9c7} - n1{r9c7 r9c9} - n7{r9c9 r6c9} - {n7 n8}r4c7 ==> r7c7 <> 8
nrczt-whip-cn[2] n8{r6c2 r3c2} - {n8r3c7 .} ==> r6c9 <> 8
nrczt-whip-rc[3] n8{r6c3 r6c5} - n7{r6c5 r6c9} - {n7r4c7 .} ==> r4c1 <> 8
nrczt-whip-rc[3] n8{r6c3 r6c5} - n7{r6c5 r6c9} - {n7r4c7 .} ==> r4c3 <> 8
nrc-chain[4] n6{r1c4 r1c1} - {n6 n2}r4c1 - {n2 n4}r4c3 - n4{r4c4 r9c4} ==> r9c4 <> 6
nrc-chain[4] n9{r3c4 r2c4} - n3{r2c4 r7c4} - n7{r7c4 r7c7} - n7{r3c7 r3c8} ==> r3c8 <> 9
nrc-chain[5] n1{r2c6 r3c6} - n1{r3c7 r9c7} - n5{r9c7 r7c7} - n7{r7c7 r7c4} - n3{r7c4 r2c4} ==> r2c6 <> 3
nrc-chain[3] n9{r3c4 r2c4} - n3{r2c4 r3c6} - n1{r3c6 r3c7} ==> r3c7 <> 9
hidden-singles ==> r5c7 = 9, r3c4 = 9
nrczt-whip-cn[3] n8{r3c7 r4c7} - n8{r5c9 r5c1} - {n8r6c2 .} ==> r3c6 <> 8
nrczt-whip-bn[3] {n8 n6}r3c2 - n6{r3c6 r1c4} - {n8r1c4 .} ==> r2c1 <> 8
nrczt-whip-rn[4] n1{r9c9 r2c9} - {n1 n8}r2c6 - n8{r5c6 r5c1} - {n8r1c1 .} ==> r9c9 <> 8
nrct-chain[5] n8{r4c7 r3c7} - n1{r3c7 r2c9} - {n1 n8}r2c6 - n8{r1c4 r1c1} - n8{r5c1 r5c9} ==> r4c8 <> 8
nrct-chain[5] n4{r9c4 r4c4} - n4{r6c6 r9c6} - n5{r9c6 r7c6} - {n5 n7}r7c7 - n7{r7c4 r9c4} ==> r9c4 <> 8
nrczt-whip-rc[5] {n8 n7}r4c7 - n7{r6c9 r9c9} - {n7 n4}r9c4 - {n4 n6}r4c4 - {n6r5c6 .} ==> r4c5 <> 8
nrczt-whip-rc[4] n8{r8c5 r6c5} - n8{r6c3 r5c1} - n3{r5c1 r2c1} - {n3r2c4 .} ==> r7c4 <> 8
nrc-chain[4] n4{r6c6 r4c4} - {n4 n7}r9c4 - {n7 n3}r7c4 - n3{r2c4 r3c6} ==> r6c6 <> 3
naked and hidden singles ==> r6c6 = 4, r9c4 = 4, r4c3 = 4, r4c1 = 2, r9c3 = 2, r8c3 = 9
interaction block b5 with column c5 for number 3 ==> r8c5 <> 3
interaction row r8 with block b9 for number 3 ==> r7c9 <> 3
naked-pairs-in-a-row {n6 n8}r7{c3 c9} ==> r7c6 <> 8, r7c6 <> 6
hidden-pairs-in-a-column {n1 n9}{r2 r9}c9 ==> r9c9 <> 7
naked and hidden singles ==> r6c9 = 7, r4c7 = 8
interaction column c4 with block b2 for number 8 ==> r2c6 <> 8
naked and hidden singles
GRID 4177 SOLVED. LEVEL = B-NRCZT7, MOST COMPLEX RULE = B-NRCZT7
691827354
427351689
583946172
214679835
375218946
968534217
146793528
759182463
832465791





Here is now an example of a puzzle (sudogen0 #9586) with NRCZT-rating = 8 but B-NRCZT-rating = 6 (the only such case among the 10.000 sudogen0 puzzles)

+------+-------+-------+
| 5 8 x | 7 x x | x x 4 |
| x 1 x | x 9 x | x x x |
| x x 4 | x x 8 | x 3 9 |
+------+-------+-------+
| x 5 x | x x x | 7 x x |
| x x x | 9 x x | x x x |
| x x x | 6 5 2 | x x x |
+------+-------+-------+
| x x x | x x 1 | 8 x x |
| x 7 x | x x 5 | 3 x x |
| 8 x x | x x x | x x 2 |
+------+-------+-------+

58.7....4.1..9......4..8.39.5....7.....9........652........18...7...53..8.......2

The two resolution paths start with:
hidden-singles ==> r1c3 = 9, r3c1 = 7, r6c3 = 7, r9c6 = 9, r6c7 = 9, r4c1 = 9, r7c2 = 9, r8c8 = 9, r5c6 = 7
interaction row r6 with block b6 for number 8 ==> r5c9 <> 8, r5c8 <> 8, r4c9 <> 8, r4c8 <> 8
interaction column c6 with block b2 for number 6 ==> r3c5 <> 6, r1c5 <> 6
interaction row r1 with block b2 for number 3 ==> r2c6 <> 3, r2c4 <> 3
hidden-pairs-in-a-row r2{n7 n8}{c8 c9} ==> r2c9 <> 6, r2c9 <> 5, r2c8 <> 6, r2c8 <> 5
interaction block b3 with column c7 for number 5 ==> r9c7 <> 5, r5c7 <> 5
hidden-pairs-in-a-row r2{n7 n8}{c8 c9} ==> r2c8 <> 2
nrczt-whip[2]  b7n4{r8c1 r9c2} - c7n4{r9 .} ==> r5c1 <> 4
nrc-chain[3]  r9c4{n3 n4} - r2n4{c4 c6} - r4c6{n4 n3} ==> r4c4 <> 3
interaction column c4 with block b8 for number 3 ==> r9c5 <> 3, r7c5 <> 3
nrct-chain[3]  r8c9{n6 n1} - b7n1{r8c1 r9c3} - r9n5{c3 c8} ==> r9c8 <> 6
nrczt-whip[3]  b1n2{r2c3 r3c2} - r3n6{c2 c7} - c7n5{r3 .} ==> r2c7 <> 2
nrc-chain[4]  c4n1{r4 r3} - r3c5{n1 n2} - c2n2{r3 r5} - r4n2{c3 c8} ==> r4c8 <> 1
nrct-chain[4]  c7n4{r5 r9} - r9c4{n4 n3} - r9c2{n3 n6} - r3n6{c2 c7} ==> r5c7 <> 6
nrct-chain[4]  r8c9{n6 n1} - r9n1{c8 c3} - b7n5{r9c3 r7c3} - c9n5{r7 r5} ==> r5c9 <> 6
nrczt-whip[4]  c2n3{r6 r9} - r9c4{n3 n4} - r2n4{c4 c6} - r4c6{n4 .} ==> r4c3 <> 3
nrczt-whip[4]  b7n1{r9c3 r8c1} - r8c9{n1 n6} - r4n6{c9 c8} - r4n2{c8 .} ==> r4c3 <> 1
nrct-chain[5]  c3n8{r5 r4} - r4n2{c3 c8} - r4n6{c8 c9} - r8c9{n6 n1} - r9n1{c8 c3} ==> r5c3 <> 1
interaction column c3 with block b7 for number 1 ==> r8c1 <> 1
nrczt-whip[5]  r9c4{n4 n3} - r9c2{n3 n6} - r3c2{n6 n2} - r2n2{c3 c4} - r7c4{n2 .} ==> r9c5 <> 4

At this point, the PM is:

+----------------------------+--------------------------+----------------------------+
| 5          8          9          | 7         123     36       | 126      126        4        |
| 236      1          236      | 245     9         46       | 56        78         78       |
| 7          26        4          | 125     12       8         | 1256    3           9         |
+----------------------------+--------------------------+----------------------------+
| 9          5          268      | 148     1348    34      | 7          246       136     |
| 1236    2346    2368    | 9         1348    7        | 124      12456   135     |
| 134      34        7          | 6         5          2        | 9          148       138     |
+----------------------------+--------------------------+----------------------------+
| 2346    9          2356    | 234     2467    1        | 8          4567      567    |
| 246     7           126      | 248     2468    5        | 3          9            16      |
| 8         346      1356     | 34       67        9        | 146      1457      2        |
+----------------------------+--------------------------+----------------------------+


and, apart from a single hard step, the puzzle is almost solved.

The path with whips continues (using SudoRules version 13.7wter):
nrczt-whip-rn[7]  r9c4{n4 n3} - r7c4{n3 n2 n4*} - r8c4{n2 n8 n4*} - r8n4{c4 c1 c5*} - r9c2{n4 n6 n3#1} - r3c2{n6 n2} - r2n2{c3 . c1#6 c4#2} ==> r7c5 <> 4
nrczt-whip-cn[8]  r9n5{c8 c3} - r9n1{c3 c7 c8*} - c7n4{r9 r5} - c8n4{r6 r7 r4#3 r5#3 r9*} - c8n5{r7 r5 r9*} - b6n2{r5c8 r4c8 r5c7#3} - c8n6{r4 r1 r5#5 r7#4} - c7n6{r3 . r1#7 r2#7 r9#2}  ==> r9c8 <> 7
hidden-single-in-a-row ==> r9c5 = 7
nrc-chain[4]  c5n6{r7 r8} - r8c9{n6 n1} - b7n1{r8c3 r9c3} - b7n5{r9c3 r7c3} ==> r7c3 <> 6
nrczt-whip[5]  r8c9{n6 n1} - r4c9{n1 n3} - r4c6{n3 n4} - c5n4{r4 r8} - b8n6{r8c5 .} ==> r7c9 <> 6
nrczt-whip[6]  b8n6{r7c5 r8c5} - b9n6{r8c9 r9c7} - r3n6{c7 c2} - r2n6{c3 c6} - c6n4{r2 r4} - c5n4{r5 .} ==> r7c1 <> 6
nrczt-whip[6]  r8c9{n1 n6} - r4c9{n6 n3} - c6n3{r4 r1} - c6n6{r1 r2} - c1n6{r2 r5} - c1n1{r5 .} ==> r6c9 <> 1
nrczt-whip[5]  b7n4{r8c1 r9c2} - b9n4{r9c8 r7c8} - c8n7{r7 r2} - c8n8{r2 r6} - r6n1{c8 .} ==> r6c1 <> 4
interaction column c1 with block b7 for number 4 ==> r9c2 <> 4
nrct-chain[3]  r9c2{n6 n3} - r9c4{n3 n4} - r8n4{c5 c1} ==> r8c1 <> 6
xyzt-chain[4]  r8c1{n2 n4} - r7c1{n4 n3} - r9c2{n3 n6} - r3c2{n6 n2} ==> r2c1 <> 2
nrc-chain[4]  r2n2{c4 c3} - r3c2{n2 n6} - r9c2{n6 n3} - c4n3{r9 r7} ==> r7c4 <> 2
naked-pairs-in-a-block b8{r7c4 r9c4}{n3 n4} ==> r8c5 <> 4
interaction column c5 with block b5 for number 4 ==> r4c6 <> 4
naked and hidden singles ==> r4c6 = 3, r1c6 = 6, r2c6 = 4, r1c5 = 3
interaction row r1 with block b3 for number 1 ==> r3c7 <> 1
interaction row r1 with block b3 for number 2 ==> r3c7 <> 2
interaction column c5 with block b5 for number 4 ==> r4c4 <> 4
interaction block b3 with column c7 for number 6 ==> r9c7 <> 6
interaction row r9 with block b7 for number 6 ==> r8c3 <> 6
naked-pairs-in-a-column c9{r4 r8}{n1 n6} ==> r5c9 <> 1
naked-pairs-in-a-block b8{r7c4 r9c4}{n3 n4} ==> r8c4 <> 4
hidden-single-in-row r8 ==> r8c1 = 4
nrc-chain[4]  r3c5{n2 n1} - c4n1{r3 r4} - c9n1{r4 r8} - r8n6{c9 c5} ==> r8c5 <> 2
x-wing-in-rows n2{r2 r8}{c3 c4} ==> r7c3 <> 2, r5c3 <> 2, r4c3 <> 2
naked and hidden singles ==> r4c8 = 2, r1c8 = 1, r1c7 = 2, r6c1 = 1, r4c5 = 4
x-wing-in-rows n2{r2 r8}{c3 c4} ==> r3c4 <> 2
nrc-chain[3]  r9n1{c3 c7} - b6n1{r5c7 r4c9} - r4n6{c9 c3} ==> r9c3 <> 6
naked and hidden singles
GRID 9590 SOLVED. LEVEL = NRCZT8, MOST COMPLEX RULE = NRCZT8
589736214
613294578
724518639
958143726
236987145
147652983
395421867
472865391
861379452


After the above PM, the path with braids continues (using SudoRules version 13.7wbisB2):
nrczt-braid-rc[6]  r9n5{c8 c3} - r9n1{c3 c7 c8*} - c7n4{r9 r5} - b3n1{r1c7 r1c8 r3c7#2} - r2c8{n7 n8} - r6c8{n8 . n1#4 n4#3} ==> r9c8 <> 7
;;; notice that we get the same elimination of n7r9c8 as after the first two steps in the path with whips, but with a braid[6] instead of a whip[8]
;;; notice that, in this braid:
;;; - the left-linking candidate of the fourth cell (n1r1c7) is not nrc-linked to the right-linking candidate of the third cell (n4r5c7), as should be the case for a whip, but is nrc-linked to the right-linking candidate of the second cell (n1r9c7)
;;; - the left-linking candidate of the fifth cell (n7r2c8) is not nrc-linked to the right-linking candidate of the fourth cell (n1r1c8), as should be the case for a whip, but is nrc-linked to the target (n7r9c8)

hidden-single-in-a-row ==> r9c5 = 7
nrc-chain[4]  n6{r7c5 r8c5} - {n6 n1}r8c9 - n1{r8c3 r9c3} - n5{r9c3 r7c3} ==> r7c3 <> 6
nrczt-whip-cn[6]  n2{r4c8 r4c3} - n6{r4c3 r4c9} - {n6 n1}r8c9 - {n1 n6}r8c3 - n6{r9c2 r9c7} - {n4r9c7 .} ==> r4c8 <> 4
interaction row r4 with block b5 for number 4 ==> r5c5 <> 4
nrct-chain[6]  n2{r5c2 r3c2} - n2{r2c1 r2c4} - {n2 n1}r3c5 - {n1 n3}r1c5 - {n3 n8}r5c5 - n8{r5c3 r4c3} ==> r4c3 <> 2
hidden-single-in-a-row ==> r4c8 = 2
nrc-chain[3]  {n1 n6}r8c9 - n6{r4c9 r5c8} - n5{r5c8 r5c9} ==> r5c9 <> 1, r9c8 <> 1
nrc-chain[3]  n1{r9c3 r9c7} - {n1 n6}r8c9 - n6{r4c9 r4c3} ==> r9c3 <> 6
x-wing-in-rows n6{r3 r9}{c2 c7} ==> r5c2 <> 6, r2c7 <> 6
naked and hidden singles ==> r2c7 = 5, r3c4 = 5, r4c4 = 1, r8c4 = 8
x-wing-in-rows n6{r3 r9}{c2 c7} ==> r1c7 <> 6
nrc-chain[3]  n3{r4c6 r1c6} - n6{r1c6 r1c8} - n6{r5c8 r4c9} ==> r4c9 <> 3
naked and hidden singles ==> r4c9 = 6, r8c9 = 1, r4c3 = 8, r5c5 = 8, r9c3 = 1, r7c3 = 5, r7c9 = 7, r2c9 = 8, r6c9 = 3, r5c9 = 5, r6c2 = 4, r6c1 = 1, r6c8 = 8, r2c8 = 7, r9c8 = 5
xy-chain[3]  {n2 n3}r5c2 - {n3 n6}r9c2 - {n6 n2}r8c3 ==> r5c3 <> 2
nrc-chain[2]  n2{r7c4 r2c4} - n2{r2c3 r8c3} ==> r8c5 <> 2
interaction row r8 with block b7 for number 2 ==> r7c1 <> 2
xy-chain[3]  {n6 n4}r8c5 - {n4 n3}r9c4 - {n3 n6}r9c2 ==> r8c3 <> 6
naked-single ==> r8c3 = 2
xy-chain[3]  {n3 n6}r2c3 - {n6 n2}r3c2 - {n2 n3}r5c2 ==> r5c3 <> 3
naked-singles ==> r5c3 = 6, r2c3 = 3
xy-chain[3]  {n4 n6}r8c1 - {n6 n3}r9c2 - {n3 n4}r9c4 ==> r8c5 <> 4
naked-singles ==> r8c5 = 6, r8c1 = 4
nrc-chain[3]  {n3 n6}r7c1 - {n6 n2}r2c1 - n2{r2c4 r7c4} ==> r7c4 <> 3
naked and hidden singles
GRID 9590 SOLVED. LEVEL = B-NRCZT6, MOST COMPLEX RULE = B-NRCZT6



Home(The Hidden Logic of Sudoku)         Home(Denis Berthier)