High Clue Puzzles

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

High Clue Puzzles

Postby Mathimagics » Mon Nov 04, 2019 9:45 am

We know, thanks to Mladen, that there exists a grid with a minimal 40-clue puzzle (in fact it has at least 2):

Code: Select all
123456789456789123798132564231675498584923617679841235367518942815294376942367851
1..4....9.5..8..2..981.2..4..1..5.9.58.92...7.798412.5.67518.4281.294.76.........   40
1..4....9.5..89.2..981.2..4..1..5.9.58..2...7.798412.5.67518.4281.294.76.........   40


And we also know that it has at least 38 x 37-clue puzzles:
Minimal 37C list: Show
Code: Select all
...4....9.5..8.....981.2..42.1..5.9.58.9....7.79841..5.67518.4281.294.76.........   37
...4....9.5..89....981.2..42.1..5.9.58......7.79841..5.67518.4281.294.76.........   37
1..45...9.5..8.....981.2..42.1..5.9.58.9....7.798412.5..7.1..4281.294.76.........   37
1..45...9.5..89....981.2..42.1..5.9.58......7.798412.5..7.1..4281.294.76.........   37
1..4....9.5...9.2..981.2.64..1..5...58.92.....79.412.5.67518.4281.2.4.76.........   37
1..4....9.5..8.....981.2..4.....5.9.5..92..17.7984.2.5.67518.4281.294.76.........   37
1..4....9.5..89....981.2..4.....5.9.5...2..17.7984.2.5.67518.4281.294.76.........   37
1..4....9.5...9.2..981.2.64..1..5...58..2.....79.412.5.67518.4281.294.76.........   37
1..4....9.5.....2..981.2.64..1..5...58.92.....79.412.5.67518.4281.294.76.........   37
1..4....9.5.....2..981.2.64..1..5...5..92...7.79.412.5.67518.4281.294.76.........   37
1..45.....5..89.2..9.1.2..4..1....9.58..2...7.79.412.5.67518.4281.294.76.........   37
1..4....9.5..8..2..981.2.64..1..5.9.58.92.....7...12.5.67518.4281.294.76.........   37
1..4....9.5.....2..981.2.64..1..5.9.58.92.....7..412.5.67518.4281.294.76.........   37
1..45...9....8..2..9.1.2..4..1..5.9..8.92...7..98412.5.67518.4281.294.76.........   37
1..45...9....8..2..9.1.2..4..1..5.9..8.92...7.79.412.5.67518.4281.294.76.........   37
1..45...9....8..2..9.1.2..4..1....9.58.92...7.79.412.5.67518.4281.294.76.........   37
1..45...9....89.2..9.1.2..4..1..5.9..8..2...7..98412.5.67518.4281.294.76.........   37
1..45...9....89.2..9.1.2..4..1..5.9..8..2...7.79.412.5.67518.4281.294.76.........   37
1..45...9....89.2..9.1.2..4..1....9.58..2...7.79.412.5.67518.4281.294.76.........   37
1..45...9.5..8..2..9.1.2..4..1....9..8.92...7.79.412.5.67518.4281.294.76.........   37
1..45...9.5..89.2..9.1.2..4..1....9..8..2...7.79.412.5.67518.4281.294.76.........   37
1..4....9.5..8..2..981.2..4.....5.9.5..92..17.79.4.2.5.67518.4281.294.76.........   37
1..4....9.5..89.2..981.2..4.....5.9.5...2..17.79.4.2.5.67518.4281.294.76.........   37
1..4....9..6..9.2..981.2..4..1..5.9.58......7.798.12.5.67518.4281.294.76.........   37
1..45...9....8..2..981.2..4..1..5.9..8.9....7.79.412.5.67518.4281.294.76.........   37
1..45...9....89.2..981.2..4..1..5.9..8......7.79.412.5.67518.4281.294.76.........   37
1..45...9.5.....2..981.2..4..1..5.9....9....7.798412.5.67518.4281.294.76.........   37
1..45...9.5.....2..981.2..4..1....9....92...7.798412.5.67518.4281.294.76.........   37
1..45...9.5.....2..981.2..4..1....9.5..9....7.798412.5.67518.4281.294.76.........   37
1..45...9.5..8..2..981.2..4..1..5.9....9....7.79.412.5.67518.4281.294.76.........   37
1..45...9.5..8..2..981.2..4..1....9....92...7.79.412.5.67518.4281.294.76.........   37
1..45...9.5..8..2..981.2..4..1....9.5..9....7.79.412.5.67518.4281.294.76.........   37
1..45...9.5...9.2..981.2..4..1..5.9.........7.798412.5.67518.4281.294.76.........   37
1..45...9.5...9.2..981.2..4..1....9.....2...7.798412.5.67518.4281.294.76.........   37
1..45...9.5..89.2..981.2..4..1..5.9.........7.79.412.5.67518.4281.294.76.........   37
1..45...9.5..89.2..981.2..4..1....9.....2...7.79.412.5.67518.4281.294.76.........   37
1..4....9.5..8..2..981.2.64..1..5.9.5..92...7.7...12.5.67518.4281.294.76.........   37
1..4....9.5.....2..981.2.64..1..5.9.5..92...7.7..412.5.67518.4281.294.76.........   37


Now, consider the "Continuity Question". Given a solution grid G, let L(G) be the least # of clues for a puzzle on G, and H(G) be the highest # of clues for a minimal puzzle on G. Is there necessarily a K-clue minimal puzzle for every K in the range [L, H]?

Mladen's 40C grid shows us that perhaps the answer might well be NO - there is the suggestion that, for this grid, we might have a "hole", as for K = 38, 39 we have yet to find a minimal puzzle. But a NO requires that we demonstrate conclusively that no 38C or 39C puzzle exists on this grid.

The challenge is, how to determine whether this really is a hole, or whether we just have to look harder to fill it in!

And it's a tough problem, it seems - if a 39C exists on this grid it must be at some "distance" from the 40C puzzles. A {-3, +2} search on the 40C puzzles turns up nothing. I am looking at the feasibility of a {-4, +3} search (unless somebody already has done this?) but the numbers are intimidating ...

Anyway, hopefully this will spark some discussion! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1481
Joined: 27 May 2015
Location: Canberra

Re: High Clue Puzzles

Postby dobrichev » Mon Nov 04, 2019 10:26 am

Hi Jim,

You can investigate the {-5,+?} vicinity of the 40-clue puzzles directly using sudoku35plus tool.
A tool that reads sudoku 9x9 subgrids/puzzles with 35 or more givens, converts them to 35-given subgrids by removing the givens in all possible ways, and adds additional givens in all possible ways until single-solution puzzle with no redundant clues is generated.

It will generate a bunch of minimal puzzles of size 36+.

All known 38+ puzzles were passed trough this procedure; from memory all 37s were passed too, and small part of known 36s weren't.

Surely every grid has one or more "cores" capable for producing high-clue puzzles. The gaps are fact and IMHO their classification is close to numerology.

Cheers,
Mladen
dobrichev
2016 Supporter
 
Posts: 1777
Joined: 24 May 2010

Re: High Clue Puzzles

Postby Mathimagics » Mon Nov 04, 2019 11:02 am

Thanks, Mladen!

You have answered one question for me - I actually used Sudoku35plus to get the 37C cases I reported above. I used a post-process filter to pull out just those puzzles that solved to this particular grid.

So what you are basically telling me is that there are no 38/39's within {-5, +n} of those two 40C base puzzles that I used as input?

Hmmm .... :?

Cheers
MM
User avatar
Mathimagics
2017 Supporter
 
Posts: 1481
Joined: 27 May 2015
Location: Canberra

Re: High Clue Puzzles

Postby dobrichev » Mon Nov 04, 2019 11:35 am

I told you that this procedure would find all 35s, 37, 38s, 39s, etc. within {-5, +n} of those 40s.
Use your powerful machine and run them :P

What I forgot to tell is that this procedure has some hardcoded limitations for number of solutions of the subgrids, and can crash in some cases, giving a numerical error that you can decrypt by tracing the source code.
So, more precisely, this procedure will find all the puzzles within {-5, +n} unless it crashes with some numerical error.

I can't remember how many puzzles exist in this vicinity, nor whether the procedure crashes for this particular case.
dobrichev
2016 Supporter
 
Posts: 1777
Joined: 24 May 2010

Re: High Clue Puzzles

Postby Mathimagics » Mon Nov 04, 2019 1:15 pm

dobrichev wrote:I told you that this procedure would find all 35s, 37, 38s, 39s, etc. within {-5, +n} of those 40s.
Use your powerful machine and run them :P


"Jack" is currently booked solid right through to February 2020 (on LCT-19 and LCT-17 completion work) !! :?

"Jill" (my "old" PC, the 4-core i7-7700K) is doing the heavy lifting here.

When you say "run them", do you mean I should keep feeding the puzzles I get from one pass back through Sudok35plus to try and find more?

dobrichev wrote:So, more precisely, this procedure will find all the puzzles within {-5, +n} unless it crashes with some numerical error.

Cute! :lol:
User avatar
Mathimagics
2017 Supporter
 
Posts: 1481
Joined: 27 May 2015
Location: Canberra

Re: High Clue Puzzles

Postby dobrichev » Mon Nov 04, 2019 1:24 pm

Mathimagics wrote:When you say "run them", do you mean I should keep feeding the puzzles I get from one pass back through Sudok35plus to try and find more?

You can do this and reinvent the known puzzles.
At some point the yield will drastically decrease and you will switch to other task. At least I did so.
dobrichev
2016 Supporter
 
Posts: 1777
Joined: 24 May 2010


Return to General