Challenge: New set of 11 'Unsolvables'

Advanced methods and approaches for solving Sudoku puzzles

Correlations

Postby denis_berthier » Fri Mar 28, 2008 8:47 am

This may not be the best thread for this, but as this is based on UN23-33, ...

Remember that the (linear) correlation coefficient between 2 statistical variables has a value between -1 and +1.
A correlation coefficient whose absolute value is greater than .8 is generally considered high.
A correlation coefficient whose absolute value is smaller than .5 is generally considered low (which means that there is no meaningful correlation between the two variables - the angle between the 2 variables is > 45°).
As an example, correlation coefficients between astrological signs and typical traits of personality usually associated with them have been evaluated as .4. Sorry for those who thought astrology was a science.

Here are a few results about correlation coefficients based on UN23-33 (currently the only list for which I have the necessary data).
As this list of puzzles is short, the following should be taken with some care. In particular, as all these puzzles are in my levels 4 to 8 (hard to hyper-diabolical for a human player), I don't kow if these results can be extended to lower levels (higher levels are likely to be beyond a normal human player's capacities).
Remember that the level of a puzzle in my classification is the length of the longest chain necessary to solve it (using my set of rules - i.e. basic rules + nrczt chains)


Results in my approach:
My-levels vs My-computation-times: .887
My-levels vs My-memory-requirements: .791
My-computation-times vs My-memory-requirements: .953

Notice that although there is such a statistical correlation between level and time or memory, time or memory can't be used to define the level of an individual puzzle: these results are valid only statistically.

Comparisons:
My-levels vs Champagne-levels (Champagne's level 1+ given value 1.75): 0.67
My-levels vs Champagne-levels (Champagne's level 1+ given value 1.5): 0.822
My-levels vs Champagne-levels (Champagne's level 1+ given value 1.25): 0.834
My-levels vs Champagne-levels (Champagne's level 1+ given value 1): 0.82

Champagne-levels vs Champagne-computation-times: 0.785 (Champagne's level 1+ given value 1.5)


It'd be interesting to compute the correlations with ER, but I have no means of computing ER. If anyone can do it for each of these puzzles, I'll do the complementary statistical computations.

It'd be interesting also to compute such correlations for a longer list of puzzles, but this may require a lot of work (computation times and memory requirements are not recorded in the current version of SudoRules).
If anyone is interested, please let me know, so that we can chose a reference collection of puzzles. I think 1000 random minimal puzzles would be enough (unless we concentrate on exceptionally hard ones).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby Mike Barker » Fri Mar 28, 2008 1:53 pm

Here are the 33 unsolvables with their Sudoku Explainer ratings. I've also shown the suexrat9 rating (based on 10001 trials) and the suexratt rating (based on 10000 2 trials). I also tried adding results from Glenn's solver, but this is the first time I've tried rating with it and the results are suspect. Its easy to do for a larger set. By the way I wouldn't consider the correlation between Champagne's times and his ratings as significant. Since one is simply a simple grouping of the other there is bound to be a decorrelation.
Code: Select all
######################################################################################################################
1..9.7..3.8.....7...9...6....72.94..41.....95..85.43....3...7...5.....4.2..8.6..9 # 1 SE=7.2  s9=104 st=77  gsf=1352
...3.2....5.798.3...7...8....86.73...7.....6...35.41....5...6...2.419.5....8.6... # 2 SE=7.1  s9=89  st=65  gsf=1042
...8....6..162.43.4...71..2..72...8.....1.....1...62..1..73...4.26.481..3....5... # 3 SE=6.6  s9=68  st=59  gsf=781
3.5..4.7..7......1.4.9...3.4...51..6.9.....4.2..84...7.2...7.6.8......9..6.4..2.8 # 4 SE=4.5  s9=80  st=59  gsf=293
...7..3...6....57..738..41...928....5.......9....936...98..715..54....6...1..9... # 5 SE=4.2  s9=67  st=59  gsf=277
...6....4.3..9..2..6.8..7....5.6...167.3.1.589...5.4....6..3.9..1..8..6.2....6... # 6 SE=6.6  s9=80  st=58  gsf=537
8....1.4.2.6.9..1...9..6.8.124.....9.........9.....824.5.4..1...8..7.2.5.9.5....7 # 7 SE=7.1  s9=93  st=77  gsf=1113
652.48..7.7.2.54............641...7.....8.....8...456............86.7.2.2..89.751 # 8 SE=6.7  s9=63  st=59  gsf=271
..6..2..91..5...2..473.6..1.....8.4..3.....7..1.6.....4..8.321..6...1..43..4..9.. # 9 SE=6.6  s9=90  st=75  gsf=292
..4.5.9......7...637......2..95...8...12.43...6...92..2......931...4......6.2.7.. #10 SE=7.1  s9=72  st=60  gsf=795
....3.79.3.......5...4.73.6.53.94.7.....7.....1.82.64.7.19.8...8.......1.94.1.... #11 SE=6.69 s9=79  st=63  gsf=545
..73..4......4..9..5.....6......76..5...3...1..39.8....2.....7..1..8......46.92.. #12 SE=7.5  s9=182 st=96  gsf=95820
...2.1.3.3...5...8....4...5.....8.7...4.3.1...9.5...2.9...8....6.......7.3.9.5... #13 SE=9.0  s9=283 st=145 gsf=95733
.4.....2.9.....1.3..23.79.....1.4...8.......4...7.5.9...85.26..1.9.....8.6.....7. #14 SE=8.4  s9=194 st=106 gsf=538
8.......6......15...69..2..3...1...4..9.6.7..2...7...3..3..14...45....8.6.......9 #15 SE=8.3  s9=137 st=65  gsf=544
.9.3.......7...6......24.3.91......8.........4....5.27.5.87..6...1...5.....5.6.9. #16 SE=8.3  s9=255 st=127 gsf=1457
....8...1..61.792..1..4..5......8..3......7..4..5......8..2..9..396.18......9.... #17 SE=8.5  s9=109 st=69  gsf=553
.6..32.4.8..5....1..9............29....7.3....14...5....8...3..7....6..9.2.48..5. #18 SE=8.5  s9=188 st=116 gsf=1301
2......6...93.4.....4.5.8..4.......6.9.1.7.2.7.......1..5...6.....2.35...1.....37 #19 SE=7.2  s9=181 st=103 gsf=1435
..1.5.7..3.......9.2.7..14....9.2..1..3...5..6..4......84..6.3.5.......7..6.9.8.. #20 SE=7.2  s9=148 st=93  gsf=613
...546..74.......9......3....63..5...3.....2...5..21....7......8...1...33..298... #21 SE=7.8  s9=264 st=153 gsf=1313
.6..8..2....372...7.....1.5..4...3...9...8.6...7...2..3.8.........4.5....5..2..9. #22 SE=7.1  s9=133 st=80  gsf=790
...8.21...6..4..5.1......72..59.67......8......13.48..25......1.1..3..9...34.1... #23 SE=9.0  s9=251 st=154 gsf=68003
6...8...5.4...128..8.....6...7..23.....5.8.....17......6.....4...43...2.3...9...6 #24 SE=9.0  s9=355 st=200 gsf=95002
4...1...56..2.7..4......1...4.9...6...2.5.8...9...4.....7......8..5.1..31...6...8 #25 SE=8.4  s9=149 st=85  gsf=1684
.26...9....5.6.4.....9.7...9..1....5.4....28.5....3..4...6.2.....9.5.7....1...85. #26 SE=8.9  s9=222 st=136 gsf=95184
.....1...4..9.8..5..2...6.8.3..5..71.8.....6..7..9..8.3.9...4..6..4.5..7...2..... #27 SE=8.5  s9=206 st=82  gsf=1309
..5...8...7.3...1.8..1.5..96......74...2.6...29......83....4..1.1...9.4...6...3.. #28 SE=8.4  s9=151 st=94  gsf=1302
.....8.6.19.....7...5.2.4..93.....4....2.7....6.....89..3.7.8...5.....26.1.3..... #29 SE=8.5  s9=171 st=105 gsf=1555
.5.....6...4.2.3..9...4...5.96...5.....4.8.....5...13.7...6.2.3..2.1.9...3.....7. #30 SE=8.4  s9=255 st=110 gsf=95000
....5.....4.2.8.9...7.6.4.2.8.....7.7.6...2.5.5.....4.3.8.2.1...7.9.1.......3.... #31 SE=8.3  s9=187 st=89  gsf=346
9...1...3...4.7.....1.5.6...23...49.5.......8..8...72...6.4.5.....1.8...4...9...1 #32 SE=8.4  s9=209 st=106 gsf=580
.1.....5.7.8........26.83..9..3.5..7.........8..4.2..6..97.12....3...4...8.....9. #33 SE=9.0  s9=329 st=174 gsf=19626
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby champagne » Fri Mar 28, 2008 6:18 pm

I just took adantage of the list given by Mike to make a comparison.

I would just stress that we have reached SE9.0 (maximum 11.5 if I am right) and we have a maximum processing time on my side of 2.5 seconds against about 85 for Golden Nugget in the same conditions.
I see an exponential growth of difficulty for hardest puzzles (as long as nobody comes with a new way to crack them).



# 1 SE=7.2 s9=104 st=77 gsf=1352 0s125
# 2 SE=7.1 s9=89 st=65 gsf=1042 0s47
# 3 SE=6.6 s9=68 st=59 gsf=781 0s31
# 4 SE=4.5 s9=80 st=59 gsf=293 0s15
# 5 SE=4.2 s9=67 st=59 gsf=277 0s16
# 6 SE=6.6 s9=80 st=58 gsf=537 0s31
# 7 SE=7.1 s9=93 st=77 gsf=1113 0s47
# 8 SE=6.7 s9=63 st=59 gsf=271 0s16
# 9 SE=6.6 s9=90 st=75 gsf=292 0s47
#10 SE=7.1 s9=72 st=60 gsf=795 0s15
#11 SE=6.69 s9=79 st=63 gsf=545 0s32
#12 SE=7.5 s9=182 st=96 gsf=95820 0s78
#13 SE=9.0 s9=283 st=145 gsf=95733 1s984
#14 SE=8.4 s9=194 st=106 gsf=538 0s828
#15 SE=8.3 s9=137 st=65 gsf=544 0s375
#16 SE=8.3 s9=255 st=127 gsf=1457 0s125
#17 SE=8.5 s9=109 st=69 gsf=553 0s375
#18 SE=8.5 s9=188 st=116 gsf=1301 0s313
#19 SE=7.2 s9=181 st=103 gsf=1435 0s62
#20 SE=7.2 s9=148 st=93 gsf=613 0s78
#21 SE=7.8 s9=264 st=153 gsf=1313 0s63
#22 SE=7.1 s9=133 st=80 gsf=790 0s47
#23 SE=9.0 s9=251 st=154 gsf=68003 1s828
#24 SE=9.0 s9=355 st=200 gsf=95002 1s125
#25 SE=8.4 s9=149 st=85 gsf=1684 0s234
#26 SE=8.9 s9=222 st=136 gsf=95184 0s438
#27 SE=8.5 s9=206 st=82 gsf=1309 0s218
#28 SE=8.4 s9=151 st=94 gsf=1302 0s375
#29 SE=8.5 s9=171 st=105 gsf=1555 0s532
#30 SE=8.4 s9=255 st=110 gsf=95000 0s875
#31 SE=8.3 s9=187 st=89 gsf=346 0s62
#32 SE=8.4 s9=209 st=106 gsf=580 0s328
#33 SE=9.0 s9=329 st=174 gsf=19626 2s563
champagne
2017 Supporter
 
Posts: 5720
Joined: 02 August 2007
Location: France Brittany

Postby denis_berthier » Fri Mar 28, 2008 6:26 pm

Mike, thanks for these results. Here are mine.

The following results have been obtained with the collection of Unsolvables#1-#33
(# 13 and 33 have been eliminated because I have an unexplained memory overflow problem with them - although physical memory remains available.).
The collection is taken from Mike's last post above. It is better than the previous one limited to 23-33, as the puzzles now range from my levels 2 to 8.
The SER, sr9, srt and gsf ratings are also taken from Mike.
"My-levels" are as defined in my book and on this forum. They are computed with SudoRules version 13.


Firstly, here are the correlation coefficients for my-levels and SudoRules behaviour:
My-levels vs SudoRules-computation-times: .83
My-levels vs SudoRules-memory-requirements: .79
SudoRules-computation-times vs SudoRules-memory-requirements: .96


Secondly, here are the correlation coefficients for all couples of ratings:

My-levels vs SER: .76
My-levels vs sr9: .76
My-levels vs srt: .79
My-levels vs gsf: .45

SER vs sr9: .71
SER vs srt: .63
SER vs gsf: .36

sr9 vs srt: .93
sr9 vs gsf: .60

srt vs gsf: .67



As the gsf rating seems to have no strong correlation with any of the others, I've tried to replace it with its log or its square root. This makes things only slightly better. As I'm not familiar with these ratings, I have no explanation.

SudoRules-levels vs LN(gsf): .57
SudoRules-levels vs LN(LN(gsf)): .58
SudoRules-levels vs sqrt(sqrt(gsf)): .49
SudoRules-levels vs sqrt(sqrt(gsf)): .52


SER vs LN(gsf): .46
SER vs LN(LN(gsf)): .48
SER vs LN(LN(LN(gsf))): .49
SER vs sqrt(gsf): .42
SER vs sqrt(sqrt(gsf)): .39


srt vs LN(gsf): .67
srt vs LN(LN(gsf)): .67
srt vs LN(LN(LN(gsf))): .68
srt vs sqrt(gsf): .62
srt vs sqrt(sqrt(gsf)): .64



As the sample used is small (31) and not random, this has to be used with care.

Mike, if you're interested in pursuing the comparisons with the other ratings, why not try with the first 100 or 1000 in Sudogen0?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby gsf » Sat Mar 29, 2008 12:09 pm

I'm reposting Mike's data with the last field changed to my solver's -q1 rating
it should be a better match for suex* ratings

recall that an ER rating is the sudoku explainer rating for the hardest move in a puzzle
so the difficulty of two puzzles with the same ER could vary quite a bit depending
on the ratings for all moves required to solve each puzzle

also, suex* and -q1 ratings are estimates of work done by a backtrack solver that propagates the basic sudoku constraints
suex* washes backtrack ordering effects by averaging over many (default 1000) pseudo random permutations of the input puzzle
-q1 washes the ordering effects by measuring the branching at each ply when chosing the most constrained moves at each ply
(i.e., bivalue/location moves first, then trivalue/location etc.) and by batching the placements/eliminations at the end of each ply

this means that suex* -q1 ratings may overrate puzzles cracked by methods deemed easy

Code: Select all
#!sudoku -c1' puzzle ordinal ER suex9 suext q1'
1..9.7..3.8.....7...9...6....72.94..41.....95..85.43....3...7...5.....4.2..8.6..9  1   7.2 104  77  466
...3.2....5.798.3...7...8....86.73...7.....6...35.41....5...6...2.419.5....8.6...  2   7.1  89  65  232
...8....6..162.43.4...71..2..72...8.....1.....1...62..1..73...4.26.481..3....5...  3   6.6  68  59  248
3.5..4.7..7......1.4.9...3.4...51..6.9.....4.2..84...7.2...7.6.8......9..6.4..2.8  4   4.5  80  59  432
...7..3...6....57..738..41...928....5.......9....936...98..715..54....6...1..9...  5   4.2  67  59  345
...6....4.3..9..2..6.8..7....5.6...167.3.1.589...5.4....6..3.9..1..8..6.2....6...  6   6.6  80  58  469
8....1.4.2.6.9..1...9..6.8.124.....9.........9.....824.5.4..1...8..7.2.5.9.5....7  7   7.1  93  77  416
652.48..7.7.2.54............641...7.....8.....8...456............86.7.2.2..89.751  8   6.7  63  59  278
..6..2..91..5...2..473.6..1.....8.4..3.....7..1.6.....4..8.321..6...1..43..4..9..  9   6.6  90  75  542
..4.5.9......7...637......2..95...8...12.43...6...92..2......931...4......6.2.7.. 10   7.1  72  60  315
....3.79.3.......5...4.73.6.53.94.7.....7.....1.82.64.7.19.8...8.......1.94.1.... 11  6.69  79  63  412
..73..4......4..9..5.....6......76..5...3...1..39.8....2.....7..1..8......46.92.. 12   7.5 182  96  764
...2.1.3.3...5...8....4...5.....8.7...4.3.1...9.5...2.9...8....6.......7.3.9.5... 13   9.0 283 145  285
.4.....2.9.....1.3..23.79.....1.4...8.......4...7.5.9...85.26..1.9.....8.6.....7. 14   8.4 194 106  907
8.......6......15...69..2..3...1...4..9.6.7..2...7...3..3..14...45....8.6.......9 15   8.3 137  65  488
.9.3.......7...6......24.3.91......8.........4....5.27.5.87..6...1...5.....5.6.9. 16   8.3 255 127  314
....8...1..61.792..1..4..5......8..3......7..4..5......8..2..9..396.18......9.... 17   8.5 109  69  646
.6..32.4.8..5....1..9............29....7.3....14...5....8...3..7....6..9.2.48..5. 18   8.5 188 116  381
2......6...93.4.....4.5.8..4.......6.9.1.7.2.7.......1..5...6.....2.35...1.....37 19   7.2 181 103  717
..1.5.7..3.......9.2.7..14....9.2..1..3...5..6..4......84..6.3.5.......7..6.9.8.. 20   7.2 148  93  505
...546..74.......9......3....63..5...3.....2...5..21....7......8...1...33..298... 21   7.8 264 153  548
.6..8..2....372...7.....1.5..4...3...9...8.6...7...2..3.8.........4.5....5..2..9. 22   7.1 133  80  446
...8.21...6..4..5.1......72..59.67......8......13.48..25......1.1..3..9...34.1... 23   9.0 251 154  577
6...8...5.4...128..8.....6...7..23.....5.8.....17......6.....4...43...2.3...9...6 24   9.0 355 200 1770
4...1...56..2.7..4......1...4.9...6...2.5.8...9...4.....7......8..5.1..31...6...8 25   8.4 149  85  432
.26...9....5.6.4.....9.7...9..1....5.4....28.5....3..4...6.2.....9.5.7....1...85. 26   8.9 222 136  397
.....1...4..9.8..5..2...6.8.3..5..71.8.....6..7..9..8.3.9...4..6..4.5..7...2..... 27   8.5 206  82  310
..5...8...7.3...1.8..1.5..96......74...2.6...29......83....4..1.1...9.4...6...3.. 28   8.4 151  94  478
.....8.6.19.....7...5.2.4..93.....4....2.7....6.....89..3.7.8...5.....26.1.3..... 29   8.5 171 105  397
.5.....6...4.2.3..9...4...5.96...5.....4.8.....5...13.7...6.2.3..2.1.9...3.....7. 30   8.4 255 110  659
....5.....4.2.8.9...7.6.4.2.8.....7.7.6...2.5.5.....4.3.8.2.1...7.9.1.......3.... 31   8.3 187  89  608
9...1...3...4.7.....1.5.6...23...49.5.......8..8...72...6.4.5.....1.8...4...9...1 32   8.4 209 106  747
.1.....5.7.8........26.83..9..3.5..7.........8..4.2..6..97.12....3...4...8.....9. 33   9.0 329 174 2295
#######################################################################################################
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby denis_berthier » Sat Mar 29, 2008 12:58 pm

Here are the complementary correlation results for gsf -q1

gsf-q1 vs My-levels: .46
gsf-q1 vs SER: .63
gsf-q1 vs sr9: .66
gsf-q1 vs srt: .70

The correlation with any of the other ratings remains inexistent or weak (sr9, srt).
It may be because any new rule introduces a possibility of making simple anything that looked complex without it. As the -q1 rating uses almost no rule, it seems natural that it is decorrelated from almost any rating based on lots of rules.

Same remarks as above: small sample => all this may not be very meaningful.
If you want to check all this on a large random sample, the 10.000 minimal puzzles in sudogen0 are here:
http://www.carva.org/denis.berthier/HLS/sudogen0.txt

gsf, for symmertry reasons, wouldn't it be more meaningful to have hidden singles playing the same pruning role as naked singles in such -q1 ratings?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby gsf » Sat Mar 29, 2008 4:18 pm

denis_berthier wrote:gsf, for symmertry reasons, wouldn't it be more meaningful to have hidden singles playing the same pruning role as naked singles in such -q1 ratings?

by default the q1 rating actually does propagate naked/hidden singles
the constraints propagated are specified on the command line
here are the ratings in order when FNBTHW (singles locked-candidates 2,3,4 tuples, 2,3,4 xwing/sword/jelly) are propagated
Code: Select all
1046 1047 1031 1055 1042 1053 1061 1039 1056 1043 1044 2094 1047 1063 1046 1048 1030 1038 1036 1052 1062 1047 2088 2094 1052 1045 1062 1041 1044 1049 1033 1054 3145

in this rating the thousands digit is the number of proposition rounds, more rounds => harder on average for a guesser

here are the options to do that
Code: Select all
-q'FNBTHW-G' -Z'FNBTHWP*' -B -M- -R'P0*1000+P2+(P8>1?10000:0)' -f'%r'
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby denis_berthier » Sun Mar 30, 2008 6:37 am

Here are the complementary results for the above gsf rating with all naked, hidden and super-hidden subsets (I'll call it the gsf-sub rating) - with always the same remarks on small sample size (31).

gsf-sub vs gsf-q1: .67
gsf-sub vs My-levels: .51
gsf-sub vs SER: .26
gsf-sub vs sr9: .35
gsf-sub vs srt: .47
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby champagne » Sun Mar 30, 2008 8:27 am

I checked Denis 10000 puzzles.

I got the following statistics

Average time 35 milliseconds per puzzle average printsize 3K
(Golden Nugget 85000 milliseconds and 400K printsize)

A split per "level" gives

Code: Select all
no tagging    6851   16  0;47    (number, av time, min time, max time all milliseconds)
level 0        828   30  15;78   (only bi values on digits including groups)
level 1       2140   61  15,234  (same as above plus bi values in cells)
level 1+       169  355  78;1641 (ternary kraken blossoms)
level 2         12 1977  406;4406(ALS ACs no loop on derived weak links)

No puzzle requested more than level 2 (out of 4 levels)
champagne
2017 Supporter
 
Posts: 5720
Joined: 02 August 2007
Location: France Brittany

Postby denis_berthier » Sun Mar 30, 2008 10:16 am

champagne
I've opened a new thread so that we do not overload this one, dedicated to Unsolvables.
Your 4 levels are too rough a classification to lead to useful detailed comparisons as I've done with the other ratings.
Two of your parameters could be useful:
- the computation time for each puzzle
- the memory requirements for each puzzle

(I can do nothing with mean values).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby champagne » Sun Mar 30, 2008 10:38 am

I can send the short text file including original file and times.

Memory is not a relevant data in my process.

How can you catch it simply it's to long to be posted (1420kB)
champagne
2017 Supporter
 
Posts: 5720
Joined: 02 August 2007
Location: France Brittany

Postby denis_berthier » Sun Mar 30, 2008 10:49 am

champagne wrote:Memory is not a relevant data in my process.

Do you mean that the same memory size is used for any puzzle?

champagne wrote:How can you catch it simply it's to long to be posted (1420kB)


The easiest way is to put it in a PM, as Mike did.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Postby champagne » Sun Mar 30, 2008 12:21 pm

Denis wrote

Code: Select all
Do you mean that the same memory size is used for any puzzle?


For sure not, but as long as you stay below tagging level (60%) of the total, yes.

I would say that later on, each level has somehow a memory requirement although I did not optimize the program to the point where I would acquire memory dynamically.

Memory requirements in a dynamic view of memory acquisition would be more or less depending on

The number of strong links and the number of layers at level one (about 50 layers and may be 200 strong links)

Same plus the number of ALS ACs and the number of choices in level 2.
Here we jump to some hundreds of layers and mor or less 300 AC2 + ALS

Level 3 is dependant of the number of loops needed to find clearing AICs.
Each time you loop, you have to keep in memory
. the origin of derived weak links,
. the binary map of weak links (1MB fo a 1000 tags map)

Memory requirements are not at all influenced by the length of clearing chains.

I send you the file in PM
champagne
2017 Supporter
 
Posts: 5720
Joined: 02 August 2007
Location: France Brittany

Solution for 16

Postby BrianS » Sun May 17, 2009 10:47 am

Nobody has posted a solution for "unsolvable" number 16. I have a solution that uses a Sue-De-Coq and an empty rectangle as its most advanced strategies.

1. E9 is the only candidate for 6 in column 9.
2. G3 is the only candidate for 9 in column 3.
3. Hidden pair in box 9, H8 and J7 reduced to 7/8.
4. Hidden triple in row 8, H1 and H2 reduced to 6/7/8.
5. Pointing pair, 7s at E1 and E2 point to E4 and E6.
6. Pointing triple, 3s at D7, E7 and F7 point to G7.
7. Pointing pair, 5s at D8 and E8 point to A8 and B8.
8. Pointing pair, 9s at E7 and F7 point to C7.
9. Pointing pair, 4s at J2 and J3 point to J5 and J9.
10. Pointing pair, 4s at H4 and H5 point to H9.
11. Sue-De-Coq, Group A=[A1,B1,C1], Group B=[C2,C3], Stem=G1. A3 reduced to 2/4, B2 reduced to 2/3/4, E1 reduced to 5/7/8, J1 reduced to 7/8.
12. Naked pair, J1 and J7 are 7 and 8, striking them from J2 and J3.
13. Empty rectangle, CJ17, 8 removed from C7.
14. Line/box reduction, 8s in row C and box 1, 8 removed from A1 and B1.
15. Finned X-Wing on 2, AG17, Fin=B1, 2 removed from A3.
16. A3=4.
17. J2 is the only candidate for 4 in row J.
18. Almost Locked Sets, [C2,C3] and [A6,B4,B5,B6,C4] removes 5 from B1.
19. Almost Locked Sets, [D5,D7] and [B4,E4,F4,H4] removes 4 from D4.
20. Alternating Inference Chain, 3(G9)-3(G1)=3(J3)-2(J3)=2(J9)-2(H9)=3(H9). 3 removed from G9.
21. Alternating Inference Chain, 1(A5)-6(A5)=6(A1)-6(H1)=6(H2)-7(H2)=7(E2)-2(E2)=2(B2)-3(B2)=3(B1)-3(G1)=3(G6)-3(J5)=1(J5). 1 removed from A5.
22. Alternating Inference Chain, 7(A7)-2(A7)=2(G7)-2(G1)=2(J3)-3(J3)=3(J1)-3(B1)=3(B2)-2(B2)=2(E2)-7(E2)=7(E1)-7(J1)=7(J7). 7 removed from A7.
23. Alternating Inference Chain, 8(A6)-7(A6)=7(A8)-7(H8)=7(J7)-8(J7)=8(A7). 8 removed from A6.
24. Alternating Inference Chain, 1(G6)-1(A6)=7(A6)-7(A8)=7(H8)-7(H2)=7(E2)-2(E2)=2(B2)-3(B2)=3(B1)-3(G1)=3(G6). 1 removed from G6.
25. J5 is the only candidate for 1 in box 8.
26. Naked pair, H9 and J9 are 2 and 3, removing 2 from A9, B9, G7 and G9.
27. A7 is the only candidate for 2 in column 7.
28. J7 is the only candidate for 8 in column 7.
29. H8=7.
30. J1=7.
31. A6 is the only candidate for 7 in row A.
32. C7 is the only candidate for 7 in column 7.
33. E2 is the only candidate for 7 in row E.
34. B2 is the only candidate for 2 in column 2.
35. D4 is the only candidate for 7 in row D.
36. F2 is the only candidate for 3 in column 2.
37. B1 is the only candidate for 3 in row B.
38. G1 is the only candidate for 2 in column 1.
39. G6 is the only candidate for 3 in row G.
40. J3 is the only candidate for 3 in column 3.
41. J9 is the only candidate for 2 in row J.
42. D6=2.
43. H9=3.
44. H6=9.
45. H5=4.
46. H4=2.
47. E3 is the only candidate for 2 in row E.
48. E4 is the only candidate for 4 in column 4.
49. Naked triple, E1, E6 and E8 are 1, 5 and 8, removing 8 from E5 and 1 from E7.
50. Pointing pair, 6s at D3 and F3 point to C3.
51. Simple coloring on 1. Group A: [B6,E8,F4,G7] Group B: [E6,F7,G9]. 1 removed from B9.
52. XY Chain on 8, B6,E6,E1,E8,A8. 8 removed from A5 and B8.
53. A8 is the only candidate for 8 in row A.
54. X-Wing on 1, BE68. 1 removed from B4.
55. B4=9.
56. C9 is the only candidate for 9 in row C.
57. Box/line reduction, 5 in box 1 and row C. 5 removed from A1.
58. Y-Wing on 8, E6,F3,F4. 8 removed from E1 and F5.
59. E1=5.
60. D3=6.
61. E8=1.
62. B8=4.
63. D5=3.
64. E6=8.
65. F3=8.
66. F7=9.
67. B6=1.
68. B9=5.
69. C3=5.
70. D7=4.
71. D8=5.
72. E5=9.
73. E7=3.
74. F5=6.
75. A5=5.
76. A9=1.
77. B5=8.
78. C4=6.
79. F4=1.
80. G7=1.
81. A1=6.
82. C2=8.
83. G9=4.
84. C1=1.
85. H1=8.
86. H2=6.
BrianS
 
Posts: 1
Joined: 17 May 2009

Previous

Return to Advanced solving techniques

cron