The New Sudoku Players' Forum

[ronk]

Out of the candidates that can be eliminated then, i take the (first) one, that reduces the number of candidates most.

Do the candidates counted include exclusions of subsequent logical techniques until another "brute-force elimination" is required ... or the puzzle is solved? For the last BFE, if more than one BFE could bring the puzzle to solution, which one do you pick?

[ravel]

Do the candidates counted include exclusions of subsequent logical techniques until another "brute-force elimination" is required

Yes.

... or the puzzle is solved? For the last BFE, if more than one BFE could bring the puzzle to solution, which one do you pick?

From each starting candidate (those that can be eliminated when it gets stuck the first time) i keep a list of eliminations, until it is solved (or it gives up after a maximum number). At the end i take the minimum number of needed eliminations as the number of BF steps.
For one step (and the last also) I always take the first elimination that leads to a minimum number of remaining candidates, starting with 1,2,3,.. in r1c1 and ending with 9 in r9c9. That means, that scrambling the puzzle can lead to different results, when more than 1 elimination ends with the minimum number. This was the case for the 2 hardest puzzles (the more steps are needed, the more probable it is that a scrambled puzzle can give better results).

[ronk]

For one step (and the last also) I always take the first elimination that leads to a minimum number of remaining candidates ...

So, for the last BFE, you take the first elimination found that solves the puzzle?

[Mike Barker]

Ocean, of your 20 puzzles, my solver can solve all but 2 - #2 and #14. #14 really threw my solver for a loop before it gave up. Most of the others can be solved with simple nice loops, a few require larger (2 cells or more) ALS techniques, and one requires a grouped nice loop.

[Viggo]

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

When you look at the 10 hardest puzzles on Ravels list, none have a number of clues of 20. They all have between 23 and 25 clues. So if you limit yourselves to only 20 clues, this could be the reason why these puzzles are not so hard according to Ravels solver.

/Viggo

[Havard]

Ocean, of your 20 puzzles, my solver can solve all but 2 - #2 and #14. #14 really threw my solver for a loop before it gave up. Most of the others can be solved with simple nice loops, a few require larger (2 cells or more) ALS techniques, and one requires a grouped nice loop.

Yup, I got the same result!

Havard

[ravel]

So, for the last BFE, you take the first elimination found that solves the puzzle?

Yes, in my hardest list i do not show the shortest steps, but i did for some posted puzzles. In these step lists the last step is the first elimination (in the above order) that solved it finally.

[Carcul]

Ocean, of your 20 puzzles, my solver can solve all but 2 - #2 and #14.

Yes, although still easy, puzzle #14 looked harder than puzzle #1:

Code: Select all

 *--------------------------------------------------------------------*
 | 5789   5689   2      | 3      689    5689   | 4      5678   1      |
 | 589    4      589    | 7      1      5689   | 258    2568   3      |
 | 1      3568   3578   | 4      2      568    | 578    9      568    |
 |----------------------+----------------------+----------------------|
 | 3      2589   589    | 1      89     4      | 6      258    7      |
 | 589    7      46     | 2      689    3      | 1      458    589    |
 | 289    1      46     | 689    5      7      | 3      248    289    |
 |----------------------+----------------------+----------------------|
 | 6      3589   1      | 589    4      2      | 5789   3578   58     |
 | 25789  2589   5789   | 5689   3      689    | 2589   1      4      |
 | 4      23589  3589   | 589    7      1      | 2589   23568  2568   |
 *--------------------------------------------------------------------*


1. [r6c9]=2=[r9c9]=6=[r9c8]=3=[r7c8]=7=[r1c8]-7-[r1c1]=7=[r8c1]=
=2=[r6c1]-2-[r6c9], => r9c9<>5,8; r9c8<>2,5,8; r7c8<>5,8;
r8c1<>5,8,9; r6c8<>2.

2. [r2c8]=2=[r2c7]-2-[r89c7]=2=[r9c9]=6=[r3c9]-6-[r2c8], => r2c8<>6.

3. -2-[r8c2]={Nice Loop: [r8c1]=2=[r8c7]-2-[r9c9]=2=[r6c9]-2-[r6c1]=
=2=[r8c1]}=2=[r8c1](=7=[r8c3])=7=[r1c1]-7-[r1c8]-6-[r1c2|r3c9]-
-{Nice Loop: [r7c9]-5-[r8c7]=5=[r8c2]-5-[r1c2]=5=[r1c6]-5-[r3c6]=5=
=[r3c9]-5-[r7c9]}-5-[r7c9](-8-[r7c4])-8-[r3c9]-5-[r3c6]-8-[r8c6]=
=8=[r9c4]-8-[r9c23]=8=[r78c2]-8-[r1c2]-5-[r1c6]=5=[r3c6],
=> r8c2=2.

4. [r4c3](-5-[r4c2])-5-[r8c3]=5=[r8c7]-5-[r3c7]=5=[r3c6]-5-[r1c6]=5=
[r1c1]-5-[r2c1]-{TILA(8,9): r2c1|r2c3|r8c3|r8c6|r1c6|r1c5|r4c5|r4c2|
|r5c1}, => r4c3<>5.

5. -8-[r2c1]-{TILA(8): r1c1|r5c1|r4c3|r4c5|r1c5}, => r2c1=8 and that
solves the puzzle.

Carcul

[RW]

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.

My original purpose was to find out if the entwining has any effect at all on any attributes of the puzzles constructed from the grid. But it seems that hard puzzles are hot right now, so people are mostly looking for them.

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

The MCN is rather high, but the entwining is nothing near minimal. Comparing to the puzzle I posted earlier:

Code: Select all

My puzzle - 123469785456187932789253164371694528698512347542378691215946873864735219937821456

           2-perm.  4-perm.  8-perm.  16-perm.         
dukuso15 - 18                18
dukuso16 - 21       6        1        8
my puzzle- 9        17       10

Both of dukusos puzzles have at least twice as many fully entwined pairs as mine. The total number of 2-digit unavoidable sets in my puzzle is 73, dukuso15 has 72 and dukuso16 has 68, so no records broken here...

[edit: MCN for my puzzle: 13]

RW

[coloin]

Back on the thread now !

Thanks for looking at the dukuso grids - of course they were chosen to have a high numbers of 4 set unavoidables - and it is not possible to have 4 of these with two clue numbers - like this invalid

Code: Select all

+---+---+---+
|12.|...|...|
|...|12.|...|
|...|...|.12|
+---+---+---+
|21.|...|...|
|...|21.|...|
|...|...|.21|
+---+---+---+
|...|..?|...|
|..1|...|2..|
|..2|...|1..|
+---+---+---+

But this is a "16 perm" as I understand

Code: Select all

+---+---+---+
|12.|...|...|
|...|12.|...|
|...|...|.12|
+---+---+---+
|21.|...|...|
|...|.12|...|
|...|...|.21|
+---+---+---+
|...|2.1...|
|..1|...|2..|
|..2|...|1..|
+---+---+---+ 3 four clue and 1 six clue unavoidable set

These grid structures are what defines each different grid termed "templates " [Edit - Pappacom defined these as [9-clue] Rookeries]] it has been calculated the number of ways to lay these down.

By the former definition, I worked out a while back that there are
T(0) = 1 way of laying down no digits at all
T(1) = 46656 ways of laying down all the 1s
T(2) = 838501632 ways of laying down all the 1s,2s
T(3) = 5196557037312 ways of laying down all the 1s,2s,3s
T(4) = 9631742544322560 ways of laying down all the 1s,2s,3s,4s


T(8) = 6670903752021072936960 ways of laying down all the 1s-8s
T(9) = 6670903752021072936960 ways of laying down all the 1s-9s

...so a lot of grid options then !

This thread introduced the 3- rookery concept from Wolfgang - a step too far for me......but significant in that it predicted grids which had low clue solutions.

High MCN grids have a high number of 4 set unavoidables - and this reduces the total number of unavoidable sets in the whole grid - so high MCN grids tend to need more clues - but then dont have so many unavoidable sets to cover......so there are conflicting processes here.

I will have a scan for maximal clues in your grid

C

[Viggo]

I have read some of the stuf in the minimum sudoku thread. It's a very long thread of complicated topis (for me). I should be gratefull for a link to a few articles explaining some of the many concepts of this thread.

I have some difficulty in the terminology and the number of unavoidable sets. According to this link you have 240000 unavoidable sets in the SF grid. At the same time it is stated, that it is sufficient to use about 50-300 of them - which ones?. A small subset of the unavoidable sets are the "templates", "the entwined pairs", "2-rookeries" or "[9-clue] Rookeries". There are at least 36 of them, and I think all these names have been used for the same subject. I suppose, that when you have got a grid with:

21 2-permutable
6 4-permutable
1 8-permutable
and 8 16-permutable

then you have actually have got 21*1 + 6*2 + 1*3 + 8*4 = 68 unavoidable sets like this - am I right?

Generally most unavoidable sets involve more than two cell values. The 2-rookeries involve two cell values.

I have tried to make some statistics on the grid from the top 3 puzzles on Ravels list and 3 random grids provided by coloin. I have added results from the SF grid and SFB grid:

Code: Select all

Grid name:                             top1  top2  top3  ran1  ran2  ran3    SF   SFB
Number of 2-permutable:                  20    19    26    18    23    25    28    36
Number of 4-permutable:                  13    13     9    16     9     8     8     0
Number of 8-permutable:                   2     4     1     2     3     3     0     0
Number of 16-permutable:                  1     0     0     0     1     0     0     0
Sum of solutions all 2-rookeries:       124   122    96   116   122   106    88    72
Sum of solutions all 3-rookeries:      3414  3384  2322  3252  3222  2574  1818  1194
Max numb. solutions of 3-rookeries:     360   258   252   264   264   120   102    54
Number of minimal 3-rookeries:            7     5    10     2     5    11    15    39       
MCN:                                     12    10    10    10    12    10     9     8


The solver, Simple sudoku, was used to count the number of solutions of each subgrid involved.

I have not been able to identify any difference between 3 random grids and the 3 grids used by the hardest puzzles on Ravels list. I have also looked at the prime factors for each of the 3-rookery number of solutions, but still I could not see any significant difference. I have used an excel spreadsheet to make the puzzles etc. and I can provide them if you have are interested.

The SF grid and SFB grids are very different from the other "random" grids. Looking at these numbers alone, the SFB grid is the most special, and perhaps you would expect this puzzle to have the most 17 puzzles, but it IS the SF grid. So what is the difference in stucture between these two grids, that make this difference?

/Viggo

[Moschopulus]

I just read this thread. Some interesting discussion and ideas although I haven't digested everything.

I have some difficulty in the terminology and the number of unavoidable sets. According to this link you have 240000 unavoidable sets in the SF grid. At the same time it is stated, that it is sufficient to use about 50-300 of them - which ones?.

The smallest ones. But the question is, what are they sufficient for.....
That site is using them to search for puzzles with a given number of clues. To do this you really only need the smallest 50-300 unavoidable sets. This is what we mean.

A small subset of the unavoidable sets are the "templates", "the entwined pairs", "2-rookeries" or "[9-clue] Rookeries". There are at least 36 of them, and I think all these names have been used for the same subject.

A template is a set of 9 cells with one in each row and column and box. So if you look at the 9 cells in a completed grid where 1 is (or any digit) then this is a template. (Someone correct me if I'm wrong)

An entwined pair is an unavoidable set with two digits, I think. This could have 18 cells, or less.

A 2-rookery consists of all 18 cells containing two digits. This is an unavoidable set, but perhaps not a minimal unavoidable set. If it is minimal, we are calling the digits a fully entwined pair.

A template is a 1-rookery.

A 3-rookery consists of all 27 cells containing any given three digits.

I suppose, that when you have got a grid with:

21 2-permutable
6 4-permutable
1 8-permutable
and 8 16-permutable

then you have actually have got 21*1 + 6*2 + 1*3 + 8*4 = 68 unavoidable sets like this - am I right?

Yes.
You would have 68 unavoidable sets with only two digits in them.
You could say that 21 of the 36 2-rookeries are minimal unavoidable sets, and the other 15 are not minimal.

The SF grid and SFB grids are very different from the other "random" grids. Looking at these numbers alone, the SFB grid is the most special, and perhaps you would expect this puzzle to have the most 17 puzzles, but it IS the SF grid. So what is the difference in stucture between these two grids, that make this difference?

Good question. That is what we were trying to understand a while back, but we never did.

[RW]

Thanks Viggo for the detailed analysis of the puzzles.

I have not been able to identify any difference between 3 random grids and the 3 grids used by the hardest puzzles on Ravels list. I have also looked at the prime factors for each of the 3-rookery number of solutions, but still I could not see any significant difference.

I'm not suprised, right now I don't think that the entwining makes it more likely for hard puzzles to appear. When I first counted the pairs for the "toughest known" it seemed to me that 20 would be a quite high number, but at that point I had nothing to compare with. Now it seems that 20 is in fact below average.

I still wonder if the entwining affects the possibility of low clue puzzles. I ran an exhaustive check with checker on my "9-entwined" grid and found no 17s. I also had my computer search for 18s for 8 hours, but then I had to unplug the machine and stuff it into my car so I couldn't complete the test. Found no 18s in the first 8 hours though, I'll try to complete the search when I've got time. Thanks coloin for looking for high clue puzzles, I haven't really figured out how to do that yet.

RW

[coloin]

That is what we were trying to understand a while back, but we never did.

Yes...... we now know there are many many unavoidable sets ! But still many unanswered questions......

We are also clearer on definitions too
Although there is a diffence between grid solutions and clue completion [solutions]

To add:

2-rookery

Code: Select all

2-rookery- 18 clues - there are 36 pairs of these in a completed grid

no unavoidables in the two clues  - SFB grid - maximum entwining.

two unavoidables in the 2-rookery
one 4-clue unavoidable - and one 14 clue unavoidable
4 grid solutions - each having 4*14 ways to insert two clues
............
4 unavoidable sets in the 2-rookery e.g. three 4-clue and one 6 clue - 16 grid solutions - as my post above - each grid has 4*4*4*6 ways to insert four clues

3-rookery

Code: Select all

 3 - rookery - 27 clues - there are 84 in a completed grid [any 3 from 9][7+6+5+4+3+2+1]+[6...+1]+[5..+1].+[2]+[1]= 84

46656 1-rookeries (templates) , 1 equivalence class
419250816 2-rookeries , 170 classes
866092839552 3-rookeries , 92053(?) classes
...
46656 8-rookeries , 170 classes
1 9-rookery , 1 class

Condor did more work on these figures in an aptly titled thread !

Wolfgang found a higher total number number of clues that made a 2-rookery unique in the grids with a 17 [more than 3000] - this is essentially an index of how entwined all the 2-rookeries are.

Id like to mention that Moschopulos' grid only contains 2628 pairs of clues that make a 3-rookery unique and only 30 of the 84 3-rookeries are unique with a 2-clue pair (the others need at least 3 clues), while for the strangely familiar grid the numbers are 5049/60.
(So it was more surprising for me that Moschopulos' grid has a 19 clue than that it doesnt have a 16 clue)

So I wonder if the opposite is true - will a grid with a higher number of clues have less entwining - as in RW's example.

Thanks coloin for looking for high clue puzzles, I haven't really figured out how to do that yet.

Can we get a grid which is even more un - entwined ?

BTW Red Ed thought this grid was the best candidate for maximal clues - He tends to know these things - I cant find the post though.

Code: Select all

 Rededmax - 157629834826743591493185267268491375934257618571836942385914726619572483742368159

I dont think we have worked out any quick way - any statistical methods of counting clue frequencies as we did in finding 17s - are swamped by the enormity of the number of minimal puzzles around.

And as for grid choice - 2 of the 3 grids which I have found 35s in have been random grids [ran1 and one other]!

There are also plenty of 34s in both the SF and the SFB ! [explain that ]

Incidently - my method of homing in on high clue minimals depends on chosing an entwined 2-rookery [which one ?], and deciding by analysis of clue frequencies which clue of the 18 is the clue for that 18-clue unavoidable set. The other 17 clues are initailly removed from the string [from which puzzles are randomly generated] . What this does is to force the clues / and their respective unavoidable sets to coincide better.

[Viggo]

Thank you for explaining the terminology for me and the links!

One statement seems different from my results:

Id like to mention that Moschopulos' grid only contains 2628 pairs of clues that make a 3-rookery unique and only 30 of the 84 3-rookeries are unique with a 2-clue pair (the others need at least 3 clues), while for the strangely familiar grid the numbers are 5049/60.

Does it mean, that the SF-grid should have 60 of 84 3-rookeries which can be unique with 2 clues? A 3-rookery with 2 clues is the same as a 3-rookery with 6 solutions. It may be called minimal as for the 2-rookeries. My count on minimal 3-rookeries is 15 for the SF grid and not 60, so what is the difference here? I have added my count on minimal 3-rookeries in my previous post.

/Viggo