## Structure of the puzzle solution 1 : the Megaclue !

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

### re: MegaClue in 17-clue puzzles

above, Red Ed (2006.Sep.29) wrote:The whole thing completed in about 8 hours.

with over 40,000 17-clue puzzles now,
could we run the MegaClue test
on the new puzzles only?

or would we have to re-run it on the entire set of 17s?
~ Pat

Pat

Posts: 3936
Joined: 18 July 2005

### Re: re: MegaClue in 17-clue puzzles

Pat wrote:could we run the MegaClue test
on the new puzzles only?

Do you mean the counts of "numbers of solutions of the puzzles with one clue deleted"?

For all of the 17-clue puzzles, I've calculated the numbers of solutions of each of the 17 puzzles obtained by deleting one clue in turn, and incorporated them into my database.

So if this is what you mean, then I can easily calculate any particular statistic you would like from these figures...

I have not yet put a proper front end on so that these stats are accessible easily, but here are some examples..

Examples:

Most mega of clues: Clue # 3 from Puzzle #15586 leading to 11339281 solutions

[Clue #3 means the third clue in the MIN LEX version of puzzle #15586, not the downloadable "sudoku17" file]

[NOTE: At the moment the only way you can easily pull this out of the DB is to get the PDF from http://people.csse.uwa.edu.au/gordon/sudoku17pdf.php?id=15586 which is not really suitable for programmers]

Least mega of clues: 2 solutions obtained in lots of ways

We can play lots of min-max games

(1) Max max megaclue: which puzzles have overall maximum solutions among their 17 1-clue deletions

Code: Select all
+-------+----------+
| id    | maxmax   |
+-------+----------+
| 15586 | 11339281 |
| 21355 | 10789663 |
| 33611 |  9370174 |
| 33864 |  9239041 |
| 33920 |  8587343 |
|  8104 |  8159472 |
| 32773 |  8159472 |
| 39852 |  7856752 |
| 15578 |  7547833 |
| 19861 |  7487776 |
+-------+----------+

(2) Min max megaclue: Which puzzles have the minimum value of the maximum solutions over all 17 1-clue deletions

Code: Select all
+-------+--------+
| id    | minmax |
+-------+--------+
| 20515 |   8503 |
| 28773 |  14437 |
| 22111 |  15656 |
| 22731 |  16741 |
| 31403 |  17171 |
| 10832 |  18938 |
| 22734 |  19005 |
| 17025 |  19155 |
|  1158 |  19450 |
| 32506 |  20040 |
+-------+--------+

(In other words, 1-clue deletions of puzzle #20515 have AT MOST 8503 solutions, no matter which clue you remove)

(3) Max min megaclue : which puzzles have the maximum value of the minimum number of solutions over all 17 1-clue deletions

Code: Select all
+-------+--------+
| id    | maxmin |
+-------+--------+
|  3673 |  81469 |
| 12919 |  43983 |
| 20858 |  37293 |
| 33503 |  31584 |
| 36412 |  29545 |
| 29019 |  25522 |
|  3832 |  25248 |
| 14078 |  23961 |
| 28992 |  21953 |
| 29018 |  21586 |
+-------+--------+

In other words, 1-clue deletions of puzzle #3673 have AT LEAST 81469 solutions no matter which clue is deleted..

Can do averages, standard deviations etc etc, but not now - I'm off to bed.

Cheers

Gordon
gfroyle

Posts: 214
Joined: 21 June 2005

### re(2): MegaClue in 17-clue puzzles

Pat

Posts: 3936
Joined: 18 July 2005

ronk wrote:If one removes a single clue from a minimal 9x9 sudoku, the minimum number of solutions is 2 ... but what is the maximum?.......

We seem to have this sorted for the 17 clues.....how about for a minimal 25 clue puzzle ?

Redirected from another thread here is my initial offering
Code: Select all
+---+---+---+
|.2.|...|...|
|...|...|.6.|
|687|..9|.34|
+---+---+---+
|..3|9..|621|
|.7.|..2|...|
|...|5.8|..7|
+---+---+---+
|..2|.1.|..3|
|...|..3|8..|
|.4.|...|..6|
+---+---+---+  omitting the 1 at r7c5 gives 6040 grid solutions

Can anyone do better...?

C
coloin

Posts: 2182
Joined: 05 May 2005
Location: Tenerife

quick search : 25 clues minimal
Code: Select all
*-----------*
|.2.|...|...|
|...|...|.6.|
|6.7|..9|.34|
|---+---+---|
|..3|9..|621|
|.7.|..2|...|
|...|5.8|..7|
|---+---+---|
|..2|.1.|..3|
|...|..3|8..|
|.48|...|..6|
*-----------*   omitting the 1 at r7c5 gives 10855 solutions

but one can do much better.
Why 25 clues ?

JPF
JPF
2017 Supporter

Posts: 5920
Joined: 06 December 2005
Location: Paris, France

still 25 clues, minimal :
Code: Select all
*-----------*
|.2.|...|...|
|.3.|...|.6.|
|687|..9|.34|
|---+---+---|
|8..|9..|62.|
|.7.|..2|...|
|...|5.8|..7|
|---+---+---|
|..2|.1.|..3|
|...|..3|8..|
|.4.|...|..6|
*-----------*    omitting the 1 at r7c5 gives 12845 solutions.

JPF
JPF
2017 Supporter

Posts: 5920
Joined: 06 December 2005
Location: Paris, France

JPF wrote:why 25 clues ?

It was in response to mauricio's post here
C
coloin

Posts: 2182
Joined: 05 May 2005
Location: Tenerife

My attempt was made on a random selection of puzzles.....but I can see how you improved it.

I have made similar changes to mauricio's puzzle.....which shows we do have much furthur to go.

I was going to leave it for a bit, but I couldnt resist the latest "nice trick"
Here is the complete 25 clue minimal puzzle
Code: Select all
+---+---+---+
|.3.|...|...|
|...|..3|.4.|
|.24|..5|37.|
+---+---+---+
|...|..2|7..|
|.18|..7|.6.|
|...|1.6|.5.|
+---+---+---+
|.6.|...|487|
|.8.|...|.3.|
|1..|9..|...|
+---+---+---+
Highlight the area below to read the spoiler I wrote: omitting the 9 @r9c4 gives 114528 grid solutions

C
coloin

Posts: 2182
Joined: 05 May 2005
Location: Tenerife

coloin wrote:My attempt was made on a random selection of puzzles.....but I can see how you improved it.

these options to my solver will stream through a collection of puzzles and list puzzles with
megaclue count > the previous listed puzzle
Code: Select all
-qFN -f'%v # %(required(max))x' -e 'max(required(max))'
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Code: Select all
*-----------*
|.3.|...|...|
|...|..3|.4.|
|.24|..5|37.|
|---+---+---|
|...|..2|7..|
|.18|..7|.6.|
|...|1.6|.5.|
|---+---+---|
|.6.|..1|4.7|
|.8.|...|.3.|
|1..|9..|...|
*-----------*  omitting the 9 @r9c4 gives 138142 grid solutions

etc...

JPF
JPF
2017 Supporter

Posts: 5920
Joined: 06 December 2005
Location: Paris, France

We are obviously using the same technique !
Code: Select all
155323      .3............3.4..24..537......27...18..7.6....1.6.5..6......7.8....43.14.......
145563      .3............3.4..24..537......27...18..7.6....1.6.5..6...1..7.8.....3.14.......
138142      .3............3.4..24..537......27...18..7.6....1.6.5..6...14.7.8.....3.1........
131767      ...........1..3.4..24..537......27...18..7.6....1.6.5..6....48778.....3..........
127763      .3............3.4..24..537......27...18..7.6....1.6.5..6......7.8....13.14.......

I wonder if this furthurs the max clues exercise....

C
coloin

Posts: 2182
Joined: 05 May 2005
Location: Tenerife

I wonder if those 24 clue puzzles can be part of a high clue sudoku (>36). I think that due to the fact that it all started with this sudoku
Code: Select all
Ravel's 38 -14 clues +1 clue. Minimal.
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . 3 | . 4 . |
| . 2 4 | . . 5 | 3 7 . |
+-------+-------+-------+
| . . . | . . 2 | 7 . . |
| . 1 8 | . . 7 | . 6 . |
| 2 . . | 1 . 6 | . 5 . |
+-------+-------+-------+
| . 6 . | . . . | 4 8 . |
| . 8 . | . . . | . 3 . |
| 1 . . | 9 . . | . . 6 |
+-------+-------+-------+
25 clue minimal puzzle - 9 @ r9c4 = 32213 grid solutions

In the remaining 24 clue subpuzzle, you can add 14 clues minimally. Can this be possible too with the given subpuzzles?
Mauricio

Posts: 1174
Joined: 22 March 2006

Mauricio wrote:In the remaining 24 clue subpuzzle, you can add 14 clues minimally. Can this be possible too with the given subpuzzles?

A -1/+14? I would not get my hopes up. Even though you can bail out any time the puzzle reaches a solution before all 14 are added, I think the searchspace would be far to big.

Havard
Havard

Posts: 378
Joined: 25 December 2005

Havard wrote:the search space would be far to big

I initially was of this opinon

Except......
The search options are reduced by
Never insert a 9 clue
Never insert more than 6 of any of the other clues [1-8]

Having said that I cant make a single minimal puzzle from any of these subpuzzles, so I think its not going to work.

Minimality is [as usual] the difficult issue and therefore all the clues need to have high solution counts, these individual counts all progressivly reducing with each additional clue.

C
coloin

Posts: 2182
Joined: 05 May 2005
Location: Tenerife

Havard wrote:I think the searchspace would be far to big.

I think that too, I was just thinking that it could be possible that those subpuzzles may be part of a larger minimal puzzle. Obviously trying to actually find those puzzles exhaustively is not an optimal way to find minimal puzzles with high number of clues.

In the meantime I started with this subpuzzle coloin posted:
Code: Select all
. 3 .|. . .|. . .
. . .|. . 3|. 4 .
. 2 4|. . 5|3 7 .
-----+-----+-----
. . .|. . 2|7 . .
. 1 8|. . 7|. 6 .
. . .|1 . 6|. 5 .
-----+-----+-----
. 6 .|. . .|. . 7
. 8 .|. . .|4 3 .
1 4 .|. . .|. . .
coloin says it has 155323 grid solutions, I have not checked that fact. 24 clues

Doing a nested 1off/2on I arrived to:
Code: Select all
Minimal, coloin subpuzzle + 10 clues. 34 clues.
. 3 .|4 . .|5 . .
. . 1|. 7 3|. 4 .
. 2 4|. 1 5|3 7 .
-----+-----+-----
. . .|. 8 2|7 . .
. 1 8|. . 7|. 6 .
2 . .|1 . 6|. 5 .
-----+-----+-----
. 6 5|. . .|. . 7
. 8 2|. . .|4 3 .
1 4 .|. . .|6 . .

My resources to do that were not optimal, and I think more clues are possible.

Addendum: I found this, but I am stuck at 35 clues at the moment
Code: Select all
. 3 .|. . .|5 . .
. . .|2 . 3|. 4 .
. 2 4|. . 5|3 7 .
-----+-----+-----
. . .|3 8 2|7 . .
. 1 8|. 5 7|2 6 .
. . .|1 . 6|. 5 .
-----+-----+-----
. 6 .|. . .|1 . 7
. 8 7|6 . .|4 3 .
1 4 .|. . .|6 2 .
Mauricio

Posts: 1174
Joined: 22 March 2006

PreviousNext