## Grid not containing a 16

Everything about Sudoku that doesn't fit in one of the other sections
Thanks for proving that - it was a good bit simpler than the SF im sure.

So a tendancy to the canonical grid gives a low solution rate. The different row/different column spacing for the "3" numbers in an individual box induces 4 set pairings for the 6 other numbers - which make a low clue puzzle impossible [but the advantage albeit small is that it makes unavoidable sets between the "3" numbers in the box impossible].

There has to be a happy medium between these two extremes.
C
coloin

Posts: 1738
Joined: 05 May 2005

For the record, two more grids that do not have a 16:

639241785284765193517983624123857946796432851458619237342178569861594372975326418
873692451649517328521348976132976845498125637765483192954761283386254719217839564

The first is known as the SF (strangely familiar) grid.
Moschopulus

Posts: 256
Joined: 16 July 2005

Another grid that does not contain a 16 is the solution grid to this puzzle
Code: Select all
` 6 . . | . 4 . | . . 3 . 1 . | . . . | . 7 . . . 5 | . . . | 8 . .-------+-------+------ . . . | 5 . 2 | . . . 3 . . | . 9 . | . . 2 . . . | 1 . 3 | . . .-------+-------+------ . . 8 | . . . | 9 . . . 7 . | . . . | . 5 . 2 . . | . 3 . | . . 4  `
Moschopulus

Posts: 256
Joined: 16 July 2005

### But does it have an 18 ?

Moschopulus wrote:Here is a grid which does not contain a puzzle with 16 clues:

937856241
562194387
481273569
823647915
615932478
749581623
378469152
196725834
254318796

How do I know? By a computer calculation.

I thought I would refer to this grid as it is relevant to recent postings.

This is the grid [refered to as the miracle grid] with 15 disjoint unavoidable sets which as you have shown not to have a 16.

You have recently given details http://forum.enjoysudoku.com/viewtopic.php?t=2419&start=0&postdays=0&postorder=asc&highlight=of this program available at http://www.maths.nuim.ie/staff/gmg/sudoku and also an excellent links to other programs http://magictour.free.fr/sudoku.htm

This grid surprised us in having many [180] solutions with 19 clues. http://www.csse.uwa.edu.au/~gordon/sudokupat.php?cn=6

These solutions do not have many clues in common and they may indeed be from separate regions of the grid.

Have you checkered this to show that an 18 is not possible in this grid ........ or will that take too long ?

Regards
coloin

Posts: 1738
Joined: 05 May 2005

I just checked MG for a 17, it doesn't have one, as expected. Using the program CHECKER it took about 3 hours.

I started the search for an 18, it looks like that will take a few days.
You can do it yourself of course - just download checker from http://www.maths.nuim.ie/staff/gmg/sudoku and type
"checker filename 18"
where the grid is in filename.

You can use the option -firstclue to divide up the computation into pieces.

The program UNAVOID will find unavoidable sets, and the MCN. Ask me if you have any questions.
Moschopulus

Posts: 256
Joined: 16 July 2005

I thought it would take some time.......but I wasnt quite sure whether to use the checker 64/128 etc.

I hadnt realized there were quite so many 19s [180] in this grid - that would explain the lower than expected "suexsf" number. It also perhaps has skewed my estimate of "almost every clue having an 18"

I cant really understand how it can have so many 19s but no 18..........one would have thought it would be easily found by Gordon's program - if it was there.

I await your result.....it may be tucked away somewhere else in the grid.

Is it my imagination or are there less unavoidables in high MCN grids ?

An mcn 16 might be an interesting grid.

C
coloin

Posts: 1738
Joined: 05 May 2005

coloin wrote:I thought it would take some time.......but I wasnt quite sure whether to use the checker 64/128 etc.

You have to experiment. The running times vary and I don't know why. It's a mystery. But the difference is not great sometimes. Just try one of them.
Is it my imagination or are there less unavoidables in high MCN grids ?

A high MCN grid seems to have more small ones, and less in total. dukuso was saying this before.
An mcn 16 might be an interesting grid.

Yes, very. That's the next question. Is there a grid with MCN = 16?

I ran through over 13,000 random grids here
http://forum.enjoysudoku.com/viewtopic.php?t=605&start=315
and listed the MCNs. There were 7 with MCN = 15.
Moschopulus

Posts: 256
Joined: 16 July 2005

coloin wrote: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.
Wolfgang

Posts: 208
Joined: 22 June 2005

I see....It is bizarre terraine ! .......especially as we thought the highlands should be lowlands [in the MC grid].

incidence of MCNs = 15 is 7 in 13000

interestingly of the 16 solutions to
Code: Select all
`+---+---+---+|145|927|638||627|385|149||893|641|..2|+---+---+---+|..2|1..|3..||3.8|..2|..1||.1.|.3.|.2.|+---+---+---+|..1|29.|..3||2..|..3|.1.||.3.|.1.|29.|+---+---+---+`

Code: Select all
`145927638627385149893641572452179386378462951916538427581294763269753814734816295145927638627385149893641572472169385358472961916538724761294853289753416534816297145927638627385149893641572952176384378452961416839725761294853289563417534718296145927638627385149893641572952178364378462951416539827561294783289753416734816295145927638627385149893641572972156384358472961416839725761294853289563417534718296145927638627385149893641572972156384368472951514839726751294863289563417436718295145927638627385149893641572972156384368472951514839726751294863289763415436518297145927638627385149893641572972168354358472961416539827561294783289753416734816295145927638627385149893641752452169387378452961916738524561294873289573416734816295145927638627385149893641752472159386358462971916738425781294563269573814534816297145927638627385149893641752952168374378452961416739825761294583289573416534816297145927638627385149893641752952176384368452971714839526571294863289563417436718295145927638627385149893641752952176384368452971714839526571294863289763415436518297145927638627385149893641752952176384378452961416839527561294873289763415734518296145927638627385149893641752972156384358472961416839527561294873289763415734518296145927638627385149893641752972158364358462971416739825761294583289573416534816297`

the MCNs are
Code: Select all
`12, 13, 15, 13, 15, 15, 15, 13, 12, 12, 13, 15, 15, 15, 15, 13`
coloin

Posts: 1738
Joined: 05 May 2005

### Re: But does it have an 18 ?

Interesting, all those 15s.

coloin wrote:
937856241
562194387
481273569
823647915
615932478
749581623
378469152
196725834
254318796

...
This grid surprised us in having many [180] solutions with 19 clues. http://www.csse.uwa.edu.au/~gordon/sudokupat.php?cn=6
...

I have shown (using checker64) that this grid does not have a 16 or a 17 or an 18.

The computation for an 18 took about 23 hours.

gfroyle found 19s, at the above link (grid called Moschopulus 1)
Moschopulus

Posts: 256
Joined: 16 July 2005

### Re: But does it have an 18 ?

Moschopulus wrote:The computation for an 18 took about 23 hours.

Great, i had searched the grid 2 days (finding about as much 19's as gfroyle) and only could say that an 18 is unprobable. i wonder, if you could make an exhaustive search over 17-clue patterns in reasonable time also.
Wolfgang

Posts: 208
Joined: 22 June 2005

### Re: But does it have an 18 ?

Wolfgang wrote:Great, i had searched the grid 2 days (finding about as much 19's as gfroyle) and only could say that an 18 is unprobable. i wonder, if you could make an exhaustive search over 17-clue patterns in reasonable time also.

I'm not sure what you mean. Do you mean a pattern for the clues (the positions of the clues in the grid) ? In one grid?

checker searches exhaustively in a given grid for a puzzle with N clues. You input the grid and N.
Moschopulus

Posts: 256
Joined: 16 July 2005

### Re: But does it have an 18 ?

Moschopulus wrote:I'm not sure what you mean. Do you mean a pattern for the clues (the positions of the clues in the grid) ? In one grid?

Yes/no. I meant, what gfroyle started with an 18-clue pattern (without a chance to finish it), when he came to the conclusion that he had at most 1% of the 18-clues. But i fear that such an exhaustive search is a big lot more time consuming than an exhaustive grid search.
Wolfgang

Posts: 208
Joined: 22 June 2005

Previous