The New Sudoku Players' Forum

[coloin]

Of course .....I mean " where are the others ?"

They are bigger than size 14 - the size limit was arbitrarily introduced, to reduce numbers. All unavoidables need "hitting" by a clue , and I suppose the larger the unavoidable the more likely it is to be "hit" by a clue.

In running "checker" program it was important to get the small unavoidables sorted completly and then worry about the large ones using a solver program.

Of course they are important in this grid....and we will find them !

unav27 and unav35 [and unav45] from dukuso have been around for a while........though I dare say not all unavoidables up to the stated size are found with these programs.

C

[ronk]

unav27 and unav35 [and unav45] from dukuso have been around for a while ...

unav45 is not on Guenter Stertenbrink's Sudoku page. Do you have a source?

I didn't know dukuso and Guenter Stertenbrink were one and the same.

TIA, Ron

[Red Ed]

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

Just 24 minimal unavoidables, you reckon? Ho ho ho ...

There are actually 82543. Here's the output from my code:

Code: Select all

Number of minimal unavoidables: 82543
    3 of size 12
    0 of size 13
    2 of size 14
    0 of size 15
    7 of size 16
    7 of size 17
    6 of size 18
    5 of size 19
   13 of size 20
   18 of size 21
   27 of size 22
   38 of size 23
   45 of size 24
   80 of size 25
  102 of size 26
  158 of size 27
  221 of size 28
  252 of size 29
  398 of size 30
  626 of size 31
  832 of size 32
 1094 of size 33
 1462 of size 34
 2076 of size 35
 2648 of size 36
 3231 of size 37
 4127 of size 38
 5022 of size 39
 5851 of size 40
 6527 of size 41
 7064 of size 42
 7532 of size 43
 7494 of size 44
 7060 of size 45
 6120 of size 46
 4925 of size 47
 3375 of size 48
 2235 of size 49
 1132 of size 50
  498 of size 51
  177 of size 52
   41 of size 53
   11 of size 54
    1 of size 55

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

The biggest minimal unavoidables:
  55 2 {11,13,15,16,18,19,21,22,24,26,27,29,31,32,33,34,35,36,37,38,43,44,46,49,52,53,54,55,56,58,61
,64,65,67,68,69,72,75,76,77,79,81,82,83,84,85,88,89,91,92,93,95,96,98,99}

The highest valency minimal unavoidables:
  46 6 {13,15,16,17,18,19,21,22,23,24,29,32,33,34,35,36,37,38,43,44,46,48,49,52,53,55,56,61,62,63,65
,66,67,68,72,75,76,77,81,83,84,85,88,89,91,98}

Positions of the clues (% of all min unavs):
  41.6   --   53.5   --   45.3  73.6  48.8  47.1  41.2
  53.5  43.4  75.3  70.1   --   76.0  62.0   --   77.6
  54.1  74.2  90.9  61.0  61.3  66.2  56.1  95.3   --
   --   58.7  49.6  57.3   --   80.3   --   67.5  50.0
   --   57.0  72.5  63.6  63.0  64.1   --   44.2   --
  68.7  53.1  81.2  57.6  73.4  58.2  95.1  51.0  70.7
   --   95.1   --   54.4  72.8  64.0  99.6   --   60.2
  72.5  63.2  63.2 100.0  57.8  49.5   --   95.1  59.9
  47.9  56.8  57.2   --   62.3  66.2  45.3  85.4  56.4

The "valency" is the number of ways of laying down clues that have the same row, column and box memberships as the given minimal unavoidable. Most minimal unavoidables have valency 2. Until today, I'd never seen anything with valency >5. (Nor, for that matter, had I ever seen a minimal unavoidable with as many as 55 clues.)

[ronk]

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

Just 24 minimal unavoidables, you reckon? Ho ho ho ...

There are actually 82543. Here's the output from my code:[code]Number of minimal unavoidables: 82543

Good show! How many of those unavoidables have clue 84 and none of the other 16 clues?

[Ocean]

Just 24 minimal unavoidables, you reckon? Ho ho ho ...

There are actually 82543. Here's the output from my code:

Great! Good job.

I could only tell for sure there would be at least 24. Figured there were some extras, but had no idea how many.

Good show! How many of those unavoidables have clue 84 and none of the other 16 clues?

All of them (82543), I presume - (I only checked the largest - which is a minimal 2-permutable set of size 55).

[Red Ed]

Good show! How many of those unavoidables have clue 84 and none of the other 16 clues?

All of them (82543), I presume

Yes, that's what the "Positions of the clues" table was all about. If you stick an extra clue in r8c4 then you kill 100.0% of the minimal unavoidables, thus solving the puzzle. Put it in r7r7 instead and you kill 99.6% of the minimal unavoidables, leaving you with 3200 solutions. At r1c9, killing only 41.2% of minimal unavoidables leaves you with over 6 million solutions.

[ronk]

Good show! How many of those unavoidables have clue 84 and none of the other 16 clues?

All of them (82543), I presume

Yes, that's what the "Positions of the clues" table was all about.

I noted the 100% in the table for clue 84, but wasn't sure if the table was based on all 82543 minimal unavoidables or a subset.

To be clear then ... it appears you're using minimal unavoidables to mean the set of all possible unavoidables of a solution grid filtered to remove the effect of fixing a clue set. Correct?

[Red Ed]

No, not correct. An unavoidable U is a subset of the (cell,value) pairs of a grid G such that the other (cell,value) pairs, G\U, define a puzzle with multiple solutions. I used "valency" above to mean the number of solutions. A minimal unavoidable is an unavoidable that does not contain any other unavoidables.

The stats I gave above are for those minimal unavoidables that do not include any of the 16 (cell,value) pairs from the 11339281-solution grid (so, yes, they are filtered).

[RW]

Very interesting stats on the unavoidables. I'd never thought that minimal unavoidables could be that large. Your results also show that the average size for minimal unavoidables in that region is >40. Has there been any research done on this, is this the average size for whole grids also? With 16 clues fixed, you only had 65 clues to work with, and if there's a 55 in them, then there could be even larger minimal unavoidables in full grids...

Looking forward to the final results on the Megaclue issue!

RW

[ronk]

A minimal unavoidable is an unavoidable that does not contain any other unavoidables.

Thanks. I was thinking an unavoidable set was minimal by definition.

[ronk]

Given a 9x9 sudoku with 2 solutions, the ambiguity involves the minimum of 2 digits and 4 cells of the well-know unique rectangle.

But what are the maximums? And do both maximums occur in the same puzzle?

[Ocean]

Given a 9x9 sudoku with 2 solutions, the ambiguity involves the minimum of 2 digits and 4 cells of the well-know unique rectangle.

But what are the maximums? And do both maximums occur in the same puzzle?

Not sure if I understand your question - since the current example is most likely the highest known. Here is the "ambiguity that involves 9 digits and 55 cells":

Code: Select all

Pseudo-puzzle and its two solutions:
 *-----------*
 |.1.|5..|2..|
 |..3|.7.|.8.|
 |...|...|..9|
 |---+---+---|
 |75.|.2.|46.|
 |2..|...|5.1|
 |.46|..5|...|
 |---+---+---|
 |6.2|3..|.4.|
 |...|..2|3..|
 |...|9..|8..|
 *-----------*
817596234923471685465283719751829463289634571346715928692358147578142396134967852
914568273563279184827431659759123468238746591146895732682317945495682317371954826


Finding the maximum possible unavoidable set is a problem of combinatorics.
For possible examples with higher numbers, running through the 18s might be prospective - since there are many more known 18s than 17s (three orders of magnitude).
or:

With 16 clues fixed, you only had 65 clues to work with, and if there's a 55 in them, then there could be even larger minimal unavoidables in full grids...

.. alternatively start searching all known grids. Don't know which is the better strategy. Of course, after having searched all grids we also know the theoretical maximum - without use of combinatorics, but at the cost of long waiting....
#
What is the relation between the two solution grids? Does the second solution grid also have a 17? What is the lowest number of clues for a sudoku in the second grid?

[ronk]

Not sure if I understand your question - since the current example is most likely the highest known. Here is the "ambiguity that involves 9 digits and 55 cells":

Code: Select all

Pseudo-puzzle and its two solutions:
 *-----------*
 |.1.|5..|2..|
 |..3|.7.|.8.|
 |...|...|..9|
 |---+---+---|
 |75.|.2.|46.|
 |2..|...|5.1|
 |.46|..5|...|
 |---+---+---|
 |6.2|3..|.4.|
 |...|..2|3..|
 |...|9..|8..|
 *-----------*
817596234923471685465283719751829463289634571346715928692358147578142396134967852
914568273563279184827431659759123468238746591146895732682317945495682317371954826


You understood correctly ... and I should have been able to figure that out on my own.

[gsf]

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.

[ back from a disconnected weekend ]
this is what we had originally estimated ~5-6 days to complete?
how did you reformulate the problem to get it done ~18x faster?

[coloin]

Amazing.... Red Ed certainly did find all the unavoidable sets....

The number of grid solutions from the 16 clues subgrid [without the megaclue] was related to :
to the number of unavoidables ..[not sure if size really matters !]
the iterations or "valancy" of the unavoidable [valancy a better word]

The large unavoidable that was found might well be bettered in some of the lesser megaclues, but I doubt if there is an 18 clue puzzle with as large a megaclue in terms of grid solutions - but though there are significantly more to pick from [millions].

There may well be other unavoidable sets larger than this picked from a random set of 16 clues with more grid solutions....if Red Ed thinks this is worthwhile. Personally the large unavoidable with our best megaclue is good enough.

Suffice to say I regret that it is not proving useful finding clues [max] Though I am working on it.

Code: Select all

+---+---+---+
|..7|.9.|23.|
|.23|...|..5|
|46.|2..|71.|
+---+---+---+
|...|8.9|...|
|.8.|6.4|.7.|
|...|.1.|...|
+---+---+---+
|.9.|..8|1.7|
|.78|.42|.9.|
|.3.|.6.|85.|
+---+---+---+ a 32 clue puzzle without using any of the 17 clues

It is a relevant point that that any unavoidable set of 47 and above clues will automatically be covered by any combination of 35 clues.

As an exercise though it certainly pushed out the extremes of our knowledge.

I dont think dukuso thought the unav45 program of much use...it was slow and the data output was large. For that reason I cant find a copy of it in my archive. Sorry

Could we have the top five megaclues please.....maybe there are more, smaller unavoidables in these ?

C