The New Sudoku Players' Forum

[blue]

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

[Serg]

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

Serg

[dobrichev]

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]

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.

[blue]

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.

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.

[dobrichev]

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

In minlex

Code: Select all

123456789457189236698273514214837965376925841589614372732541698861392457945768123


[blue]

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)

[Mathimagics]

Hello everyone!

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

[Mathimagics]

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.

[blue]

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

[Mathimagics]

Silly me, I meant to say "known maximum" of course!

[Mathimagics]

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

[Mathimagics]

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

[coloin]

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 !

[blue]

Hi Mathimagics,

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

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.