Grids containing a 21 but no 20

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

Grids containing a 21 but no 20

Postby blue » Wed Jun 26, 2019 5:16 pm

A post, relating to this thread: Low/Hi Clue Thresholds

I'm getting that these grids don't have a 20 clue puzzle, but do have 21 clue puzzles.

Code: Select all
123456789456789123789123456214897365365214897897365214541632978632978541978541632
123456789456789123789132465218967534564213978937548216391875642645321897872694351
123456789457189326689327154216534897745891632938672541361245978574918263892763415
123456789457189326689327154216534897745891632938672541392765418574918263861243975

Were any of them previously known ?
(They're in minlex form).

Would somebody please verify the "no 20" finding, using dobrichev's GridChecker app ?
(I've never used it, and the Windows version (for download), won't run for me -- missing a DLL).

Cheers,
Blue.

P.S.: The grids are from the set of 560151 ED grids having at least one non-trivial automorphism.
The first has 18 automorphisms total, the 2nd & 3rd have six, and the 4th has two.

The remainder (of the 560151 grids), have a 20-clue (or smaller) puzzle.
[ There are several grids in that list, that have a 20 clue, but no 19 clue puzzles. ]
blue
 
Posts: 877
Joined: 11 March 2013

Re: Grids containing a 21 but no 20

Postby Serg » Wed Jun 26, 2019 7:26 pm

Hi, Blue!
Interesting observation!
Do you mean that 4 published grids have no 17, 18, 19-clue puzzles too?

Serg
Serg
2018 Supporter
 
Posts: 652
Joined: 01 June 2010
Location: Russia

Re: Grids containing a 21 but no 20

Postby dobrichev » Wed Jun 26, 2019 7:51 pm

Hi blue,

In http://forum.enjoysudoku.com/post65611.html#p65611 the second grid was given as exemplar for a particular symmetry class.

There was a single grid with large clique (18?) found by Guenter Stertenbrink. From memory, it was checked. I can't remember the minimal size of the puzzles there. Most probably it was highly symmetric too.

I will give a try to confirm these 4 grids later today or tomorrow.
dobrichev
2016 Supporter
 
Posts: 1745
Joined: 24 May 2010

Re: Grids containing a 21 but no 20

Postby dobrichev » Wed Jun 26, 2019 8:52 pm

Confirming non-existence of 20-clue puzzles in these 4 grids.
Code: Select all
123456789456789123789123456214897365365214897897365214541632978632978541978541632 puz20=0 puz21= 7488
123456789456789123789132465218967534564213978937548216391875642645321897872694351 puz20=0 puz21= 3138
123456789457189326689327154216534897745891632938672541361245978574918263892763415 puz20=0 puz21= 3894
123456789457189326689327154216534897745891632938672541392765418574918263861243975 puz20=0 puz21=19682

The number of 21-clue puzzles, if matched, could be used as kind of measure for the correctness of my code.
dobrichev
2016 Supporter
 
Posts: 1745
Joined: 24 May 2010

Re: Grids containing a 21 but no 20

Postby blue » Wed Jun 26, 2019 8:53 pm

Serg wrote:Do you mean that 4 published grids have no 17, 18, 19-clue puzzles too?

Yes, exactly.
At least 21 clues are required, for a puzzle having one of these grids as it's unique solution.

dobrichev wrote:I will give a try to confirm these 4 grids later today or tomorrow.

Thanks, and thanks for the reference for the 2nd grid.
All 4 grids have MCN=15. The tests should go quickly, I think.

Cheers.
blue
 
Posts: 877
Joined: 11 March 2013

Re: Grids containing a 21 but no 20

Postby dobrichev » Wed Jun 26, 2019 9:34 pm

... and the grid with highest known MCN=16 is http://forum.enjoysudoku.com/post15867.html#p15867

In minlex
Code: Select all
123456789457189236698273514214837965376925841589614372732541698861392457945768123
dobrichev
2016 Supporter
 
Posts: 1745
Joined: 24 May 2010

Re: Grids containing a 21 but no 20

Postby blue » Wed Jun 26, 2019 11:05 pm

dobrichev wrote:Confirming non-existence of 20-clue puzzles in these 4 grids.
(...)
The number of 21-clue puzzles, if matched, could be used as kind of measure for the correctness of my code.

Thank you !

I got the same puzzle counts:
Code: Select all
#1 - 7488 21's, 416 ED (none with a non-trivial automorphism)
#2 - 3138 21's, 523 ED (none with a non-trivial automorphism)
#3 - 3894 21's, 649 ED (none with a non-trivial automorphism)
#4 - 19682 21's, 9841 ED (none with a non-trivial automorphism)
blue
 
Posts: 877
Joined: 11 March 2013

Re: Grids containing a 21 but no 20

Postby Mathimagics » Wed Jun 26, 2019 11:24 pm

Hello everyone! 8-)

Thanks for this information - so, so interesting!!!

What exactly does MCN mean in the posts above? I assume it's a lower bound for min number of clues based on maximum known UA clique size?

Cheers!
MM
Last edited by Mathimagics on Wed Jun 26, 2019 11:59 pm, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: Grids containing a 21 but no 20

Postby Mathimagics » Wed Jun 26, 2019 11:58 pm

blue wrote:Would somebody please verify the "no 20" finding, using dobrichev's GridChecker app ?
(I've never used it, and the Windows version (for download), won't run for me -- missing a DLL).


The missing dll (VCOMP120.dll) is part of VS2013 redistributable support, you can get it here.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: Grids containing a 21 but no 20

Postby blue » Thu Jun 27, 2019 12:56 am

Mathimagics wrote:What exactly does MCN mean in the posts above? I assume it's a lower bound for min number of clues based on maximum known UA clique size?

Yes ... with hesitation over the word "known".
RW mentions seeing grids with (N-1) disjoint (presimably small) UA's, and "seeing" another one in the cells not covered by the UAs.

RW also reports having a collection of 1000 grids with MCN=16 (here).
blue
 
Posts: 877
Joined: 11 March 2013

Re: Grids containing a 21 but no 20

Postby Mathimagics » Thu Jun 27, 2019 1:11 am

Silly me, I meant to say "known maximum" of course! :lol:
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Grids containing a 21 but no 20

Postby Mathimagics » Sat Jul 20, 2019 6:55 pm

I got excited when I thought that the LCT-20 project had turned up a 5th grid with no 20C:

Code: Select all
123456789457189623689723451231645897745891236896237145312564978574918362968372514


This was identified by the BlueMagic tool (from you know who!). It was the only grid among the first batch of 1.5 million grids which I tested, that failed to turn up a 20C. The grid batch was comprised of grids that had not yet been hit by the random 20C generator program.

As I understand it, when this program fails to find a 20C, then the grid:

  • just might be a no-20C case
  • or, more likely, it has 20C puzzles, but none with the 668 clue pattern which the app targets

So its kind exceptional either way you look at it.

The magic app took 90s to fully search the pattern space for this grid (typically it finds 20C's in 0.005s, by the way).

ANyway, I threw my not very magic slow 20C tester app on it and after about 20s of random reductions it found a 20C, which, as can be seen, has a 677 pattern (both by band and by stack):

Code: Select all
 +-------+-------+-------+
 | . 2 . | . . . | . . . |
 | 4 . . | . 8 . | . . 3 |
 | . . 9 | 7 . . | . . . |
 +-------+-------+-------+
 | . . . | 6 . . | . 9 . |
 | . . 5 | . . . | . . . |
 | 8 . . | . 3 . | 1 . 5 |
 +-------+-------+-------+
 | 3 1 . | . . 4 | . . 8 |
 | . . . | 9 . . | . 6 . |
 | . . . | . . . | . . 4 |
 +-------+-------+-------+


So no cigar on the "No 20C" attempt, but it is good to know that my little program still has its uses ... 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: Grids containing a 21 but no 20

Postby Mathimagics » Sun Jul 21, 2019 3:38 pm

It raises an interesting question, though.

Does having a 20C puzzle with 677 distribution but nothing for 668 suggest that the overall 20C puzzle count is probably very small?

Perhaps Mladen or blue might enumerate them for this grid ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1329
Joined: 27 May 2015
Location: Canberra

Re: Grids containing a 21 but no 20

Postby coloin » Mon Jul 22, 2019 1:23 pm

We will see I hope

Code: Select all
                                                                                    grid    20s   ED 20s     21s   ED 21s   av. size

123456789456789123789123456214897365365214897897365214541632978632978541978541632  -Blue1    0      0       7488    416     26.04
123456789456789123789132465218967534564213978937548216391875642645321897872694351  -Blue2    0      0       3138    523     26.00
123456789457189326689327154216534897745891632938672541361245978574918263892763415  -Blue3    0      0       3894    649     25.94
123456789457189326689327154216534897745891632938672541392765418574918263861243975  -Blue4    0      0      19682   9841     25.71
                                                                                                                           
123456789456789123789123456231564897564897231897231564312645978645978312978312645  - MC      648    1                       25.68
123456789457189326689327154231645897745891632896732541318264975574918263962573418  - PT      6      1                       25.55
                                                                                                                           
123456789457189623689723451231645897745891236896237145312564978574918362968372514  - Magic   1*     1*                      25.67


PT grid - made by Red Ed Platinum Trellis - He may not be happy that he has been surpassed ! :)
* not confirmed as the only one !
coloin
 
Posts: 1813
Joined: 05 May 2005

Re: Grids containing a 21 but no 20

Postby blue » Tue Jul 23, 2019 1:39 pm

Hi Mathimagics,

Mathimagics wrote:I got excited when I thought that the LCT-20 project had turned up a 5th grid with no 20C:

Code: Select all
123456789457189623689723451231645897745891236896237145312564978574918362968372514

(...)

The magic app took 90s to fully search the pattern space for this grid (typically it finds 20C's in 0.005s, by the way).

I'm pretty sure you meant 90ms (milliseconds).

Mathimagics wrote:It raises an interesting question, though.

Does having a 20C puzzle with 677 distribution but nothing for 668 suggest that the overall 20C puzzle count is probably very small?

Perhaps Mladen or blue might enumerate them for this grid ...

It has 24 20C's total (1.5s), and 2 ED 20C's.

Code: Select all
.......8....1....3..9.2.4...3.6.....7.5.9.2..........5..2..497...4.......6.3..... (morph of original puzzle)
......78.4.....6....9.2...1..16.......5.9....8....7.4.3....4.7....91...2.........

For the automorphic grids, the answer to the question is "yes, the overall 20C puzzle count is very small".

Code: Select all
123456789456789123789123456231564897564897231897231564312645978645978312978312645 : 648 20C,  1 ED (MC)
123456789456789123789123456231564978564978231978231564312645897645897312897312645 : 702 20C,  7 ED
123456789457189326689327154231645897745891632896732541312564978574918263968273415 :  12 20C,  1 ED
123456789457189623689723451231645897745891236896237145312564978574918362968372514 :  24 20C,  2 ED
123456789457189623986327451231645897698732145745891236312564978574918362869273514 :  96 20C,  8 ED
123456789456789123789123456214365897365897214897214365541632978632978541978541632 :  12 20C,  2 ED
123456789456789123789132465218967534645321897937548216391875642564213978872694351 :   6 20C,  1 ED
123456789456789123798132465219543876564897231837261594381624957645978312972315648 :   6 20C,  1 ED
123456789457189326689327154231645897745891632896732541318264975574918263962573418 :   6 20C,  1 ED (PT)
123456789457189326689327154214563978375918462968274513541632897732891645896745231 :   8 20C,  4 ED
123456789457189236689237154218365947745918362936742518391624875574891623862573491 :   3 20C,  1 ED
123456789456789123789123465215937648634218957897564312361872594542391876978645231 :  12 20C,  6 ED
123456789456789123789123465215937648634218957978564312361872594542391876897645231 :  16 20C,  8 ED
123456789456789123789123465215938647634217958978645231361892574542371896897564312 :  10 20C,  5 ED
123456789456789123789123465217634958645978231938215647371542896564897312892361574 :  20 20C, 10 ED

The grid from above, is #4 in the list.
We still don't have a "no-668" grid, that only has the non-trivial automorphism.
blue
 
Posts: 877
Joined: 11 March 2013

Next

Return to General