The New Sudoku Players' Forum

[JPF]

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  #  000000009000700000700203000000000000694000000000000270002500000010090304000060000
1414  #  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

[coloin]

Im glad you have had a think about this too.......

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]

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

[gfroyle]

I am wondering if anon17 is gfroyles alter ego

Not me I can assure you..

Gordon

[Pat]

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

[JPF]

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

[re'born]

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.

[gfroyle]

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

[coloin]

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

[gsf]

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.80s
real    0m38.16s
real    4m15.40s
real    20m42.04s
real    58m17.73s


[gfroyle]

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

[RW]

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

[gsf]

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

[JPF]

Good work JPF..

Thanks.
Much easier than finding new 17s.

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.

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

[gfroyle]

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