17-clue and 18-clue Sudoku update

Everything about Sudoku that doesn't fit in one of the other sections

Postby JPF » Sat Sep 08, 2007 10:12 pm

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  #  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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Sat Sep 08, 2007 10:39 pm

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
 
Posts: 1633
Joined: 05 May 2005

Postby coloin » Sun Sep 09, 2007 9:03 am

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: 1633
Joined: 05 May 2005

Postby gfroyle » Sun Sep 09, 2007 1:37 pm

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

Postby Pat » Mon Sep 10, 2007 3:48 pm

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
User avatar
Pat
 
Posts: 3425
Joined: 18 July 2005

Postby JPF » Mon Sep 10, 2007 9:13 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby re'born » Mon Sep 10, 2007 9:20 pm

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

Postby gfroyle » Tue Sep 11, 2007 1:31 am

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

Postby coloin » Tue Sep 11, 2007 11:26 pm

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: 1633
Joined: 05 May 2005

Postby gsf » Wed Sep 12, 2007 12:47 am

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

Postby gfroyle » Thu Sep 13, 2007 1:51 am

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

Postby RW » Thu Sep 13, 2007 1:04 pm

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

Postby gsf » Thu Sep 13, 2007 2:49 pm

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

Postby JPF » Thu Sep 13, 2007 11:53 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby gfroyle » Fri Sep 14, 2007 1:49 pm

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

Return to General