Grid not containing a 16

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

Postby coloin » Thu Nov 03, 2005 12:20 am

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: 1727
Joined: 05 May 2005

Postby Moschopulus » Tue Nov 08, 2005 1:50 am

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

Postby Moschopulus » Tue Nov 08, 2005 11:51 pm

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 ?

Postby coloin » Fri Dec 09, 2005 2:54 pm

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: 1727
Joined: 05 May 2005

Postby Moschopulus » Fri Dec 09, 2005 10:31 pm

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

Postby coloin » Sat Dec 10, 2005 1:47 pm

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: 1727
Joined: 05 May 2005

Postby Moschopulus » Sat Dec 10, 2005 7:20 pm

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

Postby Wolfgang » Sat Dec 10, 2005 11:42 pm

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

Postby coloin » Mon Dec 12, 2005 11:17 am

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
145927638627385149893641572452179386378462951916538427581294763269753814734816295
145927638627385149893641572472169385358472961916538724761294853289753416534816297
145927638627385149893641572952176384378452961416839725761294853289563417534718296
145927638627385149893641572952178364378462951416539827561294783289753416734816295
145927638627385149893641572972156384358472961416839725761294853289563417534718296
145927638627385149893641572972156384368472951514839726751294863289563417436718295
145927638627385149893641572972156384368472951514839726751294863289763415436518297
145927638627385149893641572972168354358472961416539827561294783289753416734816295
145927638627385149893641752452169387378452961916738524561294873289573416734816295
145927638627385149893641752472159386358462971916738425781294563269573814534816297
145927638627385149893641752952168374378452961416739825761294583289573416534816297
145927638627385149893641752952176384368452971714839526571294863289563417436718295
145927638627385149893641752952176384368452971714839526571294863289763415436518297
145927638627385149893641752952176384378452961416839527561294873289763415734518296
145927638627385149893641752972156384358472961416839527561294873289763415734518296
145927638627385149893641752972158364358462971416739825761294583289573416534816297


the MCNs are
Code: Select all
12, 13, 15, 13, 15, 15, 15, 13, 12, 12, 13, 15, 15, 15, 15, 13
coloin
 
Posts: 1727
Joined: 05 May 2005

Re: But does it have an 18 ?

Postby Moschopulus » Tue Dec 13, 2005 4:00 pm

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 ?

Postby Wolfgang » Tue Dec 13, 2005 8:14 pm

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 ?

Postby Moschopulus » Wed Dec 14, 2005 7:50 pm

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 ?

Postby Wolfgang » Wed Dec 14, 2005 9:20 pm

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

Return to General