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

Postby Pat » Tue May 29, 2007 11:15 am

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
User avatar
Pat
 
Posts: 3424
Joined: 18 July 2005

Re: re: MegaClue in 17-clue puzzles

Postby gfroyle » Tue May 29, 2007 1:57 pm

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

Postby Pat » Tue Jun 05, 2007 11:24 am

User avatar
Pat
 
Posts: 3424
Joined: 18 July 2005

Postby coloin » Wed Aug 01, 2007 12:11 am

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: 1632
Joined: 05 May 2005

Postby JPF » Wed Aug 01, 2007 1:34 am

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby JPF » Wed Aug 01, 2007 6:55 am

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Wed Aug 01, 2007 7:16 am

JPF wrote:why 25 clues ?

It was in response to mauricio's post here
Which is some way ahead.
C
coloin
 
Posts: 1632
Joined: 05 May 2005

Postby coloin » Wed Aug 01, 2007 7:10 pm

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: 1632
Joined: 05 May 2005

Postby gsf » Wed Aug 01, 2007 7:49 pm

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

Postby JPF » Wed Aug 01, 2007 11:07 pm

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: 3752
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Wed Aug 01, 2007 11:41 pm

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: 1632
Joined: 05 May 2005

Postby Mauricio » Thu Aug 02, 2007 1:01 am

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

Postby Havard » Thu Aug 02, 2007 9:57 am

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: 377
Joined: 25 December 2005

Postby coloin » Thu Aug 02, 2007 10:21 am

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: 1632
Joined: 05 May 2005

Postby Mauricio » Thu Aug 02, 2007 7:45 pm

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

Return to General