The New Sudoku Players' Forum

[coloin]

This is dukuso's elegant proof that the grid does not have an 18 - but does have a 19.

123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645

uses gangsters 1,1,1 - 1,1,1 so I think it's the most canonical.
It could also be the one requiring the most clues, since gangster1 stands for 1728 bands, the most of all gangsters.

So now I tested whether there is a 18-clues sudoku whith that grid as unique solution.
18 clues are required at least, as we have seen before and these must be arranged such that 2 clues solve each of the 18 3*3 latin subsquares.
This gives only 1296 possible configurations of the 18 clues and none of them give a sudoku with unique solution.
We have :
18 configurations with 413108 solutions
108 configurations with 141917 solutions
36 configurations with 47479 solutions
18 configurations with 44148 solutions
162 configurations with 41224 solutions
162 configurations with 22245 solutions
18 configurations with 16740 solutions
324 configurations with 15156 solutions
162 configurations with 9258 solutions
108 configurations with 4914 solutions
162 configurations with 411 solutions
18 configurations with 96 solutions

it seems that we have 18-fold symmetry here.

With 19 clues however there are uniquely solvable sudokus over this grid.

Code: Select all

.........
..6.8.1..
7....3.52
..1.6.8..
.....7.3.
...2.....
3....5.7.
.4.......
..8...6..    EDIT  this does not have a unique solution !


EDIT

This is wrong

It does NOT have a 19-clue puzzle !!!!!!!

[DanO]

Sorry, but F (as well as some others) is not unavoidable.

You are absolutely right. I tried covering the grid with 18 clues and got unavoidable sets that were similar to F but were probably spanning the disjoint sets. I'll have to try again and see where I went wrong.

[edit - The third set of clues in each subgrid was in fact superfluous. I got down to 20 clues by hand and will leave further reductions to the computers]

PS: is there someplace I can pick up another pair of eyeballs?

[Moschopulus]

From analysis of my list of 17s, these are the top 5 most fertile complete grids (in the sense of containing multiple different 17s).

Code: Select all

639241785284765193517983624123857946796432851458619237342178569861594372975326418
873692451649517328521348976132976845498125637765483192954761283386254719217839564
438926751796451382251738469123687945647593218589214673362175894914862537875349126
236195478487263159591487632123759864759648321648321795314972586872516943965834217
481972365296534178537168942123697584658241793749385216314726859965813427872459631


The number of 17s (that I know of) in these grids is 29, 20, 14, 12 and 11 respectively.

The third grid in the top 5 has no 16. I did an exhaustive search over the weekend.

[Moschopulus]

123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645

uses gangsters 1,1,1 - 1,1,1 so I think it's the most canonical.
It could also be the one requiring the most clues, since gangster1 stands for 1728 bands, the most of all gangsters.

So now I tested whether there is a 18-clues sudoku whith that grid as unique solution.
18 clues are required at least, as we have seen before and these must be arranged such that 2 clues solve each of the 18 3*3 latin subsquares.
This gives only 1296 possible configurations of the 18 clues and none of them give a sudoku with unique solution.
We have :
18 configurations with 413108 solutions
108 configurations with 141917 solutions
36 configurations with 47479 solutions
18 configurations with 44148 solutions
162 configurations with 41224 solutions
162 configurations with 22245 solutions
18 configurations with 16740 solutions
324 configurations with 15156 solutions
162 configurations with 9258 solutions
108 configurations with 4914 solutions
162 configurations with 411 solutions
18 configurations with 96 solutions

it seems that we have 18-fold symmetry here.

With 19 clues however there are uniquely solvable sudokus over this grid.

Code: Select all

.........
..6.8.1..
7....3.52
..1.6.8..
.....7.3.
...2.....
3....5.7.
.4.......
..8...6..


Can you (or anyone) do the same with this grid?

123789456
456123789
789456123
231564897
564897231
897231564
312645978
645978312
978312645

The same proof works to show that at least 18 clues are needed.
It would be interesting to know if this has an 18.

[dukuso]

if I made no mistake, then this grid :

Code: Select all

123 789 456
456 123 789
789 456 123

231 564 897
564 897 231
897 231 564

312 645 978
645 978 312
978 312 645


has no 18-clue-sudoku.

I couldn't even find any set of 18 cells such that each of the 6 chutes
had a unique solution when all the 54 clues in the complement were filled in.

I had problems to find a 19-clue-sudoku in this grid
but couldn't prove it's impossible either.
Here is a 20-clue-sudoku with this grid as solution:

Code: Select all

1.3 ... .5.
... .2. 7..
... ..6 ..3

..1 5.. .9.
.6. ..7 ...
8.. ... ...

... ... ...
..5 9.. .1.
.7. 3.2 6..



OK, I ran through a process now to prove that there is no 19.
I won't yet say that I proved there is no 19, regarding the
history of errors and bugs. Give it 50% that my "proof" is correct.
I found only 8 nonequivalent unique-solution-sudokus over this grid
with 6 clues in two bands each and 27 clues in the third band.
Then I ran these through http://magictour.free.fr/suexmult.exe
and no 19 was found. No 20 was found this way either.


here are the 8 files run with suexmult file 7 :

Code: Select all


2...2.........22....2....2..2...2...2.......2...2...2.111111111111111111111111111
123789456456123789789456123231564897564897231897231564312645978645978312978312645

2...2.........22....2....2....2...2..2...2...2.......2111111111111111111111111111
123789456456123789789456123231564897564897231897231564312645978645978312978312645

2...2...2..22...2............22......2.......2...2...2111111111111111111111111111
312645978645978312978312645231564897564897231897231564123789456456123789789456123

2...2...2..22......2.........22......2....2......2...2111111111111111111111111111
312645978645978312978312645231564897564897231897231564123789456456123789789456123

2...2...2..2.......2....2....2....2......22..2...2....111111111111111111111111111
312645978645978312978312645231564897564897231897231564123789456456123789789456123

2...2...2..2.......2....2....2.......2...22..2...2....111111111111111111111111111
312645978645978312978312645231564897564897231897231564123789456456123789789456123

2...2......2....2......22....2....2......22..2...2....111111111111111111111111111
312645978645978312978312645231564897564897231897231564123789456456123789789456123

2...2......2....2......22.....2...2..2...2...2.......2111111111111111111111111111
312645978645978312978312645231564897564897231897231564123789456456123789789456123



[Moschopulus]

Can you not reduce to 1296 configurations for 18 clues, like the previous time, and then add one more clue in all possible ways?

[dukuso]

Can you not reduce to 1296 configurations for 18 clues, like the previous time, and then add one more clue in all possible ways?

that's what I did.
But instead of 1296 configurations, I found zero.

BTW. I think there are 64 sudoku isomorphism-classes
over this grid with 6,6,9 clues in the 3 bands.
None with 6,6,6 none with 6,6,7 none with 6,6,8

[gfroyle]

Here's a question for you all..

I have now got about 13 x 10^6 distinct 18-clue Sudokus.

Consider now the PATTERN of occupied cells... some patterns are more prolific than others, in that I have lots of ways of choosing the actual values to complete a uniquely completable Sudoku. Some patterns are less prolific in that I only know a few ways of filling them in.

The MOST prolific pattern (among my particular collection) is

Code: Select all

. . .  x . .  x x . 
x . x  . . .  . . . 
. . .  x . .  . . . 

x . .  . x .  . . x 
. x .  x . .  x . . 
. . .  . . .  . . . 

. . .  . x x  . . x 
. x .  . . .  . x . 
. . .  . x .  . . .


for which I currently know just over 2500 distinct 18-clue puzzles.

What makes it good?

[Moschopulus]

What makes it good?

I don't know, but would it be feasible to search all 16-clue sub-patterns of this pattern for a 16?

[gfroyle]

I don't know, but would it be feasible to search all 16-clue sub-patterns of this pattern for a 16?

If I restrict the search to considering patterns where no digit occurs more than three times, then I can do a 16-clue pattern exhaustively. So there would be 9 x 17 of them to do, which would take me a while.

Unfortunately the guy that emailed me saying that he could do an exhaustive search over a 17-pattern in 2.5 hours has since emailed me to say that he has discovered bugs in his program ..

So, to answer your question, feasible but not easy, and not something I would undertake without a stronger feeling that it would be worthwhile (because my computers are also busy doing actual work!)

What is frustrating is that this pattern appears to be very "middle of the road" compared to the other 18-patterns that appear - it doesn't stand out in any way that I can see...

Cheers

Gordon

[Wolfgang]

We know that such a pattern is isomorphic to many others. Do you have a method to choose a representative for each class ?

[Wolfgang]

Code: Select all

. . .  x . .  x x . 
x . x  . . .  . . . 
. . .  x . .  . . . 

x . .  . x .  . . x 
. x .  x . .  x . . 
. . .  . . .  . . . 

. . .  . x x  . . x 
. x .  . . .  . x . 
. . .  . x .  . . .


What makes it good?

I think, one reason is that its easy to force singles with this pattern. Eg when you put a 1 in r2c3, r4c9 and r7c5, all 1's already are fixed.

[gfroyle]

We know that such a pattern is isomorphic to many others. Do you have a method to choose a representative for each class ?

Yes, but I can't tell you much about the chosen representatives!

Or more accurately, I convert each puzzle into a graph, find the canonical labelling of that graph with "nauty" and then convert back to a puzzle. The canonical labelling that nauty provides has no particular human interpretation, but is rather a feature of the computation tree involved in the labelling. The only guarantee that we have is that isomorphic graphs will have the same canonical labelling..

So it is essentially a black box. In goes a puzzle, out pops a relabelled puzzle. The program guarantees that if you enter two isomorphic puzzles (in other words one obtained from the other by renaming symbols, permuting rows within a band, permuting columns within a chute, permuting entire bands or chutes, or transposing the matrix) then the output will be IDENTICAL in each case. But there is nothing much else that one can say.

This is how I can make my lists of 17s and 18s and claim that I have a particular number of them. Each time a supposed new one turns up, I use the black box to relabel it, then compare it with the existing list, only adding it if it is not already in the list.

Now it APPEARS that it consistently relabels patterns of a particular size. In other words, the relabelled version of two puzzles that use the same pattern will also use the same pattern. However I have not verified that rigorously (whereas the stuff about isomorphism is absolutely correct), but could probably do so if it were necessary.

Cheers

Gordon

[Wolfgang]

Moschopulus, i ran my old program with your grid above over night. I only found a lot of 20-clues (must be over 200). Finding a 19-clue in this grid seems to be about that hard as to find an 18-clue in 'Moschopulus I'.

[coloin]

Interesting post regarding the patterns in 18 clue puzzles. Ultimately all minimal clue puzzles initially generate clues , whether they generate all of one clue initially or generate the rest as the grid completes - depends on the order at which you decide to solve/add clues.

In the analysis of the patterns -
A question concerning some of the clues in your pattern.
Typically there are several sets of three clues in a puzzle - Of your most prolific pattern would I be correct to say that of the particular positions in your pattern there are sets of three clues which recur? - ie are they potentially are in the same template. For the first template of clues in your prolific pattern two out of the three clues might be in one of [r1c4,r3c4 or r5c4] and [r8c8 or r8c2] - thereby generating a clue in r9c6. Or perhaps the 3 positions that Wolfgang mentions - which generates a template.


This ties in nicely with recent posts on "templates" on the "fruitless discoveries thread" which may well be better continued here.

There are 46656 ways of inserting the first template of 9 similar clues in the 9 boxes and essentially they are all similar.

Code: Select all

1-- --- ---
--- 1-- ---
--- --- 1--

-1- --- ---
--- -1- ---
--- --- -1-

--1 --- ---
--- --1 ---
--- --- --1


There are 8696 [or ?17972 ways] of inserting the 2nd template given the 1st template already filled.
After that there is a range of ways for filling in the 3rd and subsequent templates
[Only 1 way to fill in the 9th]

46656 1-rookeries (templates) , 1 equivalence class
419250816 2-rookeries , 170 classes
866092839552 3-rookeries , 92053(?) classes
...
46656 8-rookeries , 170 classes
1 9-rookery , 1 class

I have run a solver on a few grids of the following pattern [with different B2-B9]:

Code: Select all

123 --- ---
456 1-2 ---
789 --- -12-

--- -2- --1
-1- --- 2--
--2 --1 ---

--1 --- -2-
2-- -1- ---
--- 2-- 1--


The analysis take 9 hours each! [Hopefully the B1 filling doesnt introduce bias - I cant see any]
Of the five I have done I got solution rates of approx.
2100,000,000
1220,000,000
1200,000,000
1080,000,000
989,000,000 {this is canonical - 1/2 in different row and column}


Apparently there are 170 equivalent double template combinations.[From dukuso's rookery calculations above]

If a particular double template combination has a low solution rate - they might be more frequent in Gordon's patterns.

EDIT - unfortunatly they are not !

Or maybe it is a specific triple or quadruple template combination which gives 17s ?