17-clue and 18-clue Sudoku update

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

Postby JPF » Wed Jan 17, 2007 8:11 pm

gsf wrote:...in a list papy sent to ruud there were 2 not in gordon's catalog
Code: Select all
120000080400900000000007003097000500000084000000000000800020010000500900000000000
120006000400000010000700500005010000006000900000004000008900000600000000000000042

these are the first new entries in over a year

Félicitations Papy!
You should tell us how you do it !

In the meantime, I made this study :

The strange familiar grid (SF) has been carefully studied in many threads of this forum.
This grid includes 29 non isomorphic 17 clues puzzles.
Code: Select all
SF
123456789456789132789213645275341968314968257968572413537194826642837591891625374


In the actual Gordon's list of the known 17s, there are other grids containing more than one essentially-different 17 clues puzzle.

Here's the list of the non isomorphic grids with more than 5 non isomorphic 17s :
Code: Select all
29  123456789456789132789213645275341968314968257968572413537194826642837591891625374
20  123456789456789123789132564264918357875324691931675248392861475547293816618547932
14  123457689456189273789236451265713948348965712971842536534698127612374895897521364
12  123456789456789132789213546264597813597138264831624957375862491648971325912345678
11  123456789456798132789231546237615894815924673964873251342567918591382467678149325
9   123456789456789132789213546267594813594138267831627954375862491648971325912345678
8   123456789456789123789132546231864975864597231975321468347918652592643817618275394
8   123456789456789231789231564214895673395627418867143952531974826648512397972368145
8   123457689456189327789236451271364895368591742594728136642875913837912564915643278
7   123456789456789132789213456271594863638127945945638217397845621514962378862371594
7   123456789456789132789231546247193658368574291591862374635928417812347965974615823
7   123456789456798132789231546264875391831629475975143268348912657592367814617584923
7   123457689456189237789632154245798316371265948968341572594816723637524891812973465
7   123457689456189273789263451267815394395674128814392567538746912641928735972531846
7   123457689456189372789362415261743958375918246948625731532876194617594823894231567
7   123457689456189732789362154238795461517846923964231578371524896642978315895613247
6   123456789456789123789132465215967348347518296698324517561843972874295631932671854
6   123456789456789123789132465217895346394627851568341297642513978835974612971268534
6   123456789456789123789132564267314958531968247894527316342675891675891432918243675
6   123456789456789132789123546231867954675941328948532671367294815592318467814675293
6   123456789456789132789123546275348961638291475941567328392675814567814293814932657
6   123456789456789132789132546267593418391847625845621973532974861678215394914368257
6   123456789456789132789132564234875691598361427671294358362917845847523916915648273
6   123456789456789132789132564261894357537621498948375216394567821675218943812943675
6   123456789456789132789213456214895673538627941967341825392174568671538294845962317
6   123456789456789132789213654248197563615348297937562418364925871592871346871634925
6   123456789456789132789231546237915468591864273648327915372548691814692357965173824
6   123456789456789132789231546278314695395678214641592378534967821862143957917825463
6   123456789456789132789231546295814673674392815831675924367928451548163297912547368
6   123456789456789231789231564215347896378695412964128357537914628692873145841562973
6   123456789456798132789213546247589613538167924961324857395641278672835491814972365
6   123456789456798132789213546267345891395681274814927365572869413648132957931574628
6   123456789456798132789213546274935861391682457865147293537829614618374925942561378
6   123457689456189237789263154268935741394716528517842963671324895842591376935678412
6   123457689456189237789632514274963851618524973935718426341295768567841392892376145
6   123457689456189327789632541237945168864713295915826473342598716578261934691374852


Here's the number N of non isomorphic grids with n non isomorphic 17 puzzles.
Code: Select all
N      n

1      29
0      28
0      27
0      26
0      25
0      24
0      23
0      22
0      21
1      20
0      19
0      18
0      17
0      16
0      15
1      14
0      13
1      12
1      11
0      10
1      9
3      8
7      7
20     6
18     5
80     4
226    3
1504   2
32244  1
-----
36628
     


JPF
Last edited by JPF on Tue Jan 23, 2007 5:20 am, edited 2 times in total.
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby gsf » Wed Jan 17, 2007 8:30 pm

here are the box-normal canonical grids for the two new papy 17's
Code: Select all
123456789456789132789231645237915864591648273648327951315872496864193527972564318
123456789456789231789132546215648973364917825978325614547291368691873452832564197

the first one is in gordon's list but the second is not
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Wed Jan 17, 2007 11:16 pm

Finally, something materialised out of this.........

Papy's trials were eventually friutful......I'm glad that the language/communication barriers were overcome by Papy's tenacity & the Players' help, well done.

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby RW » Thu Jan 18, 2007 8:55 am

gsf wrote:here are the box-normal canonical grids for the two new papy 17's
...
the first one is in gordon's list but the second is not

So it's still possible to find new 17s, even from grids already on the list... Would be nice to see the previous 17(s) from that first one, to see how much it differs from Papy's new puzzle.

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

Postby gsf » Thu Jan 18, 2007 9:40 am

RW wrote:Would be nice to see the previous 17(s) from that first one, to see how much it differs from Papy's new puzzle.

there was only one for that grid in gordons catalog
here are the submitted forms for gordon and papy
Code: Select all
000000081700050000020000000601200000080000040000090300300004000200000500000800000
120006000400000010000700500005010000006000900000004000008900000600000000000000042

and the box-normal canonical puzzles (based on the box-normal canonical grid) in the same order
Code: Select all
000400000000700030009000600000000004000008070608020001300000000000090500070000008
000400000000700030009000600000000004000008073608020000300000000000090500070000008
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby RW » Thu Jan 18, 2007 1:41 pm

gsf wrote:and the box-normal canonical puzzles (based on the box-normal canonical grid) in the same order
Code: Select all
000400000000700030009000600000000004000008070608020001300000000000090500070000008
000400000000700030009000600000000004000008073608020000300000000000090500070000008

Only one clue different, I thought Gordon had checked all those already... I wonder if there's more puzzles around the existing 17s that he has missed.

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

Postby m_b_metcalf » Thu Jan 18, 2007 5:30 pm

In a totally vain attempt to win at JPF's Puzzle Game:( I incidentally, while testing some new code, came up with a 17-clue that is not in Gordon's list, but which I suppose is isomorphic to one of them. Could I ask someone to kindly check?
Code: Select all
000000010600000000040000000000050602008000300001070000300600200050100000000809000



Thanks,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8339
Joined: 15 May 2006
Location: Berlin

Postby JPF » Thu Jan 18, 2007 5:52 pm

m_b_metcalf wrote:Could I ask someone to kindly check?
Code: Select all
000000010600000000040000000000050602008000300001070000300600200050100000000809000

#4185 in the Gordon's list
Code: Select all
000041000009000007050000300000000541000708000000000060000530200100000000000200000

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Thu Jan 18, 2007 8:32 pm

Well done Papy.
Apart from gfroyle, some unreferenced Japenese source and Wolfgang, to my knowledge no one else has found a 17.

Even before Checker give us any uniques.......

I will not take any credit for the third 17 in the first of Papy's grids
Code: Select all
...4........7...3...9...6..........4.....8.736.8.2....3............9.5...7......8
...4........7...3...9...6..........4.....8.7.6.832....3............9.5...7......8
...4........7...3...9...6..........4.....8.7.6.8.2...13............9.5...7......8

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby RW » Thu Jan 18, 2007 8:45 pm

A third one! Looks as though I picked the wrong grid, just ran checker on the other of Papys grids, only one there.:( Did you use checker, or did you just try adding and removing clues? Could there be even more in this grid?

Btw, setting r8c7=1 gives three new ones. Are those three puzzles already in the list?
...4........7...3...9...6..........4.....8.736.8.2....3............9.1...7......8
...4........7...3...9...6..........4.....8.7.6.8.2...53............9.1...7......8
...4........7...3...9...6..........4.....8.7.6.832....3............9.1...7......8

Actually, play around with r8c7 and r6c5 and the values 1,2 and 5 and there's six combinations that yield valid 17s with r5c9=3. For all of these grids you get three valid 17s with the same masks as the three for Papy's puzzle.

RW
Last edited by RW on Thu Jan 18, 2007 5:03 pm, edited 3 times in total.
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby coloin » Thu Jan 18, 2007 8:55 pm

No checker is still running - no uniques found as yet
No I ran a "suexmult" on the 16 common clues.

There were no more found at the 15 clue level
.................................
RW wrote:I wonder if there's more puzzles around the existing 17s that he has missed.


Yes, I suspect not many, but there is only one way to find out !

The reason why no one has found a 17 is that it is so difficult - starting from a likely grid less than 1 in 100000 will have a 17. Even when you know a grid has a 17 it is difficult to tease it out by analysing the slightly increased frequency of clues in randomly generated 21 and 22 clue sudoku puzzles in the grid.

With the improve version of checker this can be done quite quickly in many grids.

Since Gordon's program was so productive, no one really bothered, and since the generation of new 17s withered we lost interest, Gordon was intent on finding a 16, but when this became statistically unlikly we all gave up.....

With our improved puzzle generation techniques I would think it would not be too difficult to get a rough idea as to how complete Gordons collection is.

We could easily search fo all the puzzles in one 17-class [not yet classified]

From earlier on in this thread, the distribution of clues and box occupancy was.
Clues
Code: Select all
      7 0 1 1 1 2 2 3 3 4
    175 0 1 1 1 2 3 3 3 3
    197 0 1 1 2 2 2 2 3 4
   5908 0 1 1 2 2 2 3 3 3
     12 0 1 2 2 2 2 2 2 4
   8377 0 1 2 2 2 2 2 3 3
    730 0 2 2 2 2 2 2 2 3
     10 1 1 1 1 1 3 3 3 3
     81 1 1 1 1 2 2 2 3 4
   2220 1 1 1 1 2 2 3 3 3
     13 1 1 1 2 2 2 2 2 4

  11091 1 1 1 2 2 2 2 3 3
   4104 1 1 2 2 2 2 2 2 3
      5 1 2 2 2 2 2 2 2 2

Boxes
Code: Select all
    2 001122344:B
    2 001222334:B
    2 001223333:B
    2 002222234:B
   12 002222333:B
    7 011112344:B
    4 011113334:B
    2 011122235:B
   17 011122244:B
  177 011122334:B
  108 011123333:B
    2 011222225:B
  381 011222234:B
  946 011222333:B
  100 012222224:B
  945 012222233:B
  157 022222223:B
    1 111112235:B
   22 111112244:B
  486 111112334:B
  135 111113333:B
 1341 111122234:B
 2904 111122333:B
  659 111222224:B
11342 111222233:B
11769 112222223:B
 1405 122222222:B


Is it beyond our means to pick a common combination of each of these charactaristics and enumerate all the non-isomorphic 17s ?

I suspect that all the 17 puzzles have these 6,7 or even 8 equivalent clues....
Code: Select all
+---+---+---+
|1..|...|...|
|...|2..|...|
|...|...|3..|
+---+---+---+
|.4.|...|...|
|...|.5.|...|
|...|...|...|
+---+---+---+
|..6|...|...|
|...|..7|...|
|...|...|...|
+---+---+---+


Its difficult to find a puzzle without the first 7 clues [equivalent] as charted.

maybe this observation doesnt contribute much.......

C
Last edited by coloin on Thu Jan 18, 2007 5:33 pm, edited 1 time in total.
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby gsf » Thu Jan 18, 2007 9:32 pm

coloin wrote:I will not take any credit for the third 17 in the first of Papy's grids
Code: Select all
...4........7...3...9...6..........4.....8.736.8.2....3............9.5...7......8
...4........7...3...9...6..........4.....8.7.6.832....3............9.5...7......8
...4........7...3...9...6..........4.....8.7.6.8.2...13............9.5...7......8


the 3d one is already there
Code: Select all
.......817...5.....2.......6.12......8.....4.....9.3..3....4...2.....5.....8.....,684,gfroyle
Last edited by gsf on Thu Jan 18, 2007 5:56 pm, edited 1 time in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Thu Jan 18, 2007 9:53 pm

RW wrote:Are those three puzzles already in the list?
...4........7...3...9...6..........4.....8.736.8.2....3............9.1...7......8
...4........7...3...9...6..........4.....8.7.6.8.2...53............9.1...7......8
...4........7...3...9...6..........4.....8.7.6.832....3............9.1...7......8

these are already in the list (gordon(36627) + wolfgang(1) + papy(3))

[edit: corrected count discrepancies noted by JPF]
Last edited by gsf on Thu Jan 18, 2007 7:03 pm, edited 1 time in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby tarek » Thu Jan 18, 2007 10:02 pm

From what is there I have already assumed that someone should have already done this.......

1. take each invidual puzzle of the 17-clue catalog
2. 17 different 16 clue templates.
3. plug in an extra clue (81-17)=64 times per template

that shouldn't be that hard work & I assume it was done:!::?:

tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby RW » Thu Jan 18, 2007 10:07 pm

gsf wrote:the 3d one is already there

I believe coloin had them in the wrong order. The second one was the new puzzle:
Code: Select all
...4........7...3...9...6..........4.....8.7.6.832....3............9.5...7......8


gsf wrote:
RW wrote:Are those three puzzles already in the list?
...4........7...3...9...6..........4.....8.736.8.2....3............9.1...7......8
...4........7...3...9...6..........4.....8.7.6.8.2...53............9.1...7......8
...4........7...3...9...6..........4.....8.7.6.832....3............9.1...7......8

these are already in the list (gordon(36621) + wolfgang(1) + papy(2))

So papy's second puzzle was also found by just adding one clue and removing another from an existing 17... then there might definitely be more of these. Someone with an apropriate program should do the test tarek suggested.

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

PreviousNext

Return to General