The New Sudoku Players' Forum

[coloin]

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..........1

store this in "adirectory" as file.txt

type c:\adirectory>suexk <file.txt> s9999999999 v99999999999
and the number of solutions is caluculated in around 10 seconds

C

[JPF]

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

[Smythe Dakota]

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

[Red Ed]

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.

[tarek]

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

[gsf]

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

[coloin]

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

> 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]

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.

[Red Ed]

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!

[JPF]

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.

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

[gsf]

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

[Red Ed]

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.

[Ocean]

• 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.

• 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.

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]

[coloin]

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

more questions......

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 ?

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

[ronk]

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?

[edit: the following added]

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.