The New Sudoku Players' Forum

[AnotherLife]

Many recent examples in the ‘Puzzles’ section show that SE ratings often overvalue the complexity of puzzles, and this may cause a manual solver to search for complicated solutions or even refrain from solving a puzzle as it seems too hard. The fact is that SE ratings do not take account of many conventional methods, and I will pay most attention to AICs with groups and almost locked sets.

My approach is aimed primarily at people who solve puzzles by human means, and it is easy to understand. If a puzzle is unsolvable by some standard patterns (SP), we will need some kind of chains to solve it, and I suggest that we estimate the complexity of the puzzle according to the following chain classes (CC). I will say that a sudoku belongs to:

- Class SP if standard patterns

Hidden Text: Show

By standard patterns (SP), I mean the conventional methods implemented in HoDoKu:
Singles;
Locked candidates;
Naked pairs, triples and quads (and bigger locked sets);
X-Wing, Swordfish, Jellyfish and their finned/sashimi variations;
Skyscraper, 2-string kite, Turbot fish;
Empty rectangle;
Remote pair;
W-wing;
XY-wing;
XYZ-wing;
Simple Coloring, multi-coloring (they add up to simple chains);
UR, hidden rectangle, avoidable rectangle;
BUG+1.

are sufficient to solve it;
- Class C if we need basic AICs (without group- and ALS-nodes) besides SP in order to solve it;
- Class GC if we need AICs with groups besides the methods of the previous classes in order to solve it;
- Class ALSC if we need AICs with group- and ALS-nodes besides the methods of the previous classes;
- Class FC if we need forcing chains (I accept that they may contain group- and ALS-nodes) besides the methods of the previous classes;
- Class DFC if we need dynamic forcing chains besides the methods of the previous classes in order to solve the puzzle.

I have taken a sample of 10, 318 puzzles from Denis Berthier’s cbg-000 collection and split the puzzles with SER>=7.5 (568 puzzles) into the classes specified above. As I cannot check manually a much greater sample, my analysis may be a starting point for further research in automatic mode.

I have drawn two main conclusions.
1. None of the puzzles of the list needs a dynamic forcing chain to solve it (actually, the sample contains only the puzzles with SER<=9.0), and simpler methods suffice.
2. Forcing chains are rarely needed to solve the puzzles with SER<8.4, and in most cases AICs with group- and ALS-nodes suffice.

Now let us consider the statistical results concerning the puzzles with various SE ratings. It is easy to see that the share of the puzzles of Class FC gradually decreases to 0% as the SER decreases.
SER 9.0: GC - 4.8%, ALSC – 14.3%, FC – 80.9%;
SER 8.9: ALSC – 30.8%, FC – 69.2%;
SER 8.5-8.8: SP – 1.9%, GC – 7.6%, ALSC – 39.6%, FC – 50.9%;
SER 8.4: GC – 29.2%, ALSC – 45.5%, FC – 25.3%;
SER 8.3: SP – 0.4%, C – 3.2%, GC – 48.6%, ALSC – 40.5%, FC – 7.3%;
SER 8.2: C – 3.8%, GC – 96.2%;
SER 7.5-8.0: SP – 9.9%, C – 54.3%, GC - 29.6%, ALSC - 6.2%.

--------------------------------------------------
EDIT
I updated the SER 9.0 statistics thanks to Eleven and Totuan.

[AnotherLife]

As the caravan is to move on, I will continue to post new statistical results in this thread. This time I have taken a much bigger sample of 275, 867 puzzles from Denis Berthier’s collection and analyzed all the 466 puzzles with SER=9.0. It comes to be that dynamic forcing chains are rarely needed to solve such puzzles if we allow group- and ALS-nodes in forcing chains. I have split the puzzles with SER 9.0 into the classes specified in my previous post and got the following statistics.

SER 9.0 – 466 puzzles
GC – 0.2%, ALSC – 12.9%, FC – 80.9%, DFC – 6%

[AnotherLife]

Now I doubt if my results are useful to the forum since I have got no feedback in two weeks, but I will finish my work as a responsible man. This time I have analyzed all the 590 puzzles with SER=8.9 from the previous sample of 275, 867 puzzles and split them into the chain classes. I am planning to post the last part of my statistical results concerning the puzzles with SER=8.6, 8.7, 8.8, and stop at that point because the number of easier puzzles is much greater. I hope someone will develop software that will be able to analyze big samples of puzzles in automatic mode.

Returning to the puzzles with SER 8.9, I have drawn two main consequences.
1. Only an insignificant part of such puzzles needs dynamic forcing chains to solve them (actually, there are only two of them - 1...5..89.....9....8.2....4.7...45......2..4..457...1.362........4.97.2....5....1 and 1.3..67..........6...2...4.......8.3..18.4.6.59.3.....7...913....6.4...79.5..8... ).
2. About a third of such puzzles are solvable by AICs with groups and almost locked sets in addition to standard patterns.

SER 8.9 – 590 puzzles
C – 0.2%, GC – 1.5%, ALSC – 33.9%, FC – 64.1%, DFC – 0.3%

[yzfwsf]

1...5..89.....9....8.2....4.7...45......2..4..457...1.362........4.97.2....5....1 and 1.3..67..........6...2...4.......8.3..18.4.6.59.3.....7...913....6.4...79.5..8... ).

The first one does not actually need dynamic forcing chain.
Cell or region forcing chain with als and grouped node sometimes much more complicted than dynamic forcing chain.
Now it seems that dynamic may refer more to the programming implementation. I have also asked some of my manual puzzle solving master friends, they seem to be more willing to find dynamic forced chains instead of super-many branched forced chains.Of course, on average, the dynamic chain is relatively more complicated.

[AnotherLife]

Hi YZF,

The first one does not actually need dynamic forcing chain.

In this resolution state
:0000:x:1+2.+45..89+4+5...9....8.2...+54.7..+145...+3+1.2+5.4..457...1.362.+4...+5+5+14.97.2..+9.5.+2+4.1:733 641 941 854 859 861 867 877 884 895 798::
you can apply only the Broken Wing method besides dynamic forcing chains, but I have not included it in the list of standard patterns. So in my approach this puzzle belongs to Class DFC.

Cell or region forcing chain with als and grouped node sometimes much more complicted than dynamic forcing chain.
Now it seems that dynamic may refer more to the programming implementation. I have also asked some of my manual puzzle solving master friends, they seem to be more willing to find dynamic forced chains instead of super-many branched forced chains.

I would like to listen to their opinion and see concrete examples.

Of course, on average, the dynamic chain is relatively more complicated.

I agree with you. I think that very few people can apply dynamic forcing chains in manual solving.

[AnotherLife]

I have come to the point where anomalies arise. If a theory does not accord with the experimental results, it needs to be corrected.

Firstly, if we compare the puzzles with SER 8.9 and 8.8, the share of Class FC puzzles will fall from 64.1% to 30.2%. Moreover, the share of the puzzles having short solutions via AICs with groups and ALS’s will rise from 6.6% to 13.2%. So SER 8.8 puzzles are much easier than SER 8.9 puzzles. The statistical results are as follows.
SER 8.8 – 205 puzzles
GC – 12.2 %, ALSC – 57.6%, FC – 30.2%

As expected, the puzzles with SER 8.7 prove to be easier than the previous ones. I also noticed that in roughly half the cases their rating has been lowered in the latest release of Sukaku Explainer. For example, this puzzle 1234..7....71....369........7.....5..65..81.4....2.....42....7....5..6.2....7...1 is currently rated SER 7.2, which complies with the fact that it is solvable by standard patterns and basic AICs (Class C). It is pleasant to see that the creators of Sudoku Explainer understand the need for changes in some cases. The statistics is as follows.
SER 8.7 – 27 puzzles
C – 3.7%, GC – 22.2%, ALSC – 48.2%, FC – 25.9%

If we consider the puzzles with SER 8.6, we will face a very strange fact. These puzzles need forcing chains in 64.1% of the cases, which exactly corresponds to the SER 8.9 statistics. Moreover, the share of the puzzles having short solutions via AICs with groups and ALS’s is even lower, and there are only two puzzles (..34..7.9...78....7.9...5..2.8.91....6...4...9...6.3....5....61.1.......8...1.2.5 and ....5...9..71...3..89.......3....657.9.....2..64..2.98.1682...5.7....4......3..6.) with rather short solutions. So SER 8.6 puzzles are very tough for a human, if not practically unsolvable. See the statistics below.
SER 8.6 – 78 puzzles
GC – 7.7%, ALSC – 28.2%, FC – 64.1%

As the number of the puzzles with lower SER rises considerably (SER 8.5 – 918 puzzles, SER 8.4 – 3522 puzzles, SER 8.3 – 5791 puzzles), I cannot check them manually, and I hope that someone will continue my work. I estimate that the puzzles with SER 8.5 and 8.4 will need forcing chains correspondingly in roughly a half and a fourth of the cases. In the end, I post the full list of 275, 867 puzzles with CC corresponding to SER>=8.6.

[yzfwsf]

Using the batch puzzle solving module of my solver, the following analysis results are obtained for reference.

Code: Select all

   SER8.0~8.8: 10873 puzzles in total
No need chains: 300   puzzles  2.76%
   AIC needed: 1536  puzzles  14.4%
    GC needed: 3667  puzzles  33.73%
   ALS needed: 2495  puzzles  22.95%
   ALSC needed: 1216  puzzles  11.18%
   RCFC needed: 1659  puzzles  15.26%

[AnotherLife]

It looks like 'the average temperature in the hospital'. For example, the puzzles with SER 8.0 are considerably easier than the puzzles with SER 8.6. Could you post your results for the puzzles with a fixed SER?

[yzfwsf]

Code: Select all

SER     8.0    8.1    8.2     8.3    8.4    8.5
RCFC    8      0      4       351    855    441
ALSC    1      0      3       384    645    183
ALS     7      0      1       1378   940    169
GC      12     1      350     2412   799    93
AIC     12     0      185     1069   245    25
NO C    1      0      57      197    38     7
TOTAL   41     1      600     5791   3522   918


[AnotherLife]

Oh yeah, thanks YZF! I have some questions for you.
1. What methods do you consider as standard patterns when you write "NO C" (I guess you mean all the methods colored yellow, green, and white in YZF_Solver)?
2. What is the difference between "ALS" and "ALSC" (I guess, by "ALS" you mean the puzzles that need ALS XZ-Rule, XY-Wing and W-Wing)?
3. What do you mean by RCFC?

[yzfwsf]

Oh yeah, thanks YZF! I have some questions for you.
1. What methods do you consider as standard patterns when you write "NO C" (I guess you mean all the methods colored yellow, green, and white in YZF_Solver)?
2. What is the difference between "ALS" and "ALSC" (I guess, by "ALS" you mean the puzzles that need ALS XZ-Rule, XY-Wing and W-Wing)?
3. What do you mean by RCFC?

1. Yes but broken wing exclude
2. Yes
3. Cell/Region/UR Forcing Chain

[AnotherLife]

YZF, your analysis reveals another anomaly. The share of Class FC puzzles in SER 8.0 is 19.5% compared to 0.7% in SER 8.2, 6.1% in SER 8.3, 24.3% in SER 8.4, and 48% in SER 8.5. So the puzzles with SER 8.0 are close to the puzzles with SER 8.4 with respect to forcing chains.

Could you also check the puzzles with SER 7.6-7.9 ? They need Nishio Forcing Chains and in rare cases they are unsolvable by AICs with ALS's.

[yzfwsf]

Code: Select all

SER    7.6    7.7    7.8    7.9
DFC    0      0      0      1
RCFC   0      7      27     10
ALSC   0      5      21     9
ALS    1      7      37     15
GC     5      78     224    54
AIC    631    234    342    38
NOT C  849    319    439    49
TOTAL  855    416    748    138

If I enable the complex fish technique, the 7.9 puzzle using DFC will no longer require DFC.

[AnotherLife]

This is very interesting! Can I take a look at this SER 7.9 puzzle? Also, it would be great if you presented your results in an Excel file like I did before.

[yzfwsf]

Code: Select all

.2345.....5..891....8.....4......9..3641......7....4.1..59.8......3...95....4.8.2