The New Sudoku Players' Forum

[Mathimagics]

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!

[dobrichev]

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

[Mathimagics]

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

[dobrichev]

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

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.

[Mathimagics]

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

"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?

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

Cute!

[dobrichev]

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.