The New Sudoku Players' Forum

[Moschopulus]

This grid

145726983
837495261
926381574
293874156
581269347
674153892
318547629
459632718
762918435

does not have a puzzle with 19 clues, but has the following 20 clue puzzle:

000020000037000060900001070003800006001000000000050090000007000000032008060000405

[Wolfgang]

Fine to know now that there are grids without 19-clue. So not the canonical grid is the "worst".

[coloin]

Well done. This is one of the grids with MCN 16. [0 0 0 0 0 5 92 24.875500 / 10000]


But I think the other grid [MCN15] with all 4 sets will be a harder nut to do in 20 ! Even though it only has 78 unavoidables. The "suexsf" got nowhere with it. [0 0 0 0 0 1 100 24.858601 / 10000]

Code: Select all

MCN - 15  [all clues in a 4 set]
123568479
864791352
957243681
218657934
536489127
749312865
391825746
472136598
685974213


No !
In the time taken to type .......checker64 found a 20 ! [A 19 awaited]

Code: Select all

+---+---+---+
|1..|56.|4..|
|8..|7..|..2|
|...|...|.8.|
+---+---+---+
|...|...|..4|
|...|4..|1..|
|7.9|3..|...|
+---+---+---+
|.9.|...|...|
|..2|...|5..|
|6..|.7.|.1.|
+---+---+---+



...This topic also begs the question as to how many grids need 19 or 20 clues ? Especially as I claimed that most would be solvable in 18........of course this was based on the plethora of 19s in the Mosch 1 grid. [ 0 0 0 0 1 20 273 24.480101 / 10000 ]


I think that what this tells us as that probably the fact that some grids can be solved in significantly less clues is related to a chance occurance of the combination of a minimal hitting set of clues. The spread of MCNs in all of Gordon's 17s would support this. A low MCN is a slight advantage .......but a high MCN, whilst obviously making it harder, gives a lower total count of unvoidables.

Regards

[Moschopulus]

...This topic also begs the question as to how many grids need 19 or 20 clues ? Especially as I claimed that most would be solvable in 18........of course this was based on the plethora of 19s in the Mosch 1 grid.

I'm afraid you won't convince anyone (me anyway) of a general conjecture based on the evidence of just ONE grid. If you were to select a reasonable number of grids at random, say 1000 or 10000, and if a high percentage of them had an 18, then I might be convinced. Have you (or anyone) done this?

[coloin]

I totally agree.......

At the time ....it was based on a lowly 3 grids......and the fact that the highest possible MCN we had in a grid was 15. Gordon was also wondering where all the 18s he was finding were coming from.

Subsequently we have many grids which have mcns of 15 and some at 16. These are significantly harder to reduce to 19 clues than the miraculous Mosch1 which had 180 19s.

My methods of reducing a grid to 18 are not automated [suexsf and suexmult]
http://magictour.free.fr/sudoku.htm
but I am willing to have a go at a few grids. Your checker program is good for the high mcn grids.

Can I post a random selection and we can throw it open to all [how many?] that are interested !

Regards

[coloin]

OK
In an effort to work out the distribution of minimal puzzles

For starters here is a random grid
[No 1] [MCN is 10] [ Suexsf Value 0 0 0 0 0 31 356 24.349300 ]

Code: Select all

+---+---+---+
|123|749|568|
|456|183|927|
|789|625|431|
+---+---+---+
|238|567|149|
|561|498|273|
|947|231|685|
+---+---+---+
|874|952|316|
|615|374|892|
|392|816|754|
+---+---+---+


I could only find 2 19s in this grid. Can anyone find an 18 ?

Code: Select all

...7..5..4....39...8...5...2...6..4.....9.2....7.........9.....6.5......3...1...4
...7..56.4.....9...8..25...2......4.....9......7...6.....9.......5.....23...1...4


The next 9 random grids are

Code: Select all

No 2 - 123849567456217839789356124642598713971463285538172946397681452865724391214935678
No 3 - 146328975785196342329457861493561728218973654657284139564839217832715496971642583
No 4 - 347981256582476193169523874896245317754318962213769485925137648478692531631854729
No 5 - 325681974641379258789425613134968725962537841857142396416293587273854169598716432
No 6 - 416235987275689431983147625391728546847516392562394718159873264624951873738462159
No 7 - 856923714731456298492817356348291675925764183167385429273548961684179532519632847
No 8 - 861953274395274618427681593249817356136425789578396421612749835753168942984532167
No 9 - 318924576596173824274586319785631942143259687962847153431768295659412738827395461
No 10- 241589763675143982839267514467832159593614278182975346718326495926451837354798621


Code: Select all

               MCN         Suexsf value
                           171819202122 23    Average        Min. No. of clues [Provisional]

No 1            10         0 0 0 0 0 31 356  24.349300               19 x 2   
No 2            12         0 0 0 0 1 15 256  24.465500               .
No 3            10         0 0 0 0 2 48 446  24.278299               19 x 49
No 4            11         0 0 0 0 2 19 353  24.370199               18 x 1
No 5            13         0 0 0 0 0 12 276  24.463100               .
No 6            11         0 0 0 0 0 25 306  24.400400               .
No 7            10         0 0 0 0 0 31 368  24.339399               .
No 8            11         0 0 0 0 2 17 288  24.458700               .
No 9            11         0 0 0 0 0 28 334  24.408001               .
No 10           12         0 0 0 0 0 28 274  24.539101               .



Does anybody know how to do this quickly - so we can get a bigger sample size ?

[coloin]

I have been wrestling with the above random grids and here is an updated analysis.
In some grids it is indeed proving difficult to find a combination of clues which reduce to a satisfactory minimum.

Code: Select all

           MCN        Suexsf value
                      171819202122 23    Average        No.of clues    frequency

No 1        10        0 0 0 0 0 31 356  24.349300       19               2
No 2        12        0 0 0 0 1 15 256  24.465500       19               1
No 3        10        0 0 0 0 2 48 446  24.278299       19               49 !
No 4        11        0 0 0 0 2 19 353  24.370199       18               1
No 5        13        0 0 0 0 0 12 276  24.463100       20               300+ !
No 6        11        0 0 0 0 0 25 306  24.400400       19               3
No 7        10        0 0 0 0 0 31 368  24.339399       20               32
No 8        11        0 0 0 0 2 17 288  24.458700       not yet attempted
No 9        11        0 0 0 0 0 28 334  24.408001       not yet attempted
No 10       12        0 0 0 0 0 28 274  24.539101       not yet attempted


Help with grid 5 would be appreciated. It seems there are a large number of 20 clue solutions - which disquise any? 19 in the grid.
Checker unfortunatly takes a very long time with this grid

For No 5 here is a 20

Code: Select all

...6...7.........8.8..25..3..4..87.5....3...1..7....9..1...3..........6....7..4..


At the present time the thread has an appropriate title!

[Ocean]

Help with grid 5 would be appreciated. It seems there are a large number of 20 clue solutions - which disquise any? 19 in the grid.
Checker unfortunatly takes a very long time with this grid

For No 5 here is a 20

Code: Select all

...6...7.........8.8..25..3..4..87.5....3...1..7....9..1...3..........6....7..4..


At the present time the thread has an appropriate title!

And here is a 19:

Code: Select all

 
...6...7.....7.....8...5..3..4.68...........1..7.4..9..1...3..7...8...6.......4..
 

#

[coloin]

Thanks
Many of my 20s were very much "removed " from that 19........

How did you do that so quickly ?

I dont suppose you can find the 18 in grid 3 ?

Here is a 19 - thats if you need it !

Code: Select all

1....8.......9.....2.....6..9.....2.....7...4....8.1...6......78....54....16.2...


Regards

[Ocean]

Thanks
Many of my 20s were very much "removed " from that 19........
How did you do that so quickly ?

Pure luck. Started a bunch of random searches, and out came 400 20s, plus one 19.

I dont suppose you can find the 18 in grid 3 ?

Seems to be tougher. Found slightly over 500 19s but no 18 so far.
[Update: After boiling some hours, the number of 19s continued to grow, reaching over 1000 19s without finding any 18.]

[coloin]

Thanks again
When we were looking for 18s in the MG grid, we asked the same question.....but this grid should really have an 18.....I await.

I cant really understand how it can have so many 19s but no 18

To compare grids with geographic regions: There are highlands without a very high peak (with many 19's but no 18) and lowlands which only have a few, but very high mountains (a 17). Of course, more 17s will be found in the highland regions.

this would explain why I wasnt finding the minimal puzzles in some of the grids.

Updated list

Code: Select all

           MCN        Suexsf value
                      171819202122 23    Average        No.of clues    frequency

No 1        10        0 0 0 0 0 31 356  24.349300       19               2
No 2        12        0 0 0 0 1 15 256  24.465500       19               1
No 3        10        0 0 0 0 2 48 446  24.278299       19               2000 +   NO 18 confimed by checker
No 4        11        0 0 0 0 2 19 353  24.370199       18               1
No 5        13        0 0 0 0 0 12 276  24.463100       19               2
No 6        11        0 0 0 0 0 25 306  24.400400       19               3
No 7        10        0 0 0 0 0 31 368  24.339399       19               3
No 8        11        0 0 0 0 2 17 288  24.458700       not yet attempted
No 9        11        0 0 0 0 0 28 334  24.408001       not yet attempted
No 10       13        0 0 0 0 0 28 274  24.539101       no 18


In effect what I have shown is that most grids can be can be completed in at least 19 clues.......[we sort of knew this already !]...........I suppose we need to run checker over the grids to confirm there is no 18.

In progress

[Moschopulus]

I cant get checker64 to work on grid 3 however !

It's generally better to use checker256 or checker (which is checker192) for a grid with low MCN. But even then to search exhaustively a grid with MCN 10 for an 18 will take months to complete. You have to hope it finds one early on, if there is one. You can speed things up by only searching through 1% (or any number) of puzzles, if you think there is a high chance of an 18:
checker256 grid.txt 18 1

A grid with MCN 15 will take something like 2 days to search exhaustively for an 18. I just started checking number 5 for an 18 (MCN =13), and the early estimates are of the order of 10 days.

The clique number (MCN) only gives an estimate of the time. I recently checkered an MCN 11 grid for a 17 completely in 6 hours. Then another MCN 11 grid took nearly 3 days. This shows that there are other factors affecting the running time, and I don't understand what they are.

[Wolfgang]

This shows that there are other factors affecting the running time, and I don't understand what they are.

I noticed big differences in the time i needed for solving (especially invalid) sudokus. Maybe this could be a reason.

[Moschopulus]

I noticed big differences in the time i needed for solving (especially invalid) sudokus. Maybe this could be a reason.

I'm glad others have noticed it too. In case anyone is interested, here are the grids. This grid

169583427428176935357492186746238519582619743931754268815327694673941852294865371

has MCN=11 and took about 5-6 hours to search exhaustively for a 17, using checker. None found. This is faster than some grids with MCN=12.

This grid

679213485248957613513846927391568274486732159725194368834625791152379846967481532

also has MCN=11 but took about 10 times longer to search exhaustively for a 17.

If you search both for a 16 you will see a similar difference, but the times are smaller of course. I have no idea why there is such a difference in the running time. Suggestions are very welcome. Source code is there for anyone interested in looking at it. I would also be interested in hearing about other weirdness that has been observed with checker, examples of grids done, anything at all.

[Wolfgang]

Unfortunately i dont have any (time or hardware) resources for testing something time consuming. This is one example of an invalid sudoku, for which my solver needed 1000 times longer than for an average sudoku:

Code: Select all

050000610090000400020500000000006700000000000000100040004000070003000000000025090

The clues are that "lose" that my solver needs an immense amount of backtracking to verify that it has no solution.
If your solver also takes a long time, you maybe should count the valid and invalid sudokus you have to check and look at the average times needed.
I have searched regions with hundreds of such time consuming sudokus.