- 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

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

RW

- 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

- RW
- 2010 Supporter
**Posts:**1000**Joined:**16 March 2006

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

- ravel
**Posts:**998**Joined:**21 February 2006

ravel wrote: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

gsf wrote: 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

- gsf
- 2014 Supporter
**Posts:**7306**Joined:**21 September 2005**Location:**NJ USA

RW wrote: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

- Viggo
**Posts:**60**Joined:**21 April 2006

There are two ways to count the number of solutions:Viggo wrote:Is there an easy way 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.

- Ocean
**Posts:**442**Joined:**29 August 2005

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.

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

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.

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 gridsRW wrote:I think you could get the number of fully entwined pairs down to zero, but that might require some heavier computing.

- 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

- coloin
**Posts:**1637**Joined:**05 May 2005

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.ravel wrote: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.

ravel wrote: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.......

#

- Ocean
**Posts:**442**Joined:**29 August 2005

Ocean wrote: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.

- ravel
**Posts:**998**Joined:**21 February 2006

Ravel wrote: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

- Carcul
**Posts:**724**Joined:**04 November 2005

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).

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).

- Ocean
**Posts:**442**Joined:**29 August 2005

Ocean wrote:ravel wrote: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

- gsf
- 2014 Supporter
**Posts:**7306**Joined:**21 September 2005**Location:**NJ USA

Ocean wrote: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.

- ravel
**Posts:**998**Joined:**21 February 2006