17-clue and 18-clue Sudoku update

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

Postby coloin » Thu Dec 08, 2005 12:18 pm

From the top of last page
coloin wrote:
Code: Select all
grid                 SF         SFB      Random 17 [number 1122]   Random

suexsf value        24.10       24.02        24.17                 24.42

number of 17s       29           3             1                     0

number of 18s*     2076 [71]   240  [80]      89  [89]            1 [estimate]
number of 19s*    75211      10089          4182                 80 [estimate]

where * is the number of puzzles generated using a "backbone" of the grid - there may well be many more 18s & 19s.



I "suexmulted" 2076 .......an average of 71 per each of the 29 17s in the SF.......a considerable number of these will be non minimal. [approx 1500]. There may well be others.....even some from another "region" of the grid.

............................................................................................................................................
.
A little furthur thought on the maximum number of disjointed unavoidables.[two disjointed unavoidable sets dont have intersecting clues]

Code: Select all
The reason that I think the largest minimum clues is 20 is that it is impossible to construct a grid which has more than 20 disjointed sets. You would have to have 20 disjointed 4-set unavoidables. It is also likely that a grid with 16 disjointed 4-sets, which has only room for 2 more disjointed 6-sets, will be solvable in 19 clues.


I mentioned that the upper limit numerically as 20 - in a way proving that it wasnt impossible to solve any sudoku in less than 21 clues.............

But it seems that it may not possible to fit more than 16 4-set disjointed unavoidables in any grid - and even that is going to be difficult.......with these 16 4-sets there will not be any room for any other disjointed 6-set.

Moschopulus wrote:I doubt very much if any grid has MCN = 17.


I think Mosch understood this but didnt say why !

This makes it even more likely that almost all grids are solvable in 18.

I will "try" to construct one of these high MCN grids to demonstrate..........

EDIT

Some grids with MCN of 15 and 16 have been posted recently
Code: Select all
MCN -15  [all clues in a 4 set ]
123568479864791352957243681218657934536489127749312865391825746472136598685974213

MCN -16
145726983837495261926381574293874156581269347674153892318547629459632718762918435


I doubt they can be done in 20 !

EDIT They both can be done in 20 [but almost certainly not 19]. See http://forum.enjoysudoku.com/viewtopic.php?t=2524
Last edited by coloin on Fri Dec 16, 2005 8:55 am, edited 2 times in total.
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Re: 17-clue and 18-clue Sudoku update

Postby Wolfgang » Thu Dec 08, 2005 8:46 pm

Lardarse wrote:In SF where you found 29 (iirc) minimal 17's, how many minimal 18's are there?

As far as i remember i didnt find a region with 18-clues apart from the 17-clues when i searched the grid, but i did not try for a long time, cause the 17s were found relatively soon for my method (after 1 day).
[edit:]This is only an answer to coloins question. of course there are some non trivial 18 clues in the 17-clues region, but i dont know how much.
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Postby gfroyle » Wed Dec 14, 2005 12:17 am

Some interesting data just arrived...

I was sent, from Japan, a number of new 17-clue Sudokus. He or she (I can't tell from the name!) had constructed 700 puzzles, of which 33 were not already on the list.

So, maybe this means that we really DO have almost all the 17s..

How to prove it though is entirely unclear...

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby dukuso » Wed Dec 14, 2005 2:02 am

gfroyle wrote:Some interesting data just arrived...

I was sent, from Japan, a number of new 17-clue Sudokus. He or she (I can't tell from the name!) had constructed 700 puzzles, of which 33 were not already on the list.

So, maybe this means that we really DO have almost all the 17s..

How to prove it though is entirely unclear...

Gordon




did he/she use a method different to yours ?
dukuso
 
Posts: 479
Joined: 25 June 2005

Postby gfroyle » Wed Dec 14, 2005 4:24 am

dukuso wrote:did he/she use a method different to yours ?


Almost certainly yes, but I do not know details.. I will encourage him/her to tell me and/or join the forum...

Gordon
gfroyle
 
Posts: 214
Joined: 21 June 2005

Postby Moschopulus » Wed Dec 14, 2005 10:30 am

Here's another pseudo-puzzle with 16 clues and 4 completions:

000010400800000060000900000041050000000000083000000000200806000060000100000300000
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby Wolfgang » Wed Dec 14, 2005 12:43 pm

Code: Select all
000010400800000060000900000041050000000000083000000000200806000060000100000300000

is equivalent to this one from gfroyle's list:
Code: Select all
5.42.........4..3.1.........6..73.........5.1..........3.....7....5..4..8........
Wolfgang
 
Posts: 208
Joined: 22 June 2005

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

How do you tell if two puzzles are equivalent?
Moschopulus
 
Posts: 256
Joined: 16 July 2005

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

Moschopulus wrote:How do you tell if two puzzles are equivalent?

See this recent thread:
http://forum.enjoysudoku.com/viewtopic.php?t=2505
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Postby Wolfgang » Fri Dec 16, 2005 9:54 am

I wonder that i didnt find this 17-clue in the list, there are 23 others around, which i all found in the list (maybe a bug?):
Code: Select all
120900000500000000000040300700001000008000400000000900004030070000005020000000010
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Postby gsf » Fri Dec 16, 2005 10:55 am

Wolfgang wrote:I wonder that i didnt find this 17-clue in the list, there are 23 others around, which i all found in the list (maybe a bug?):
Code: Select all
120900000500000000000040300700001000008000400000000900004030070000005020000000010

this puzzle is equivalent to
Code: Select all
....4..82631..................1.76..8......5....3......7....1..4...8.......2.....
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Wolfgang » Fri Dec 16, 2005 11:07 am

Thanks, so i have a bug in my normalization program:(
[Edit:] Fixed it, will update the source on the website this evening.
Wolfgang
 
Posts: 208
Joined: 22 June 2005

Re: 17-clue and 18-clue Sudoku update

Postby coloin » Fri Dec 16, 2005 11:19 pm

coloin wrote:A question...
In the grids with 17 clues......are there any 18s in these grids which have only a small number[or none] of clues in common with the 17 puzzle ?

Lardarse wrote:I'll take that question 1 step further:
In SF where you found 29 (iirc) minimal 17's, how many minimal 18's are there?


with 14 common clues use suexmult.exe over this text file
Code: Select all
111121211121111111121111111111211112211111111211111211211121111111111111111112122
639241785284765193517983624123857946796432851458619237342178569861594372975326418

suexmult file.txt 3 4 = 29 [17 clue] sudokus found
suexmult file.txt 4 4 = 2076 [18 clue] sudokus found

.......a considerable number of these will be non minimal.

EDIT...using suexmu35.exe which is modified to only print or cont minimal puzzles
suexmu35 sf.txt 4 4 = 397 [18 clue] sudokus found
suexmu35 sf.txt 5 4 = 6316 [19 clue] sudokus found

these are minimal suduku puzzles with this 14 clue backbone.

but I chanced upon these other [18s] [all minimal] which cannot be in the list [they dont have the 14 clue backbone]
Code: Select all
..9.4.7...8........1.....2....8.7..6.........4.....2..3.2.7..............7...6.18
...24.....8........17.........8.79...........4.....2..3..1...6........7..7...6.18
...24.....8.7......1....6.....8.7...7........4.....2..3.2.....9.......7......6.18
....4.7...8.7.....51..........8.7..6.........4.....2..3.2.............7..7...6.18
....4.7...8.7.....51..........8.7............4.....23.3.2....6...........7...6.18
....4.7...8.7.....51..........8.7............4.....2.73.2....6...........7...6.18
....4.7...8.7.....51..........8.7............4.....2..3.2....6........7..7...6.18
....4.7...8.7.....51..........8....67........4.....2..3.2.7...........7......6.18
....4.....8.7...9..17.........8.7..6.........4.....2..3.2.............7..7...6.18
....4.7...8.7......1..........8....67........4.....2..3.2.7.5.........7......6.18
....4.....8.7.....517.........8.7..6.........4.....2..3.2.............7..7...6.18
....4.....8.7.....517.........8.7............4.....2..3.2....6........7..7...6.18
....4.....8.7......17...6.....8.7............4.....2..3.2.....9.......7..7...6.18
....4.....8.7......17.........8.79...........4.....2..3.2....6........7..7...6.18
....4.....8.7......17.........8.7..6.........4.....2..3.2...5.........7..7...6.18
....4.....8.7......1....6.....8.7...7........4.....2..3.2.....9.......7..7...6.18
....4.....8.7......1....6.....8.7...7........4.....2..342.....9.......7......6.18
....4.....8.7......1....6.....8.7...7........4.....2..3.21....9.......7......6.18
....4.....8.7......1....6.....8.7...7........4.....2..3.2.7...9.......7......6.18
....4.....8.7......1....6.....8.7...7........4.....2..3.2.....9......37......6.18
....4.....8.7......1....6.....8.7...7........4.....2..3.2.....9.......7....3.6.18
....4.....8.7......1....6.....8.7...7........4.....2..3.2.....9.......7.....26.18
....4.....8.7......1....6.....8.7...7........4.....2..3.2.....9.......7......6418
....4.....8.7......1....6.....8.7...7........4.....2..3.......9.6.....7.....26.18
....4.....8.7......1....6.....8..9.67........4.....2..3.2.7...........7......6.18
....4.....8.7......1....6.....8....67........4....92..3.2.7...........7......6.18
....4.....8.7......1....6.....8.....7........4....92..3.2.7..6........7......6.18
....4.....8.7......1....6.....8.....7........4....92..3.2.7...9.......7......6.18
....4.....8.7......1....6.....8.....7........4.....2.73.2.7...9.......7......6.18


who knows how many more there are with the 10 common clues
Last edited by coloin on Tue Jul 25, 2006 6:58 pm, edited 2 times in total.
coloin
 
Posts: 2365
Joined: 05 May 2005
Location: Devon

Thumbs Up!

Postby Haley430 » Tue Dec 20, 2005 5:28 am

Wolfgang wrote:


I support it. It's the only thing that makes sense.
Haley430
 
Posts: 5
Joined: 19 December 2005

Re: Thumbs Up!

Postby Wolfgang » Tue Dec 20, 2005 9:55 am

hm, sense?
Wolfgang
 
Posts: 208
Joined: 22 June 2005

PreviousNext

Return to General