The Hidden Logic of SudokuDenis BerthierOnline SupplementsRating 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 republished or reposted without his prior written permission. 
1) INTRODUCTION  MOTIVATIONSSeveral 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): NRCZTrating SERrating SUEX9rating SUEXTrating GSFQ1rating 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) PSEUDOCODE 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 NRCZTrating 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 xfile and yfile, 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 (?xfile ?yfile ?n) (open ?xfile "xfile" "r") (open ?yfile "yfile" "r") i = 1 EX = 0 EY = 0 EX2 = 0 EY2 = 0 EXY = 0 while i < (n + 1) do ;; get the ith element in xfile: xi = eval (readline "xfile") ;; get the ith element in yfile: yi = eval (readline "yfile") ;; 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 "xfile") (close "yfile") ;; 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 "yfile") within the "while" loop, by yi = f (eval (readline "yfile")) 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 RATINGS2.1) THE NRCZTRATING Of course, I'll be concerned with the NRCZTrating, among others, so let me remind its definition. It is mainly based on nrcztwhips. 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 nrcztwhips[1]  see subsumption page) L2: Naked, Hidden and SuperHidden Pairs + nrcztwhip[2] L3: Naked, Hidden and SuperHidden Triplets + nrcztwhip[3] L4: Naked, Hidden and SuperHidden Quads + nrcztwhip[4] L5: nrcztwhip[5] For n > 4: Ln: nrcztwhip[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(Ln1). 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"FNBTHWG" 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 XWing 3.4 Hidden Pair 3.6 Naked Triplet 3.8 Swordfish 4.0 Hidden Triplet 4.2 XYWing 4.3 [Direct Hidden Quad] 4.4 XYZWing 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 XCycle or Bidirectional YCycle (14 nodes) 6.6 Turbot Fish Forcing Xchain or Bidirectional YCycle (56 nodes) 6.69 Forcing XChain (78 nodes) 6.7 Bidirectional Ycycle (78 nodes) 6.8 Forcing XChain or Bidirectional Ycycle (912 nodes) 6.9 Forcing XChain or Bidirectional Ycycle (1316 nodes) 7.0 Bidirectional Ycycle (1724 nodes) Forcing Chain or Bidirectional Cycle (14 nodes) 7.1 Forcing Chain or Bidirectional Cycle (56 nodes) 7.2 Forcing Chain or Bidirectional Cycle (78 nodes) 7.3 Forcing Chain or Bidirectional Cycle (912 nodes) 7.4 Forcing Chain (1316 nodes) 7.5 Forcing Chain (1724 nodes) Aligned Triplet Exclusion 7.6 Forcing Chain (2536 nodes) Nishio Forcing Chain (56 nodes) 7.7 Nishio Forcing Chain (78 nodes) 7.8 Nishio Forcing Chain (912 nodes) 7.9 Nishio Forcing Chain (1316 nodes) 8.0 Nishio Forcing Chain (1724 nodes) 8.1 Nishio Forcing Chain (2536 nodes) 8.2 Multiple (78 nodes) Region Forcing Chains 8.3 Multiple (912 nodes) Cell/Region Forcing Chains 8.4 Multiple (1316 nodes) Cell/Region Forcing Chains 8.5 Multiple (1724 nodes) Cell/Region Forcing Chains 8.6 Multiple (2536 nodes) Dynamic (56 nodes) Cell/Region Forcing Chains 8.7 Dynamic (78 nodes) Cell/Region Forcing Chains 8.8 Dynamic (912 nodes) CRCD Forcing Chains 8.9 Dynamic (1316 nodes) CRCD Forcing Chains 9.0 Dynamic (1724 nodes) CRCD Forcing Chains 9.1 Dynamic (2536 nodes) CRCD Forcing Chains 9.2 Dynamic (3748 nodes) CRCD Forcing Chains 9.3 Dynamic (4972 nodes) Dynamic + (912 nodes) CRCD Forcing Chains 9.4 Dynamic (7396 nodes) Dynamic + (1316 nodes) CRCD Forcing Chains 9.5 Dynamic + (1724 nodes) CRCD Forcing Chains 9.6 Dynamic + (2536 nodes) CRCD Forcing Chains 9.7 Dynamic + (3748 nodes) CRCD Forcing Chains 9.8 Dynamic + (4972 nodes) CRCD Forcing Chains 9.9 Dynamic + (7396 nodes) CRCD Forcing Chains 10.0 Dynamic + (97144 nodes) Dynamic + Forcing Chains (1724 nodes) CRCD Forcing Chains 10.1 Dynamic + (145192 nodes) Dynamic + Forcing Chains (2536 nodes) CRCD Forcing Chains 10.2 Dynamic + Forcing Chains (3748 nodes) CRCD Forcing Chains 10.3 Dynamic + Forcing Chains (4972 nodes) CRCD Forcing Chains 10.4 Dynamic + Forcing Chains (7396 nodes) CRCD Forcing Chains 10.5 Dynamic + Forcing Chains (97144 nodes) CRCD Forcing Chains 10.6 Dynamic + Forcing Chains (145192 nodes) CRCD Forcing Chains 10.7 Dynamic + Forcing Chains (193288 nodes) CRCD Forcing Chains 10.8 Dynamic + Forcing Chains (289384 nodes) CRCD Forcing Chains 10.9 Dynamic + Multiple Forcing Chains (7396 nodes) CRCD Forcing Chains 11.0 Dynamic + Multiple Forcing Chains (97144 nodes) CRCD Forcing Chains 11.1 Dynamic + Multiple Forcing Chains (145192 nodes) CRCD Forcing Chains 11.2 Dynamic + Multiple Forcing Chains (193288 nodes) CRCD Forcing Chains 11.3 Dynamic + Multiple Forcing Chains (289384 nodes) CRCD Forcing Chains 11.4 Dynamic + Multiple Forcing Chains (385576 nodes) CRCD Forcing Chains 11.4 [Dynamic + Dynamic Forcing Chains (7396 nodes) Region/Contradiction Forcing Chains] 11.5 [Dynamic + Dynamic Forcing Chains (97144 nodes) Region Forcing Chains] 11.6 [Dynamic + Dynamic Forcing Chains (145192 nodes) Cell Forcing Chains] 11.7 [Dynamic + Dynamic Forcing Chains (193288 nodes) Double Forcing Chains] CRCD=Cell/Region/Contradiction/Double UL=Unique Loop UR=Unique Rectangle BUG=Bivalue Universal Grave 
3) FIRST RESULTS3.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 GSFQ1 ratings used for the comparisons. Correlation coefficients: NRCZT vs SER: 0.89 NRCZT vs SUEX9: 0.73 NRCZT vs SUEXT: 0.77 NRCZT vs GSFQ1: 0.70 SER vs SUEX9: 0.70 SER vs SUEXT: 0.68 SER vs GSFQ1: 0.69 SUEX9 vs SUEXT: 0.88 SUEX9 vs GSFQ1: 0.75 SUEXT vs GSFQ1: 0.64 Although the GSFQ1 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: NRCZTrating: 0.678 SERrating: 0.721 SUEX9rating: 0.682 SUEXTrating: 0.716 GSFQ1rating: 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 nrcztratings and the number of chains (or the indicated function of it): nrcztrating vs number of chains: 0.54, no meaningful correlation nrcztrating vs log(number of chains): 0.96, very strong correlation nrcztrating vs sqr2(number of chains): 0.85 nrcztrating vs sqr4(number of chains): 0.93 nrcztrating vs sqr6(number of chains): 0.95 nrcztrating vs sqr8(number of chains): 0.95 here, sqrn(x) is x^(1/n) These results are valid for nrcztlevels 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 NRCZTrating 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 nrcztwhip 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 NRCZTrating, 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 NRCZTrating is reasonably well correlated with the other usual ratings (SER, SUEX9, SUEXT and GSFQ1), 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 NRCZTrating 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: L1412, L34014, L447155, L2492, L6141739, L21276, L21243, L442482, L1494, L24064, L1507, L1477, L1492, L411313,... There is an obvious second possibility: introducing sublevels for specialised cases of nrcztwhips (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 NRCZTratings and the SERratings 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 sublinearly 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 SERtimes 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? Q1times vs Q1 : 0.38 Q1times vs log(Q1) : 0.23 As Q1times may be 0, one can't compute Q1 vs log(Q1times), but Q1 vs sqr16(Q1times) : 0.50 There doesn't seem to be any correlation between Q1 and Q1times. But this may be due to the imprecision in Q1times (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 NRCZTrating. 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 nrcztchain. 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 RESULTSIn 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 NRCZTratings, the SER ratings, the number of clues, the number of partial nrcztchains. 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). nbclues nbpuzzles 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 17clue 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 NRCZTlevel : 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 nrcztwhips 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 microcomputer. 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 NRCZTlevel) 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 essentialequivalence, 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,000puzzle 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 nonnumerical variables (the puzzles) can be tested indirectly through the (normalised) autocorrelation 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) autocorrelation function? Its kth 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 autocorrelation. 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

6) pNRCZT, THE PURE NRCZT RATINGAt 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 superhidden 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 nrcztchains, but I didn't know yet that family 3 is completely subsumed by nrcztchain[´] (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 nrcztwhips 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, rowcolumn symmetry),  is based on a single homogeneous family of fully supersymmetric 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 nrcztchain 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 superhidden) 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 BNRCZT and the pBNRCZT RATINGSAs a result of the introduction of nrcztbraids, one can introduce a new rating, the pBNRCZT rating ("pure BNRCZT rating). It is defined in a way similar to the previous pNRCZT rating, but with nrcztbraids replacing nrcztwhips. Rules allowed at the different levels of the pBNRCZT rating: pBNRCZT0: ECP (no unsolved puzzle can be solved at this level) pBNRCZT1_0 : NS + HS pBNRCZT1: rules for nrczt braids of length 1 (equivalent to elementary interactions) .... pBNRCZTn : rules for nrcztbraids of length n It can be shown that it has all the good properties of one can expect from a rating. The pBNRCZT 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 nrcztbraids, we can say precisely for which puzzles the BNRCZT 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 BNRCZT rating can also be defined as above, by allowing the same subset rules at levels 2 to 4. The BNRCZT 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 BNRCZT AND THE pBNRCZT 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 BNRCZT rating is a priori always smaller than the NRCZT rating. But, it also appears that, for almost all the random puzzles, the BNRCZT rating is equal to the NRCZTrating. 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) BNRCZT rating. Eighteen of these cases have BNRCZT = NRCZT  1 and one case has BNRCZT = NRCZT  2. As a result, all the correlation and classification results that were given for the NRCZTrating can be straightforwardly transferred to the BNRCZTrating 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 BNRCZT rating. Similarly, the pBNRCZT is a priori always smaller than pNRCZT. In practice, pBNRCZT 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 BNRCZT 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 pNRCZT rating are available here. The detailed classification results of the full sudogen0 random collection of 10,000 minimal puzzles for the pBNRCZT rating are available here. 6.2) EXAMPLES Here is an example of a puzzle (sudogen0 #4177) with NRCZTrating = 8 but BNRCZTrating = 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 hiddensingleinarow ==> r8c7 = 4 interaction column c3 with block b4 for number 4 ==> r4c1 <> 4 nrcztwhip[2] c5n3{r6 r8}  c8n3{r8 .} ==> r4c4 <> 3 nrcchain[5] c4n9{r3 r2}  r2c8{n9 n8}  r1c9{n8 n4}  c1n4{r1 r2}  b1n3{r2c1 r3c3} ==> r3c4 <> 3 nrcztwhip[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: nrcztwhip[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 nrctchain[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: nrctchain[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 nrctchain[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 hiddensingleincolumn c7 ==> r5c7 = 9 nrctchain[6] b1n3{r3c3 r2c1}  r2n4{c1 c9}  c9n1{r2 r9}  c9n9{r9 r8}  b7n9{r8c3 r9c3}  c3n2{r9 r4} ==> r4c3 <> 3 nrcztwhip[6] r2n4{c1 c9}  r1c9{n4 n8}  r2c8{n8 n9}  r3n9{c8 c4}  r3n8{c4 c6}  r5n8{c6 .} ==> r2c1 <> 8 nrcztwhip[6] b1n3{r3c3 r2c1}  r2n4{c1 c9}  c9n1{r2 r9}  c9n9{r9 r8}  r8c3{n9 n8}  r7c3{n8 .} ==> r3c3 <> 6 nrcztwhip[6] r2c1{n4 n3}  r3c3{n3 n8}  r7c3{n8 n6}  r8c3{n6 n9}  c9n9{r8 r9}  c9n1{r9 .} ==> r2c9 <> 4 hiddensingles ==> r1c9 = 4, r2c1 = 4, r3c3 = 3 nrcztwhip[4] r5c6{n8 n6}  r3c6{n6 n1}  c7n1{r3 r9}  r9n5{c7 .} ==> r9c6 <> 8 nrcztwhip[4] r5c6{n6 n8}  r3c6{n8 n1}  c7n1{r3 r9}  r9n5{c7 .} ==> r9c6 <> 6 nrcztwhip[5] r5c6{n6 n8}  r3c6{n8 n1}  c7n1{r3 r9}  r9n5{c7 c6}  c6n4{r9 .} ==> r6c6 <> 6 nrcztwhip[5] b4n3{r5c1 r4c1}  c8n3{r4 r8}  c5n3{r8 r6}  r6n7{c5 c9}  r6n6{c9 .} ==> r5c1 <> 6 nrcztwhip[5] r5c6{n8 n6}  r3c6{n6 n1}  c7n1{r3 r9}  r9n5{c7 c6}  c6n4{r9 .} ==> r6c6 <> 8 nrctchain[5] b4n2{r4c1 r4c3}  c3n4{r4 r6}  r6c6{n4 n3}  c5n3{r4 r8}  c8n3{r8 r4} ==> r4c1 <> 3 hiddensingleinblock b4 ==> r5c1 = 3 nrcchain[3] r5n8{c6 c9}  r4c7{n8 n7}  r6n7{c9 c5} ==> r6c5 <> 8 nrcztwhip[5] c3n4{r4 r6}  r6c6{n4 n3}  c5n3{r6 r8}  c5n8{r8 r9}  b7n8{r9c3 .} ==> r4c3 <> 8 nrcztwhip[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 nrcchain[4] r6c6{n3 n4}  c4n4{r4 r9}  b8n7{r9c4 r7c4}  c4n3{r7 r2} ==> r2c6 <> 3 singles ==> r2c4 = 3, r3c4 = 9 nakedtripletsinacolumn c6{r2 r3 r5}{n8 n1 n6} ==> r7c6 <> 8, r7c6 <> 6 nrcchain[2] c2n6{r6 r3}  c6n6{r3 r5} ==> r6c5 <> 6 nrcchain[3] c9n1{r9 r2}  r2c6{n1 n8}  r5n8{c6 c9} ==> r9c9 <> 8 nrcztwhip[3] b7n6{r9c3 r9c1}  c8n6{r9 r8}  c5n6{r8 .} ==> r4c3 <> 6 nrcchain[4] r4c7{n7 n8}  r5n8{c9 c6}  r2c6{n8 n1}  r3n1{c6 c7} ==> r3c7 <> 7 hiddensingleinblock b3 ==> r3c8 = 7 nakedquadsinarow r9{c1 c3 c8 c5}{n6 n2 n9 n8} ==> r9c9 <> 9, r9c9 <> 6, r9c4 <> 8, r9c4 <> 6 nrcchain[4] r4n7{c7 c5}  r6c5{n7 n3}  c6n3{r6 r7}  r7n5{c6 c7} ==> r7c7 <> 7 xyztchain[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 nrcchain[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 nrcchain[4] r4c1{n8 n2}  b7n2{r9c1 r9c3}  r9n9{c3 c8}  r2c8{n9 n8} ==> r4c8 <> 8 nrcchain[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' : nrcztbraid[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 nrcztbraidcn[6] n6{r3c4 r3c6}  {n6 n8}r3c2  {n6 n8}r7c3  {n6 n8}r5c6  n8{r1c1 r4c1}  {n8r3c7 .} ==> r7c4 <> 6 nrcztwhipcn[5] n4{r4c3 r4c4}  n4{r9c4 r9c6}  n5{r9c6 r7c6}  n6{r7c6 r7c9}  {n6r9c8 .} ==> r4c3 <> 6 ;;; braids of length 7 appear here: nrcztbraidrn[7] n3{r5c1 r2c1}  n4{r2c1 r2c9}  n1{r2c9 r9c9}  n2{r4c3 r9c3}  n9{r9c3 r8c3}  n9{r2c9 r5c9}  {n3r5c9 .} ==> r4c3 <> 3 nrcztbraidcn[7] n4{r6c6 r6c3}  n3{r6c3 r3c3}  {n8 n6}r5c6  {n8 n1}r3c6  n1{r3c7 r9c7}  n5{r9c7 r9c6}  {n4r9c6 .} ==> r6c6 <> 8, r6c6 <> 6 nrctchain[5] n2{r4c1 r4c3}  n4{r4c3 r6c3}  {n4 n3}r6c6  n3{r6c5 r8c5}  n3{r8c8 r4c8} ==> r4c1 <> 3 nrcztwhipcn[6] n7{r6c9 r6c5}  n7{r9c5 r9c4}  n4{r9c4 r4c4}  {n4 n3}r6c6  n3{r7c6 r7c4}  {n3r8c5 .} ==> r7c9 <> 7 nrcchain[4] {n9 n8}r5c7  {n8 n7}r4c7  n7{r6c9 r9c9}  n1{r9c9 r9c7} ==> r9c7 <> 9 nrcchain[4] n5{r7c7 r9c7}  n1{r9c7 r9c9}  n7{r9c9 r6c9}  {n7 n8}r4c7 ==> r7c7 <> 8 nrcztwhipcn[2] n8{r6c2 r3c2}  {n8r3c7 .} ==> r6c9 <> 8 nrcztwhiprc[3] n8{r6c3 r6c5}  n7{r6c5 r6c9}  {n7r4c7 .} ==> r4c1 <> 8 nrcztwhiprc[3] n8{r6c3 r6c5}  n7{r6c5 r6c9}  {n7r4c7 .} ==> r4c3 <> 8 nrcchain[4] n6{r1c4 r1c1}  {n6 n2}r4c1  {n2 n4}r4c3  n4{r4c4 r9c4} ==> r9c4 <> 6 nrcchain[4] n9{r3c4 r2c4}  n3{r2c4 r7c4}  n7{r7c4 r7c7}  n7{r3c7 r3c8} ==> r3c8 <> 9 nrcchain[5] n1{r2c6 r3c6}  n1{r3c7 r9c7}  n5{r9c7 r7c7}  n7{r7c7 r7c4}  n3{r7c4 r2c4} ==> r2c6 <> 3 nrcchain[3] n9{r3c4 r2c4}  n3{r2c4 r3c6}  n1{r3c6 r3c7} ==> r3c7 <> 9 hiddensingles ==> r5c7 = 9, r3c4 = 9 nrcztwhipcn[3] n8{r3c7 r4c7}  n8{r5c9 r5c1}  {n8r6c2 .} ==> r3c6 <> 8 nrcztwhipbn[3] {n8 n6}r3c2  n6{r3c6 r1c4}  {n8r1c4 .} ==> r2c1 <> 8 nrcztwhiprn[4] n1{r9c9 r2c9}  {n1 n8}r2c6  n8{r5c6 r5c1}  {n8r1c1 .} ==> r9c9 <> 8 nrctchain[5] n8{r4c7 r3c7}  n1{r3c7 r2c9}  {n1 n8}r2c6  n8{r1c4 r1c1}  n8{r5c1 r5c9} ==> r4c8 <> 8 nrctchain[5] n4{r9c4 r4c4}  n4{r6c6 r9c6}  n5{r9c6 r7c6}  {n5 n7}r7c7  n7{r7c4 r9c4} ==> r9c4 <> 8 nrcztwhiprc[5] {n8 n7}r4c7  n7{r6c9 r9c9}  {n7 n4}r9c4  {n4 n6}r4c4  {n6r5c6 .} ==> r4c5 <> 8 nrcztwhiprc[4] n8{r8c5 r6c5}  n8{r6c3 r5c1}  n3{r5c1 r2c1}  {n3r2c4 .} ==> r7c4 <> 8 nrcchain[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 nakedpairsinarow {n6 n8}r7{c3 c9} ==> r7c6 <> 8, r7c6 <> 6 hiddenpairsinacolumn {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 = BNRCZT7, MOST COMPLEX RULE = BNRCZT7 691827354 427351689 583946172 214679835 375218946 968534217 146793528 759182463 832465791 Here is now an example of a puzzle (sudogen0 #9586) with NRCZTrating = 8 but BNRCZTrating = 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: hiddensingles ==> 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 hiddenpairsinarow 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 hiddenpairsinarow r2{n7 n8}{c8 c9} ==> r2c8 <> 2 nrcztwhip[2] b7n4{r8c1 r9c2}  c7n4{r9 .} ==> r5c1 <> 4 nrcchain[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 nrctchain[3] r8c9{n6 n1}  b7n1{r8c1 r9c3}  r9n5{c3 c8} ==> r9c8 <> 6 nrcztwhip[3] b1n2{r2c3 r3c2}  r3n6{c2 c7}  c7n5{r3 .} ==> r2c7 <> 2 nrcchain[4] c4n1{r4 r3}  r3c5{n1 n2}  c2n2{r3 r5}  r4n2{c3 c8} ==> r4c8 <> 1 nrctchain[4] c7n4{r5 r9}  r9c4{n4 n3}  r9c2{n3 n6}  r3n6{c2 c7} ==> r5c7 <> 6 nrctchain[4] r8c9{n6 n1}  r9n1{c8 c3}  b7n5{r9c3 r7c3}  c9n5{r7 r5} ==> r5c9 <> 6 nrcztwhip[4] c2n3{r6 r9}  r9c4{n3 n4}  r2n4{c4 c6}  r4c6{n4 .} ==> r4c3 <> 3 nrcztwhip[4] b7n1{r9c3 r8c1}  r8c9{n1 n6}  r4n6{c9 c8}  r4n2{c8 .} ==> r4c3 <> 1 nrctchain[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 nrcztwhip[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): nrcztwhiprn[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 nrcztwhipcn[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 hiddensingleinarow ==> r9c5 = 7 nrcchain[4] c5n6{r7 r8}  r8c9{n6 n1}  b7n1{r8c3 r9c3}  b7n5{r9c3 r7c3} ==> r7c3 <> 6 nrcztwhip[5] r8c9{n6 n1}  r4c9{n1 n3}  r4c6{n3 n4}  c5n4{r4 r8}  b8n6{r8c5 .} ==> r7c9 <> 6 nrcztwhip[6] b8n6{r7c5 r8c5}  b9n6{r8c9 r9c7}  r3n6{c7 c2}  r2n6{c3 c6}  c6n4{r2 r4}  c5n4{r5 .} ==> r7c1 <> 6 nrcztwhip[6] r8c9{n1 n6}  r4c9{n6 n3}  c6n3{r4 r1}  c6n6{r1 r2}  c1n6{r2 r5}  c1n1{r5 .} ==> r6c9 <> 1 nrcztwhip[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 nrctchain[3] r9c2{n6 n3}  r9c4{n3 n4}  r8n4{c5 c1} ==> r8c1 <> 6 xyztchain[4] r8c1{n2 n4}  r7c1{n4 n3}  r9c2{n3 n6}  r3c2{n6 n2} ==> r2c1 <> 2 nrcchain[4] r2n2{c4 c3}  r3c2{n2 n6}  r9c2{n6 n3}  c4n3{r9 r7} ==> r7c4 <> 2 nakedpairsinablock 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 nakedpairsinacolumn c9{r4 r8}{n1 n6} ==> r5c9 <> 1 nakedpairsinablock b8{r7c4 r9c4}{n3 n4} ==> r8c4 <> 4 hiddensingleinrow r8 ==> r8c1 = 4 nrcchain[4] r3c5{n2 n1}  c4n1{r3 r4}  c9n1{r4 r8}  r8n6{c9 c5} ==> r8c5 <> 2 xwinginrows 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 xwinginrows n2{r2 r8}{c3 c4} ==> r3c4 <> 2 nrcchain[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): nrcztbraidrc[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 leftlinking candidate of the fourth cell (n1r1c7) is not nrclinked to the rightlinking candidate of the third cell (n4r5c7), as should be the case for a whip, but is nrclinked to the rightlinking candidate of the second cell (n1r9c7) ;;;  the leftlinking candidate of the fifth cell (n7r2c8) is not nrclinked to the rightlinking candidate of the fourth cell (n1r1c8), as should be the case for a whip, but is nrclinked to the target (n7r9c8) hiddensingleinarow ==> r9c5 = 7 nrcchain[4] n6{r7c5 r8c5}  {n6 n1}r8c9  n1{r8c3 r9c3}  n5{r9c3 r7c3} ==> r7c3 <> 6 nrcztwhipcn[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 nrctchain[6] n2{r5c2 r3c2}  n2{r2c1 r2c4}  {n2 n1}r3c5  {n1 n3}r1c5  {n3 n8}r5c5  n8{r5c3 r4c3} ==> r4c3 <> 2 hiddensingleinarow ==> r4c8 = 2 nrcchain[3] {n1 n6}r8c9  n6{r4c9 r5c8}  n5{r5c8 r5c9} ==> r5c9 <> 1, r9c8 <> 1 nrcchain[3] n1{r9c3 r9c7}  {n1 n6}r8c9  n6{r4c9 r4c3} ==> r9c3 <> 6 xwinginrows n6{r3 r9}{c2 c7} ==> r5c2 <> 6, r2c7 <> 6 naked and hidden singles ==> r2c7 = 5, r3c4 = 5, r4c4 = 1, r8c4 = 8 xwinginrows n6{r3 r9}{c2 c7} ==> r1c7 <> 6 nrcchain[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 xychain[3] {n2 n3}r5c2  {n3 n6}r9c2  {n6 n2}r8c3 ==> r5c3 <> 2 nrcchain[2] n2{r7c4 r2c4}  n2{r2c3 r8c3} ==> r8c5 <> 2 interaction row r8 with block b7 for number 2 ==> r7c1 <> 2 xychain[3] {n6 n4}r8c5  {n4 n3}r9c4  {n3 n6}r9c2 ==> r8c3 <> 6 nakedsingle ==> r8c3 = 2 xychain[3] {n3 n6}r2c3  {n6 n2}r3c2  {n2 n3}r5c2 ==> r5c3 <> 3 nakedsingles ==> r5c3 = 6, r2c3 = 3 xychain[3] {n4 n6}r8c1  {n6 n3}r9c2  {n3 n4}r9c4 ==> r8c5 <> 4 nakedsingles ==> r8c5 = 6, r8c1 = 4 nrcchain[3] {n3 n6}r7c1  {n6 n2}r2c1  n2{r2c4 r7c4} ==> r7c4 <> 3 naked and hidden singles GRID 9590 SOLVED. LEVEL = BNRCZT6, MOST COMPLEX RULE = BNRCZT6 