## 17-clue and 18-clue Sudoku update

Everything about Sudoku that doesn't fit in one of the other sections
coloin wrote:Here is another method I have dreamt up
...
Here is the plan
...
Now here I present two consequetive 17s from my 41651 sample, numbered by numerical order.
Code: Select all
`1413  #  0000000090007000007002030000000000006940000000000002700025000000100903040000600001414  #  000000009000700000700203000000000000694000000000000270310090004002000000000560000`

Back to the consecutive gsf-minlex 17s.

The 2 puzzles (what you called 1413, 1414) were too different.

There are consecutive minlex 17s with more common clues.
Excluding pairs of puzzles such one is derived from the other by a {-2+2}, here are some examples :

# refers to # in the Gordon's list

14 clues :
Code: Select all
` *-----------* |..3|4..|...| |.56|...|...| |...|1.2|...| |---+---+---| |2..|...|6..| |.7.|8..|...| |...|...|3..| |---+---+---| |..4|.6.|...| |...|...|.37| |8..|...|..1| *-----------*  # 39248 *-----------* |..3|4..|...| |.56|...|...| |...|1.2|...| |---+---+---| |2..|...|6..| |.7.|8..|...| |...|...|3..| |---+---+---| |..4|.6.|...| |...|...|.73| |8..|...|.9.| *-----------*  # 39246`

13 clues :
Code: Select all
` *-----------* |.2.|...|...| |...|1..|.36| |.89|..7|...| |---+---+---| |...|...|...| |7..|6..|...| |...|.2.|9..| |---+---+---| |...|.9.|...| |5..|..4|...| |..1|..3|..4| *-----------*  # 34557 *-----------* |.2.|...|...| |...|1..|.36| |.89|..7|...| |---+---+---| |...|...|...| |7..|6..|...| |...|.2.|9..| |---+---+---| |...|.9.|...| |5.1|..3|...| |...|..4|..7| *-----------*  # 2382`

JPF
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

If the possible clues can be coded it would be possible to look for new puzzles in the "gaps".

I agree the puzzles I quoted are far apart.......whether it can be done or not depends on the reductions infered by the minlex fixed clues and the requirement to be a "minlex puzzle".

Perhaps it would be a start to attempt to look at closer puzzles ! [but perhaps not within 2*] - so I think your choice of puzzles is very reasonable........

Having said that the reason I chose those puzzles was because when you look at where anon17s fit in, not unsurprisingly they do fit in in the so called larger gaps.

C
coloin

Posts: 1790
Joined: 05 May 2005

I did a "4-on" on the 13 clue example.
Code: Select all
` *-----------*  |.2.|...|...|  |...|1..|.36|  |.89|..7|...|  |---+---+---|  |...|...|...|  |7..|6..|...|  |...|.2.|9..|  |---+---+---|  |...|.9.|...|  |5..|...|...|  |...|...|...|  *-----------* `

Actually it was a set of "3-ons"
Code: Select all
`.2..........1...36.89..7............7..6.........2.9......9....5....4.............2..........1...36.89..7............7..6.........2.9......9....5....8.............2..........1...36.89..7............7..6.........2.9......9....5...1..............2..........1...36.89..7............7..6.........2.9......9....5...4..............2..........1...36.89..7............7..6.........2.9......9....5...6..............2..........1...36.89..7............7..6.........2.9......9....5...7..............2..........1...36.89..7............7..6.........2.9......9....5..3...............2..........1...36.89..7............7..6.........2.9......9....5..7...............2..........1...36.89..7............7..6.........2.9......9....5..8...............2..........1...36.89..7............7..6.........2.9......9....5.1...............`

If I could restrict the clue options [to the end of the string] it would be faster !

No new 17-puzzles exist for this "gap" in the minlex17list.

Perhaps I need to try a 12 clue

C
coloin

Posts: 1790
Joined: 05 May 2005

coloin wrote:I am wondering if anon17 is gfroyles alter ego

Not me I can assure you..

Gordon
gfroyle

Posts: 214
Joined: 21 June 2005

### re: anon17

above, JPF (2007.Sep.7) wrote:I wonder why the number of 17s has been stuck at 46,999 now for a day...

and today (Sep.10) it has moved -- up to 47,277 -- with new finds from anon17 -- evidently still going strong

Pat

Posts: 3796
Joined: 18 July 2005

Here are some stats for the first 47000 17s :
ER is the rating from Sudoku Explainer, n the number of puzzles with this rating and an example with its # in the Gordon's list.
Code: Select all
`  ER         n   #(example)                                                        9.1         1     41826                                                         9.0         2     35409                                                         8.9         5      2973                                                         8.8         2      6374                                                         8.5        12      2519                                                         8.4        10      1076                                                         8.3        48       210                                                         8.2         7      1458                                                         7.9         6      4934                                                         7.8        40       976                                                         7.7        35      2233                                                         7.6        45      3976                                                         7.4         2     12177                                                         7.3        76        28                                                         7.2       457        47                                                         7.1       977         9                                                         7.0        14      8778                                                         6.9        16      2163                                                         6.8        59      1693                                                         6.7       533      2626                                                         6.6      2559        21                                                         6.5        20      1383                                                         6.2         2     16716                                                         5.8         1     14540                                                         5.7        35      2993                                                         5.6       546       126                                                         5.2         4      9864                                                         5.0         2      9229                                                         4.8         1     44484                                                         4.7         4      3066                                                         4.6       149       325                                                         4.5       316       276                                                         4.4      1099        45                                                         4.2        20       600                                                         4.0        14      1947                                                         3.8         3     20250                                                         3.6        19       427                                                         3.4       527       166                                                         3.2        34      2368                                                         3.0       374       151                                                         2.8       583        68                                                         2.6      9260         7                                                         2.5       198       152                                                         2.3       474         4                                                         2.0      9085         5                                                         1.7      2739        29                                                         1.5     16468         1                                                         1.2       116       121            ------                                                              46999                                                                    `

The missing puzzle #42272 is not solvable by Explainer !
Code: Select all
`800200000100000500000006300060003000000010080000400020030050100000800000000000070`

Any explanation ?

JPF
Last edited by JPF on Wed Sep 12, 2007 8:46 am, edited 1 time in total.
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

JPF wrote:The missing puzzle #42272 is not solvable by Explainer !
Code: Select all
`800200000100000500000006300060003000000010080000400020030050100000800000000000070`

Any explanation ?

Turn off BUG in the solving technique and you'll find the answer. So there's a bug in the BUG.

Edit: SE has no problems until you get to here:
Code: Select all
` *--------------------------------------------------* | 8    49   6    | 2    3    5    | 49   1    7    | | 1    47   3    | 9    47   8    | 5    6    2    | | 479* 2    5    | 1    47   6    | 3    49   8    | |----------------+----------------+----------------| | 49   6    2    | 7    8    3    | 49   5    1    | | 3    479* 479* | 5    1    2    | 6    8    49   | | 5    8    1    | 4    6    9    | 7    2    3    | |----------------+----------------+----------------| | 2    3    8    | 6    5    7    | 1    49   49   | | 467* 15   47   | 8    9    14   | 2    3    56   | | 469* 15   49   | 3    2    14   | 8    7    56   | *--------------------------------------------------*`

which it considers to be what we would call here a BUG+5 grid on 4. However, it isn't since, for instance, if we removed the candidate 4 from each of the above *'d cells, there would still be 3 9's in row 5.
re'born

Posts: 551
Joined: 31 May 2007

### Re: re: anon17

Pat wrote:and today (Sep.10) it has moved -- up to 47,277 -- with new finds from anon17 -- evidently still going strong

He sent me another 267 puzzles, but also indicated that the rate-of-finding has dropped significantly, presumably because we really are getting close to finding all the "low hanging fruit".

He also indicated that the increase in speed is primarily due to the reduction in the number of calls to the solver (not just raw solver speed).. If we look at his earlier message

For a clue to how it's done: in the full {-1,+1} test
(on an 18) the solver is called around 18*52 times, and
in the full {-2,+2} test (on a 17), it is called around
(17*16/2)*1467 times.

then we see that the number of calls required to do a {-1,+1} is far less than you would naively expect just by deleting a clue, and then testing every possible puzzle obtained by adding a clue.

So this means that somehow the search is structured so that failed efforts at solution are used to trim the future search...

I noticed this at the time, but have not had time to think through it properly.

But suppose we are doing a +1 search on a 17 (to get more 18s)... Naively we might consider the 64 open positions and then for each position try each symbol, making 64 x 9 18s to solve.

Now what happens if the first one (ie symbol 1 in first empty position) fails - then there are at least two completions, maybe many more. Any two completions P1 and P2 will be the same on the original 17 clues and the 18th clue that we are currently testing, but may have other places where they are the same...

Then if P1 and P2 *both* have symbol x in position (r,c) (not one of the original 17 nor the 18th) then there is no point in even *trying* to solve the 18-clue puzzle obtained from P by putting x into position (r,c) because we already KNOW that it cannot complete uniquely.

I don't know if this is what anon17 is doing precisely, and unfortunately I don't have time today to implement it, but it would certainly seem possible to extract lots of useful information from a single run of the solver..

Feel free to implement and test ..

Gordon
gfroyle

Posts: 214
Joined: 21 June 2005

Thanks indeed anon17, that shows the puzzles are still out there - even though we cant generate them.

Thanks for the insight into the improvements.........after a while the penny dropped.

Say you are doing a {-2+2} on a 17, by adding 6 clues at a time you can effectivly test 10 pairs of clues at once...provided thy have more than 1 grid solution. And other "useless" clues can be compiled as outlined.

In a {-3+3} instance this means if you add x clues to make a [maximal] pseudopuzzle with 2 solutions then all 3-combinations of the x clues are not valid. One unavoidable set is left !

How far can we take this ?.............

With all these new puzzles, this will have increased the size of the group which at present is known to be closed for the [-3+3} operation........any chance of repeating that analysis ?

Do we think a roving {-3+3} is feasable ?

It might even be possible to fix these 5 clues
Code: Select all
`+---+---+---+|1..|...|...||...|...|...||...|...|...|+---+---+---+|...|...|...||...|.5.|...||...|...|.6.|+---+---+---+|...|...|...||...|..8|...||...|...|..9|+---+---+---+ - I've never seen any puzzle without this "equivalent"`

C
Last edited by coloin on Tue Sep 11, 2007 9:20 pm, edited 1 time in total.
coloin

Posts: 1790
Joined: 05 May 2005

coloin wrote:T
With all these new puzzles, this will have increased the size of the group which at present is known to be closed for the [-3+3} operation........any chance of repeating that analysis ?

here are the < #classes #class-size > for the 1 through 5 closures on |G|=47277
Code: Select all
`===    47277 {1}* ===23464    1 4838    2 1153    3  676    4  264    5  173    6   99    7   59    8   47    9   30   10   26   11   18   12   16   13    8   14    3   15    9   16    5   17    5   18    4   19    5   20    1   21    3   22    1   23    5   24    5   25    2   27    1   28    1   30    2   31    2   32    1   33    1   37    1   38    2   41    1   42    1   50    1   55    1   87    1  173    1  560    1  616===    47277 {2}* ===11522    1 2885    2  841    3  478    4  228    5  146    6   78    7   66    8   41    9   29   10   17   11   17   12   12   13    7   14    5   15   12   16    5   17    4   18    7   19    3   20    1   21    3   22    6   23    4   24    1   25    1   26    1   28    2   30    1   31    1   32    1   33    3   35    1   39    1   43    1   44    1   56    1   58    1   64    1   65    1   70    1   80    1   82    1   83    1 19194===    47277 {3}* === 2823    1  550    2  133    3   72    4   28    5   13    6    7    7    3    8    6    9    2   10    4   11    2   12    1   13    1   14    1   27    1 42180===    47277 {4}* ===   73    1    9    2    1 47186===    47277 {5}* ===    1 47277`

and the computation times for 1 through 5 -- not a heavy load
Code: Select all
`real    0m4.80sreal    0m38.16sreal    4m15.40sreal    20m42.04sreal    58m17.73s`
Last edited by gsf on Thu Sep 13, 2007 12:34 am, edited 1 time in total.
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

JPF wrote:Here are some stats for the first 47000 17s :
ER is the rating from

Good work JPF.. I would like to include this information in the DB, but what exactly does the rating measure... the "most difficult" strategy that must be used, or some combination of number of strategies, their difficulty etc.

Gordon
gfroyle

Posts: 214
Joined: 21 June 2005

gfroyle wrote:what exactly does the rating measure... the "most difficult" strategy that must be used, or some combination of number of strategies, their difficulty etc.

The rating provided by SE is the difficulty rating of the most complex move required to solve the puzzle.

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

JPF, how long did it take SE to rate the 47K 17's?
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

gfroyle wrote:Good work JPF..
Thanks.
Much easier than finding new 17s.

RW wrote:
gfroyle wrote:what exactly does the rating measure... the "most difficult" strategy that must be used, or some combination of number of strategies, their difficulty etc.

The rating provided by SE is the difficulty rating of the most complex move required to solve the puzzle.

Here you can find the difficulty ratings of the solving techniques.
According to his author the scale varies between 1.2 to 12.0, but the most difficult rating found up to now is 11.4.

gsf wrote:JPF, how long did it take SE to rate the 47K 17's?
I don't know.
We know that SE is very slow when the rating is >10.0 which is fortunately not the case for this 17s collection.
To answer your question, I made a run with the first 1000 puzzles : 80 seconds ; so I guess it took 1 hour for the 47K 17's (before clerical work...)
Nothing to do with the speed of your program gsf !

JPF
JPF
2017 Supporter

Posts: 3755
Joined: 06 December 2005
Location: Paris, France

JPF wrote:To answer your question, I made a run with the first 1000 puzzles : 80 seconds ; so I guess it took 1 hour for the 47K 17's (before clerical work...)
Nothing to do with the speed of your program

How do you make it rate a whole bunch of puzzles? I downloaded it and could only see how to use it interactively, rather than in "batch mode"...
gfroyle

Posts: 214
Joined: 21 June 2005

PreviousNext