The New Sudoku Players' Forum

[RW]

And a tough puzzle I made by removing clues from the SFB-grid:

Code: Select all

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

RW

[ravel]

There are 14 ways for 3 steps, mostly going over r3c2<>6 or r1c1<>3:

Code: Select all

r1c2<>5, r1c9<>8, r3c2<>6
r1c8<>2, r1c2<>4, r1c1<>3
r1c9<>8, r3c2<>6, r1c1<>3
r2c3<>8, r3c2<>6, r2c4<>3
r3c6<>2, r1c2<>4, r1c1<>3
r3c6<>8, r1c8<>2, r2c4<>3
r3c8<>4, r3c7<>2, r1c1<>3
r4c7<>5, r1c9<>8, r3c2<>6
r5c7<>8, r3c2<>6, r1c1<>3
r6c9<>7, r3c2<>6, r1c1<>3
r7c7<>7, r3c2<>6, r1c1<>3
r9c2<>6, r1c9<>8, r3c2<>6
r9c8<>5, r1c9<>8, r3c2<>6
r9c9<>1, r3c2<>6, r1c1<>3


[gsf]

There are 14 ways for 3 steps, mostly going over r3c2<>6 or r1c1<>3:

step is flying around pretty loose in the player's forum
the inferior etc. threads state specifically what a step means for each thread
here it seems that step means

proposed candidate eliminations that lead to a solution that doesn't require more proposed candidate eliminations

what about any one of these proposed candidate eliminations?

Code: Select all

[27]^8
[33]^8


[Viggo]

The solution to the "toughest known":

Code: Select all

 
 *-----------*
 |798|635|421|
 |126|974|583|
 |453|218|679|
 |---+---+---|
 |972|586|314|
 |564|123|897|
 |381|497|256|
 |---+---+---|
 |617|352|948|
 |835|749|162|
 |249|861|735|
 *-----------* 

Out of the 36 numberpairs 20 are fully entwined (1-5, 1-6, 1-7, 1-8, 1-9, 2-3, 2-4, 2-5, 2-7, 3-4, 3-6, 3-7, 3-9, 4-6, 4-8, 5-7, 5-9, 6-8, 6-9, 8-9), two form three deadly patterns (1-2, 3-8) and one forms four deadly patterns (7-9). The rest form two.

There's also 7 triplets that are fully entwined (1-5-7, 1-6-9, 2-3-4, 2-3-7, 2-5-7, 3-6-9, 4-6-8). Removing all digits of any of these triplets would cause only 6 solutions. To compare, if you chose to remove all digits of the triplet 4-7-9, that would cause 360 solutions.

How did you find out that the triplet, 4-7-9 have 360 solutions? I have tried this combination in my solver, and it seems like 3*2*2*3*2*2=144 solutions. The solver needed 6 guesses for this combination.

I think there is 84 number-triplets. Did RW or somebody else look into the number of solutions of all triplets in the grids we have discussed? Is there an easy way to count the number of solutions?

/Viggo

[Ocean]

Is there an easy way to count the number of solutions?

There are two ways to count the number of solutions:
1. Plug the subgrid into a solver program that counts solutions.
2. Count the number of legal permutations of the excluded set.

For method 1 - if you do not have a batch solver available, you may use 'Simple Sudoku'. Start with the complete solution grid. For the 4-7-9 triplet case, set all 4s, 7s, 9s to 0, and plug the resulting subgrid into the solver. Answer (for the grid above): 360 solutions. This method works fine as long as the number of solutions is less than some upper limit (10000?). It's a good method for checking one or two specific sets, but requires too much manual work to check lots of combinations. If you have a batch solver, you can construct a pipeline that replaces certain digits with 0, followed by counting solutions for each set of digits.

Method 2 is for the combinatorics guys. Some small or simple sets are quite straightforward, while larger sets might be more of a challenge.

[coloin]

Interesting stuff - we thought very hard about constructing grids and working out why only some grids could be represented in 17 clues. I realize you are trying to find a grid with the hardest puzzle.

RW - Im glad the SFB came up good. Of course it may not be the grid with the hardest clues - but it is an "extreme" grid - it had only three 17- clue puzzles though.

We never really got an answer to the minimum clues problem.

I think you could get the number of fully entwined pairs down to zero, but that might require some heavier computing.

this thread may be relevant. And from it are two grids [provided by a dukuso search] - which would appear to have many [Maximal number of 4 sets - therefore minimal entwining ?] This may save you a lot of work. Two high MCN grids

Code: Select all

dukuso15 - 123568479864791352957243681218657934536489127749312865391825746472136598685974213
dukuso16 - 145726983837495261926381574293874156581269347674153892318547629459632718762918435


Moschopulus developed an interesting concept of the MCN (maximal clique number), The SF and SFB grids had lowish MCNs.

Example of a set of disjoint unavoidables of the grid on the home page of the forum

C:\suxxprog>unavoid pappa.txt
963174258
178325649
254689731
821437596
496852317
735961824
589713462
317246985
642598173

Found 209 unavoidable sets (36 of size 4 or 6).

The maximum # of disjoint unavoidable sets (max clique number -- MCN) is 12.
One such maximal collection is:
{14,15,74,75}
{16,18,26,28}
{35,36,95,96}
{53,55,63,65}
{56,58,66,68}
{11,12,51,52,91,92}
{17,19,67,69,77,79}
{21,22,61,62,81,82}
{24,25,44,45,84,85}
{27,29,47,49,87,89}
{31,32,41,42,71,72}
{37,38,39,97,98,99}


See Checker and unavoid

Here is a link to a solver suexk program from dukuso

Having said all this my analysis of grid clue counts has apparently drawn a blank - the ran1 grid [randomly picked /manufactured from the ether] has a completly average count of 30-clue minimal puzzles - yet it has four minimal 35s

[ravel]

step is flying around pretty loose in the player's forum

See here, what i mean with step in this context.

[Ocean]

Ocean, thanks for the interesting analysis. It also shows, how hard it is to define and evaluate super hard puzzles.
From the last list with 24 puzzles, numbers 2 (4 steps) and 19 (5 steps) are for my list.

The "last list" was highest rankings from the fully symmetric collection, for comparing - not from the sf-grid. Thanks for your evaluation. There is obviously some correspondence between the two rating methods, but they are far from equal. Agree that it is hard to grasp the magic of the superhards.

Can you use gsf's solver to extract the hardest 20 out of your 20000 ?

Ok, here are finally the 20 highest-rated of the 20s I have in the sf-grid (gsf-rating).

Code: Select all

#
95189, 5.....4.....71.2....74....6......6...7...3....1..5...96....2..8....3..1.4........
95155, 5..3..4.....71............6..8..4....7.2...8..1......96....2.......3..1.4..9..5..
95025, ....8.4.1...71...3..............462..7.2......1......96....2.....5.3..1.48.......
95013, 5....94.....716.................46..97.2......1.8.....6....2.38.......1.4.......2
95013, 5.....4.....716.......2..9......46...7.2...8..1.......6.....7......3..1.483......
95002, ..2.8.47.....1..5..3...5........46...7.2......1......96............38.1.4.......2
95002, ..2..947.....1..5..3...5........46...7.2......1......96............38.1.4.......2
95002, ..2...47.....1..5..3...5........46...7.2......1.8....96............38.1.4.......2
95002, .......7..4.71..........896..8..46...7...3..5.1.......6..5.........3..1.4.......2
94943, 5....94...4..1...3....2...6.....46...7.......21.......6............38.1.4..9..5..
94844, 5.2...4...4..1...3.............946...7.2...8..1.......6..5.2.......38.1.4........
93302, ..2...47.....1..5..3...5.......946...7.2......1......96............38.1.4.......2
93301, ..2...47.....1..5..3...5........46..97.2......1......96............38.1.4.......2
93228, ..2...4.....71...31......9......46.7.7.2......1..5.3..6....2.......3..1.4........
92858, 5.2...4.....71...3........6....94....7.......216...........2...7..63..1.4.....5..
91093, 5.2...4......162.3..............46..97.....8..1.......6....2.......3..1..8..7..6.
90518, 5.....4.....71...3....2.......1.46...7.2......1......96......3.....389..4.......2
90197, 5.....47....71...3....2.........46...7.2...8..1......96.1..........3..1.48.......
90197, 5.....47....71...3....2.........46...7.2...8..1......96.1..........3....48...1...
90197, 5.....4.....71...3..7.2.........46...7.2...8..1......96.1..........3..1.48.......
#

[ravel]

The "last list" was highest rankings from the fully symmetric collection, for comparing - not from the sf-grid.

Ah, i will correct my text.

There is obviously some correspondence between the two rating methods, but they are far from equal. Agree that it is hard to grasp the magic of the superhards.

As far as i understood gsf's rating, it reflects typical program's ratings better than humans' for hard puzzles.
Humans e.g. also will try to eliminate one of strong linked candidates, no matter how many other candidates the cells have. They will try to use all the "almost" patterns, they can see and thus try to eliminate candidates seperately, that prevent a deduction or pattern for the elimination of another one.
Also many (known) backdoors are not useful at all, because it is too hard to reach them.

My program does not guess at all, but tries many combinations (orders) of possible (brute force) eliminations, what is rather time consuming. The main disadvantages i see is that no advanced techniques are implemented (only x-wing and UR type1) and the (minimal) "length" of the steps is not considered at all.

Ok, here are finally the 20 highest-rated of the 20s I have in the sf-grid (gsf-rating).

Thanks, but none needed 4 steps.

[Carcul]

Thanks, but none needed 4 steps.

You are right on that, at least regarding the first puzzle (rating 95189):

Code: Select all

 *-------------------------------------------------------------*
 | 5     2689   289    | 3     2689  689   | 4     7      1    |
 | 389   34689  3489   | 7     1     5689  | 2     3589   35   |
 | 1     2389   7      | 4     289   589   | 3589  3589   6    |
 |---------------------+-------------------+-------------------|
 | 2389  34589  34589  | 1289  4789  14789 | 6     23458  3457 |
 | 289   7      45689  | 2689  4689  3     | 1     2458   45   |
 | 238   1      3468   | 268   5     4678  | 378   2348   9    |
 |---------------------+-------------------+-------------------|
 | 6     359    1359   | 159   479   2     | 3579  3459   8    |
 | 7     2589   2589   | 5689  3     4689  | 59    1      245  |
 | 4     23589  123589 | 1589  789   1789  | 3579  6      2357 |
 *-------------------------------------------------------------*


1. [r6c6]=7=[r6c7]-7-[r7c7]=7=[r7c5]=4=[r8c6]-4-[r6c6], => r6c6<>4.

2. [r6c3]=6=[r5c3]-6-[r5c5]=6=[r1c5]-6-[r1c2]=6=[r2c2]=4=[r4c2]-4-
-[r6c3], => r6c3<>4.

3. [r8c7](-5-[r9c7]-9-[r9c2])-5-[r8c3]=5=[r4c3]-{TILA(9): r8c3|r8c6|
|r1c6|r1c5|r4c5|r4c2|r7c2}, => r8c7<>5 which solves the puzzle.

Carcul

[ravel]

Nice! So 2 rather short NL's (eliminating candidates from 4-candidate cells) crack this terrifying grid. Interestingly the 3rd step was the longest, though then 5 numbers already are resolved.

[Carcul]

The third step could be replaced by colors (an easy-to-spot nice loop), but, as that would be so simple, I decided to try to use the more "exotic" logic of TILA.

Carcul

[Ocean]

Thanks ravel for explanations, and to Carcul for the elimination chains.

Still struggling to understand what a 'brute force elimination' is (and what it is not), and how to find such (and find useful ones). Guess the simplistic "my brute force solver tells me this candidate does not fit" is not sufficent (would reduce almost every puzzle to 2-3 steps or less).

[gsf]

Can you use gsf's solver to extract the hardest 20 out of your 20000 ?

Ok, here are finally the 20 highest-rated of the 20s I have in the sf-grid (gsf-rating).

some of these solved with no guessing so I was surprised by the high rating for those
a -v2 trace for those shows many xy cycles
the -O option can be used to pick the shortest xy cycles at each step that advance the solution
so -O should produce ratings that make more sense

[ravel]

Still struggling to understand what a 'brute force elimination' is (and what it is not), and how to find such (and find useful ones). Guess the simplistic "my brute force solver tells me this candidate does not fit" is not sufficent (would reduce almost every puzzle to 2-3 steps or less).

Yes, thats exactly, why i did not find more than 135 ultras so far.
Looking at the toughest known puzzle: When getting stuck with my basic methods, there are 211 candidates in the grid. Only for 18 of them with these methods can be shown that they would cause a contradiction and the elimination of none of the 18 helps much. That is, what it makes so hard.
To find useful ones, i start with each candidate that can be eliminated, drop it and repeat the game. Out of the candidates that can be eliminated then, i take the (first) one, that reduces the number of candidates most.