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

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

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

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? On what unavoidable set ... or entwined unavoidable sets ... is this maximum based?

I suggested the concept of a "Megaclue" and exampled a clue from one of the 17 puzzles in the SF
Code: Select all
`+---+---+---+|...|24.|7..||.8.|...|.9.||.1.|...|...|+---+---+---+|...|8..|..6||7..|...|...||4..|...|2..|+---+---+---+|3..|.7.|...||...|...|..2||...|..6|.18|+---+---+---+  remove the 7 in r7c5+---+---+---+|...|24.|7..||.8.|...|.9.||.1.|...|...|+---+---+---+|...|8..|..6||7..|...|...||4..|...|2..|+---+---+---+|3..|...|...||...|...|..2||...|..6|.18|+---+---+---+      94763 sol.`

This I thought was fairly spectacular untill I removed clues from one of this 17 from one of Groyles collection which was felt to be a little extraordinary [only one 3,7,8 and no 9]

Code: Select all
`+---+---+---+|...|...|13.||...|.8.|..5||42.|...|...|+---+---+---+|6..|...|.2.||..5|.1.|...||...|...|4..|+---+---+---+|.7.|4.2|...||...|6..|2..||...|...|..1|+---+---+---+`

Code: Select all
`+---+---+---+|...|...|13.||...|.8.|..5||42.|...|...|+---+---+---+|6..|...|.2.||..5|...|...||...|...|4..|+---+---+---+|.7.|4.2|...||...|6..|2..||...|...|..1|+---+---+---+   removing the 1 ar r5c5  gives 1197093 sol.   I didnt expect that ! `

So this really is a Megaclue !!!!!

Code: Select all
`If any one else wants to have a bash at the megaclue.........Download the program suexk `
http://magictour.free.fr/suexk.exe
Code: Select all
`and copy to "adirectory"copy a notepad textfile with a string of 81 characters like this one. This is 16 clues from one of Gfroyles 17s. The one with the megaclue.......13.....8...542.......6......2...5............4...7.4.2......6..2..........1store this in "adirectory" as file.txttype c:\adirectory>suexk <file.txt> s9999999999 v99999999999and the number of solutions is caluculated in around 10 seconds`

C
coloin

Posts: 2182
Joined: 05 May 2005
Location: Tenerife

Here's a Zettaclue* :

Code: Select all
` . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .-------+-------+------- . . . | . . . | . . . . . . | . 1 . | . . . . . . | . . . | . . .-------+-------+------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .   741211528002341437440 solutions`

remove 1 in r5c5 :

Code: Select all
` . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .-------+-------+------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .-------+-------+------- . . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . .  6670903752021072936960 solutions`

Zettaclue = 6670903752021072936960 – 741211528002341437440 = 5929792224018731499520 solutions
=5.9297x10^21 sol.

JPF

*Zetta=10^21
JPF
2017 Supporter

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

Um, I think a MegaClue (or any other kind of xxxxxClue) was intended to mean a clue which, if removed from a VALID sudoku (with just one solution), would yield gazillions of solutions.

Bill Smythe
Smythe Dakota

Posts: 564
Joined: 11 February 2006

coloin wrote:
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?...
...
I imagine searching all the 17s would reveal the best.....
I'm sure this is the right tactic and coincidentally was exactly what I started doing last night. I've checked 11% of the known 17s so far and have found a couple of puzzles with a >7 million solution "megaclue". I'll let it run and report the absolute max in a few days.
Red Ed

Posts: 633
Joined: 06 June 2005

You could also establish the mean of soultions gnerated by removing the clues one by one (Remove clue, register number solutions, return the clue, move to the next clue, Remove clue ....) & establishing which puzzle has the highest mean. I suspect that the honours there would go to an UNTOUCHABLE puzzle (JPF).

tarek

tarek

Posts: 3759
Joined: 05 January 2006

Red Ed wrote:I've checked 11% of the known 17s so far and have found a couple of puzzles with a >7 million solution "megaclue". I'll let it run and report the absolute max in a few days.

how long did it take to do the 11%?
a quick estimate looks like it might take me ~10s per puzzle or ~4 days
using a method that counts solutions by identifying each one
gsf
2014 Supporter

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

tarek wrote:suspect that the honours there would go to an UNTOUCHABLE puzzle (JPF).

I think the highest average will be from a grid with a substancial "megaclue".........and a low number of clues
Red Ed wrote:> 7 million sol....
.....that is almost obscene !

However the "number of solutions" is a function of the number /size/iterations of unavoidable sets in the the other solution grids.

The megaclue is a clue which is present in all of the remaining unavoidable sets in the specific solution grid - however many unavoidable sets there are - it solves,completes and defines the grid.

The megaclue is only good because the "other clues" [in combination]arent so good !

Having said that though the "other 16 clues" arnt that bad.....

Three random 16 clue selections had many grid solutions....[not solvable with a megaclue]
Code: Select all
`.2.....76.....5..8..3.4.......8...........6.59...7........3.....1.2.............4      5,526,514 sol.5...........6....9......8......21.9..1...3.......7......3......6.........5...843.     73,718,328 sol.1...........2...4..4...3.........2...7...5...3..6.............18...97.5..6.......     23,253,849 sol.`

C
coloin

Posts: 2182
Joined: 05 May 2005
Location: Tenerife

Whilst waiting for the 7 million dollar clue, I "chanced " upon this platinum specimen.
Code: Select all
`+---+---+---+|1..|...|7.9||.5.|.89|32.||6..|3..|.5.|+---+---+---+|2.1|..5|...||...|89.|.3.||8..|732|5..|+---+---+---+|.1.|2.4|9.5||.74|91.|...||..2|..3|4..|+---+---+---+  34 clues`

Code: Select all
`2,3,4,2,2,2,2,2,3,2,3,2,4,3,2,2,3,2,2,3,2,2,5,2,2,3,3,4,2,2,2,2,2,2 solutions respectively.`
coloin

Posts: 2182
Joined: 05 May 2005
Location: Tenerife

That's a nice twist on the theme, coloin.

The search through the 17s for a megaclue is being done by gsf and myself. gsf's search will complete before mine, it seems, and I think he's collecting extra stats besides just the max grid, so you can look forward to an interesting post from him in a few days. In the mean time, here's a taster of what's out there in seventeenland: try removing r8c4 from this ...
Code: Select all
`.1.|5..|......|.7.|.8....|...|..9---+---+---7..|.2.|4..2..|...|5.1...|...|...---+---+---6.2|...|.4....|1..|3.....|9..|...`
... you get 11339281 solutions!
Red Ed

Posts: 633
Joined: 06 June 2005

Red Ed wrote:try removing r8c4 from this ...
Code: Select all
`.1.|5..|......|.7.|.8....|...|..9---+---+---7..|.2.|4..2..|...|5.1...|...|...---+---+---6.2|...|.4....|1..|3.....|9..|...`
... you get 11339281 solutions!

Interesting...
This puzzle is an Untouchable too.

coloin wrote:
Code: Select all
`+---+---+---+|1..|...|7.9||.5.|.89|32.||6..|3..|.5.|+---+---+---+|2.1|..5|...||...|89.|.3.||8..|732|5..|+---+---+---+|.1.|2.4|9.5||.74|91.|...||..2|..3|4..|+---+---+---+  34 clues`

Code: Select all
`2,3,4,2,2,2,2,2,3,2,3,2,4,3,2,2,3,2,2,3,2,2,5,2,2,3,3,4,2,2,2,2,2,2 solutions respectively.`

Nice.
Almost the opposite of an Untouchable
(27 cells among 34 can be changed)

is there a puzzle in which every cell can be changed (one by one) ?

JPF
JPF
2017 Supporter

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

Red Ed wrote:The search through the 17s for a megaclue is being done by gsf and myself. gsf's search will complete before mine ... you get 11339281 solutions!

not so fast (ha)
my solver just hit this one an hour ago (11339281 confirmed)
so it looks like they may be on a similar pace
gsf
2014 Supporter

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

Right, I removed the stupid bug in my code that makes it go deathly slow whenever there's a 9 in the top left box (don't ask ...) and re-ran it last night. The whole thing completed in about 8 hours.

For a given grid, let s* = (s1,s2,...,s17) be the solution counts obtained from the removal of one clue. In what follows, functions written in lowercase operate on a single s* vector to give a grid score of some sort, whilst functions written in uppercase operate on all 36628 grid scores (of whatever sort) to give an overall score. With that in mind:
• MAX( max(s*) ) = 11339281 as previously reported. (Grid nr 14526)
• MAX( sum(s*) ) = 33891395, for grid nr 19995.
• MAX( min(s*) ) = 43983, for grid nr 12054.
• MIN( max(s*) ) = 8503, for grid nr 19218.
• MIN( sum(s*) ) = 60184, also for grid nr 19218.
• MIN( min(s*) ) = 2, for grids 14312, 19524, 20186, 21644, 30132, 33262, 2427, 10283, 12559, 13891, 16555, 19695, 19869, 24951, 27007, 27995, 28163, 35455.
Fun fun fun.
Red Ed

Posts: 633
Joined: 06 June 2005

Red Ed wrote:
• MAX( max(s*) ) = 11339281 as previously reported. (Grid nr 14526)

Impressively fast result! Here is a challenge: find the 24 (or more) unavoidable sets that lead to this number of solutions.

Red Ed wrote:
• MIN( min(s*) ) = 2, for grids 14312, 19524, 20186, 21644, 30132, 33262, 2427, 10283, 12559, 13891, 16555, 19695, 19869, 24951, 27007, 27995, 28163, 35455.

These are of course the 18 isomorphic 16-clues pseudo-puzzles in the SF-grid.

Pseudo-puzzles Tue Jan 03, 2006 wrote:
Code: Select all
` the isomorph 16-pseudos (with 2 completions), generated from Gordon's list of 17s. 000010004700000020300000000080000200000700030010000000000004801602300000000000000 000607300201000005000000000030000800700020000000010000005000010070800000000300000 000005081604700000000000000000200700080000040010000000000010005200000400700000000 010000070000800002000500000007000410500302000000000000800000005000010000000040200 010070000000003200000000500200005000000300080000000010500000403007810000000000000 030025000000000710060000000000060005700000600100400000400000000050000002000100000 060000052000301000040000000000000100020050000800000000100000800300400000000020040 060000705000401000030000000050070000000000010200000000000050300100000020400300000 060053000000000801020000000000020030800000200100700000030000050700000000000100000 060503000000000201040000000100070000200000400000400030700000000030000050000010000 075600000000000081000300000000500700000040000100000000400010000000080030030000500 200000030000010700030040000000600082000300000041000000800200000000000100000070000 300000206000071000400000000010000080070040000000600400600200000000000010080000000 309000500000071004000000000000500200070090000010000000000004010200900000500000000 300000007000010800400000000000300004050000070010000000207400000000008150000000000 500000700000100000060000000300075000000000081200000000010600000080000020000020500 600500000000000010030000000700000506000081000200000000000600200080020000010000030 800000040300700000000040200010062000000000083040000000020000600700000000000300000  `

[Edit: changed 21 to 24: >log2(11 mill) ... misread 1.1 mill]
Last edited by Ocean on Fri Sep 29, 2006 6:57 am, edited 1 time in total.
Ocean

Posts: 442
Joined: 29 August 2005

Great work....11339281 is seriously "heavy"

more questions......
Ocean wrote:Here is a challenge: find the 21 (or more) unavoidable sets that lead to this number of solutions.

Yes.........add 20 more clues and.....we might have a 36 ! [Hunch tells me this wont work !] - but it might lead us to a "region" where there is a 36 clue minimal ?

EDIT ! I can only find 3 unavoidable sets specific to our megaclue [of size 14 and below] - Where are they ?

JPF wrote:Almost the opposite of an Untouchable(27 cells among 34 can be changed)
is there a puzzle in which every cell can be changed (one by one) ?

Suggest Chameleon clues.........this can occur when the number of solutions is 2 - ie [only] one unavoidable set soley covered by the clue. The new puzzle tends to lose the originality minimality. I imagine it is more complicated than this !

If we got a grid with all "2 solutions" [or 3 ?] clues we might have an answer to the maximum clues question.

C
coloin

Posts: 2182
Joined: 05 May 2005
Location: Tenerife

coloin wrote:I can only find 3 unavoidable sets specific to our megaclue [of size 14 and below] - Where are they ?

Taking output of unavoid.exe and removing all sets covered by the clues -- other than 84 -- leaves the following ...

{16,17,22,24,26,27,32,34,54,56,84,86}
{23,24,26,31,34,36,61,62,84,86,92,93}
{24,26,35,36,55,56,65,66,75,76,84,85}

... but I suspect that's not what you mean by "where are they?"

What is the source of the size 14 limitation?

Combining the output of unavoid.exe and unav36.exe, the unavoidable sets covered by clue 84 only are ...

{16,17,22,24,26,27,32,34,54,56,84,86}
{23,24,26,31,34,36,61,62,84,86,92,93}
{24,26,35,36,55,56,65,66,75,76,84,85}
{42,43,44,46,52,53,54,55,56,61,62,63,64,65,66,82,84,85,91,92,93,96}
{43,44,46,53,54,55,56,61,62,63,64,65,66,74,75,76,82,84,85,91,92,93,96}
{43,44,52,55,56,61,64,65,66,74,75,76,82,83,84,85,91,92,93,96}

11,339,281 solutons! Six uncovered unavoidable sets?

There must be more sets.
Last edited by ronk on Fri Sep 29, 2006 3:26 pm, edited 1 time in total.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Next