The New Sudoku Players' Forum

[gfroyle]

The canonical one doesn't have unavoidable sets of size 6. It has 9 disjoint unavoidable sets of size 9 which each require 2 clues.

Yes it does... if the complete grid is

Code: Select all

1 2 3  4 5 6  7 8 9 
4 5 6  7 8 9  1 2 3 
7 8 9  1 2 3  4 5 6 

2 3 4  5 6 7  8 9 1 
5 6 7  8 9 1  2 3 4 
8 9 1  2 3 4  5 6 7 

3 4 5  6 7 8  9 1 2 
6 7 8  9 1 2  3 4 5 
9 1 2  3 4 5  6 7 8


then the following set is unavoidable..

Code: Select all

1 . .  4 . .  7 . . 
. . .  . . .  . . . 
7 . .  1 . .  4 . . 

. . .  . . .  . . . 
. . .  . . .  . . . 
. . .  . . .  . . . 

. . .  . . .  . . . 
. . .  . . .  . . . 
. . .  . . .  . . .


because we can just exchange them vertically to get

Code: Select all

7 2 3  1 5 6  4 8 9 
4 5 6  7 8 9  1 2 3 
1 8 9  4 2 3  7 5 6 

2 3 4  5 6 7  8 9 1 
5 6 7  8 9 1  2 3 4 
8 9 1  2 3 4  5 6 7 

3 4 5  6 7 8  9 1 2 
6 7 8  9 1 2  3 4 5 
9 1 2  3 4 5  6 7 8


At least, this is the way that I am using the term "unavoidable set" (I am more than happy to use unavoidable set; it is much better than exchangeable ).

Cheers

Gordon

[dukuso]

well, what I called the "most canonical" sudoku-grid 3 posts ago,
isn't really most canonical, I think now.
It's used in the NP-complete proof and it's so cyclical,
but it uses gangsters : 1,1,1 - 42,42,42 , while this one:

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.

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



Guenter.

[gfroyle]

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.

Presumably you mean "each of the 9 3x3 latin subsquares" ?

But even so, I can't see how you drive it down to only 1296 configurations.. or at least not trivially. You must be using some big group to reduce possibilities, but I can't replicate it (at least, in my head).. can you give a few more details..

Cheers

gordon

[dukuso]

18 latin subsquares, 3 in each band, 3 in each stack.
I used a computer program to find the 1296 configurations
with 2 clues in each of the 18.
Also the 2 clues of one latin square mustn't be in the
same row or column and mustn't
contain the same symbol.

e.g.

Code: Select all


1..4..7..
4..7..1..
7..1..4..
.........
.........
.........
.........
.........
.........


and


123......
.........
.........
231......
.........
.........
312......
.........
.........



here is the grid again to spot the 18:

(1,1,1 - 1,1,1)
123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645


here is one of the 1296  arrangements
compatible with the 18 latin squares :


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






[dukuso]

some more answers to Coloin and Moschopulus :


>Did it turn out by chance that the horizontal bands are all a
>representation of 42 ? [ Are you sure the lower band is a 42
>?]

yes,yes

>On this note - in discussing Red Ed's Gang members - it hasnt
>been pointed out that each member is a palindrome - ie when
>rearranged it is in the same gang when looked at from right to
>left - this has to be I think.

one of our 6^8*2 transformations

>On finding the 16 - It is the last clue to be added which does
>the "damage" in completing the grid - this makes logical
>addition/removal and analysis perhaps difficult to interpret.
>The 16 grid, even though unique, when "found" may not be the
>easiest grid to complete.

---------------

>How are you going about checking your 16 combinations for
>unique solutions ?

run them through my solver

>How difficult would it be to compile a "list" of all 6*10^21
>grids ?

too many

>Maybe we only need to compile a "mini-list" to get an idea
>whether a combination of 16 numbers might be unique. How long
>would this need to be ?
>
>We could take out 9! for box 1
>
>That would be 72 numbers per grid - Say 10^10 grids to start.
>Is this doable ?
>
>If you do get a fit then it is not unique. If it has a chance
>of being unique - our random 16 combination will not coincide
>with any other suduku amonst our mini-list. [Apart from the
>original].
>
>Then subject the grids which get through to a solver program
>to impart the ultimate check.
>
>How long would it take to analyse some of the 81! / 65! 16ers
>in our grid ? in this way !!
>
>Im prepared for failure here.
>
>Colin

there binomial(81,16)~3e16 possible configurations for the 16 clues once
you fix the grid. There can be some symmetries, but don't expect
too many.So in general it's not doable.
However with the 1,1,1 grids we have the constraint to place 2 clues
in each of the 3*3 latin subsquares, so they uniquely specify it


-------------------------

>A bit of a coincidence - that your grid was pulled out after
>so much analysis - and it was essentially the same as
>Moschopulus' except rotated by 90 degrees.
>
>It was a trifle symetrical - which implies that it would need
>more clues - I agree.
>
>I dont know how to take the choice of a suitable grid furthur
>- it seems that it may be a chance occurance. May be a good
>mix is what is needed !
>
>44^6 = 7256313856
>
>[5472730538 is the number Red Ed calculated for "essentially
>different grids", this is fairly healthily similar but below
>the 44^6.]
>
>Are these two numbers meaningfully depicting the same thing.
>
>44^6 minus the ones where there was no solution = 5472730538 ?

some 6-tupesl are equivalent, they correspond to the same
of the 5e9 classes.
We have a factor of about 6*6*2 : order the
3 horizontal gangsters and the 3 vertical gangsters
and then take the minimal 3-group first


>[ As I understand it - the fact that a grid can or cannot be
>transposed into another has been felt fairly unimportant -
>maybe it IS significant if it cant be transposed]

what you mean ? It's important for reducing the cases.

>What is the breakdown [gangsterwise] of Gfroyles 17s ? I
>wonder

I posted a statistics earlier in this thread


-----------------------------



>I would have thought it would make you believe more in the
>conjecture, not less. Or do you think you can make exactly 16
>clues on the right and exactly 2 clues on the left?

I meant the conjecture with the symmetry group.
We can have have many symmetries (42,42,42) but
few clues




>I was asking G how he was checking his solutions ! - in
>particular how can you reliably check that a certain
>combination does/doesnt have a single solution - surely that
>takes a long time if it envolves multiple guess logic - [maybe
>he has a solver do do this reliably]

yes, just a solver. It takes typically less than a millisecond
to solve such a puzzle. Longer to count the solutions, if there are many.


>dukuso wrote:
>
>we have 9^9=4e8 choices to place the 18 clues.
>[/code]
>
>
>Why isnt this 81!/63! - [any 18 anywhere] or 9^9*9^8 [two
>clues to a box] ?

9 possible choices for each of the 9 disjoint 3*3-latin squares,
which have to hold 2 clues.


-------------------------

>I cant imagine how you have done it ?

2 million random 18-clue-sudokus over that grid

------------------------------

>To go back to the exchangeable sets (could I suggest the name
>"unavoidable" sets):
>

in this one all pairs of symbols give chains of maximal length.
It was not easy to find !

(5,5,5 - 5,5,5)

123456789
897123456
645789123
312645978
789312645
564978312
951267834
438591267
276834591

I once tried to use it to find sudokus with few clues without success.
Guenter.

[coloin]

Thanks very much
The fact that such an apparently symetrical grid can be reduced to 18 clues is a perhaps a major breakthrough. andI believe you have shown it cant be reduced to 17. Your solver obviously has solving difficult puzzles sorted - I will try and dig out a difficult one that I saw once which had a lot of track-backs and see if it really can do it in a millisecond !!!!

So we have a 1,1,1-1,1,1. which can be done in 19
We have a 42,42,42- x,x,x. which can be done in 18
Both symetrical grids which previously we thought couldnt be represented in anything approaching these minima
Now all the other grids - are they 17ers ?

I understand now how the symetries reduced the possible combinations in these grids which unfortunatly cant be replicated in other grids. [Pity]

You wrote concerning Gfroyles 17er grid a while back
"34 29 38 , 32 34 18"

I didnt realize you can classify grids according to their 6 "44" bands until 2 days ago - [You were streets ahead of "us" mate ]

Maybe Gfroyles series of 17ers is not so surprising - if you look hard enough you are going to find a 17 in many non symetrical grids. That would explain why it didnt appear "tight" when Frazer calculated quite nicely it 's 18 box crosses. [Each B2/B4 interaction]

That might mean that we perhaps have room for finding a "tighter" grid - ie a grid with a lower overall average of box crosses.

From Frazer
"(2) One of the three rows has the same numbers as a column, but the other two have just two; e.g., 147/259/368 [384 ways].
(3) All three rows have two numbers from a column; e.g., 148/259/367 [392 ways]. "

Can we invent a grid with more of the above than normal - throw in one with no unavoidable sets - it must be possible - given G's determination !

Thanks again for explaining.

I think a 16 is sort of close !

[Moschopulus]

in this one all pairs of symbols give chains of maximal length.
It was not easy to find !

(5,5,5 - 5,5,5)

123456789
897123456
645789123
312645978
789312645
564978312
951267834
438591267
276834591

I once tried to use it to find sudokus with few clues without success.
Guenter.

You're way ahead of me.

But I don't understand what you mean by "all pairs of symbols give chains of maximal length"
This grid has
123......
.........
.........
312......
.............etc
Is this not a chain of length 3?
You probably mean something else.

--------------------------------
Thank you for showing that the most canonical grid has no 18ers.
So there may be some truth to the principle
lots of symmetry <---> lots of clues needed
but its probably of no use in finding a 16.

I also don't understand the 1296 figure. I got 162.
There are 9 3x3 Latin squares, each requiring 2 clues.
For a given 3x3 Latin square, the first clue can be chosen in 9 ways, and the second clue can be chosen in 2 ways. (it can't be in the same row, column, or be the same digit)
Since the 9 Latin squares partition the grid, there are 9x18=162 ways of choosing 18 clues.

What am I doing wrong?
---------------------------------------------------
gfroyle said

>Yes it does... if the complete grid is

pointing out the size 6 unavoidable sets. Thank you!
Those sets are subsets of the size 9 unavoidable sets, aka the 3x3 Latin squares.
(Glad you like the term unavoidable )

I was trying to formulate properties a good candidate grid for a 16 might have. And I was trying to make that particular grid fail them, since we know it requires at least 18. (and it has an 18 as dukuso found)

I'm guessing so far at
1) as little symmetry as possible
2) no unavoidable sets of size 4
3) 16 unavoidable sets of size 6 that cover all 81 cells

you guys have probably been down that road. what conditions did you come up with? Maybe its not a profitable road to go down.

[coloin]

G is way ahead !

I think unavoidable sets are to be avoided ! [sic]
A littke symmetry may not be all that bad !

??? ***
??? ***
??? ***
123
456
789

where we are given all the *, and want the ?. The situations are:

(1) The three rows of * have the same numbers as the three columns (in some order); for example, 147/258/369, or 825/417/693 [432 ways to fill in the ?].
(2) One of the three rows has the same numbers as a column, but the other two have just two; e.g., 147/259/368 [384 ways].
(3) All three rows have two numbers from a column; e.g., 148/259/367 [392 ways].
(4) Two rows have two numbers from a column, but the other has just one; e.g., 143/256/789 [400 ways].
(5) All three rows have one number from each column; e.g., 123/456/789 [448 ways].

It takes a little thought to convince yourself that there are no other possibilities. Of the 18 pairs of blocks.............

Tried the above

Problem ! -
Using (2) tends to rule out other possibilities and precludes using a (3) and a (4) if I have done it right - and that was just for completing B2B4B6B8 - constraints come into play very early on [this is good ?] and means you have to use a high scoring (5)
The other 14 interactions were beyond control - mine anyway!!!

If you can get a grid to complete with a low "box interaction average" I think we will be in buisness.
Maybe analysis of grids with this in mind is the answer.

It might work !

I will look !

[dukuso]

>dukuso wrote:
>
>
>in this one all pairs of symbols give chains of maximal length.
>It was not easy to find !
>
>(5,5,5 - 5,5,5)
>
>123456789
>897123456
>645789123
>312645978
>789312645
>564978312
>951267834
>438591267
>276834591
>
>I once tried to use it to find sudokus with few clues without success.
>Guenter.
>
>
>You're way ahead of me.
>
>But I don't understand what you mean by "all pairs of symbols give chains of maximal length"
>This grid has
>123......
>.........
>.........
>312......
>.............etc
>Is this not a chain of length 3?
>You probably mean something else.

yes, I think we had this earlier. You might have missed it.
Delete all symbols except 2 from a sudokugrid,
and consider the remaining 18 cells as vertices of a graph,
with two cells being joined by an edge, iff they are in the
same row,column or block. Then count the sizes of the
connected components.
If you do this in the grid above, you can always
reach each cell from each other cell, no matter which symbols
you choose or where you start.
No
1..2
2..1
or other things which are diconnected from the other 14 vertices.
I had uploaded a program here
http://magictour.free.fr/nppcs2.exe
which prints the coded cycle-structure of a sudokugrid.
This is invariant by the 9!*6^8*2 sudoku-transformations.


>--------------------------------
>Thank you for showing that the most canonical grid has no 18ers.
>So there may be some truth to the principle
>lots of symmetry <---> lots of clues needed
>but its probably of no use in finding a 16.

also the 1-gangster has 1728 compatible bands,
much more than the others. So even when the other 2 bands are
filled, there are still 1728 possibilities !

>I also don't understand the 1296 figure. I got 162.
>There are 9 3x3 Latin squares, each requiring 2 clues.
>For a given 3x3 Latin square, the first clue can be
>chosen in 9 ways, and the second clue can be chosen
>in 2 ways. (it can't be in the same row, column,
>or be the same digit)

the order of the clues doesn't matter, so divide this by 2.

>Since the 9 Latin squares partition the grid, there are 9x18=162
>ways of choosing 18 clues.

they are independent, so it's 9^9 , but

>What am I doing wrong?

we have another 9 latin squares vertically and these must match
with the clues too. See my other post, in reply to Gordon.

>---------------------------------------------------
>gfroyle said
>
>>Yes it does... if the complete grid is
>
>pointing out the size 6 unavoidable sets. Thank you!
>Those sets are subsets of the size 9 unavoidable sets,
>aka the 3x3 Latin squares.
>(Glad you like the term unavoidable )
>
>I was trying to formulate properties a good candidate grid
>for a 16 might have. And I was trying to make that particular
>grid fail them, since we know it requires at least 18.
>(and it has an 18 as dukuso found)
>
>I'm guessing so far at
>1) as little symmetry as possible
>2) no unavoidable sets of size 4
>3) 16 unavoidable sets of size 6 that cover all 81 cells
>
>you guys have probably been down that road. what conditions
>did you come up with? Maybe its not a profitable road to go down.

Some time ago Gordon tried a setcover method with all
the sets requiring a clue. Seems he gave up on this ?!

[dukuso]

>Thanks very much
>The fact that such an apparently symetrical grid can be reduced
>to 18 clues is a perhaps a major breakthrough. [I believe you
>have shown it cant be reduced to 17 ? ]

yes, each of the 9 disjoint 3*3 latin squares requires 2 clues at least.

>Your solver obviously has solving difficult puzzles sorted -
>I will try and dig out a difficult one that I saw once which
>had a lot of track-backs and see if it really can do it in a
>millisecond !!!!

most sudokus are easy and don't require backtracking

>I understand now how you were to reduce the possible combinations
>- and that perhaps there are going to be too many combinations
>do this with a "real" grid. [Pity]
>
>You wrote concerning Gfroyles 17er grid
>"34 29 38 , 32 34 18"
>
>I didnt realize you can classify grids according to their 6 "44" bands
>untill yesterday -[You are streets ahead of "us" mate]

I wrote a program to do this. I needed it for the enumeration
of all sudokugrids.
We have 416 equivalence classes of bands with the normal (RedEd-)
equivalence and it would be useful to have a program to print
the classes of the 6 chutes of a sudokugrid within this 416-gang
too. But I never came to write it. It was not so easy,
but clearly possible. Maybe someone else can do it ?

>Maybe Gfroyles series of 17ers is not so surprising - if you

surprising is the big number - I can't find them with this
high frequency.

>look hard enough you will find a 17 in many non symetrical grids.
>That would explain why it didnt appear "tight" when Frazer
>calculated quite nicely it 's 18 box crosses. [Each B2/B4 interaction]
>
>That might mean that we perhaps have room for finding a
>"tighter" grid - ie a grid with a lower overall average of box crosses.
>
>From Frazer
>"(2) One of the three rows has the same numbers as a column, but
>the other two have just two; e.g., 147/259/368 [384 ways].
>(3) All three rows have two numbers from a column; e.g.,
>148/259/367 [392 ways]. "

this I don't understand.
- I see your new post now, which seems to make it clear

>Can we invent a grid with more of the above than normal -

of the above what ?

>it must be possible - given G's determination !
>
>Thanks again for explaining.
>
>I think a 16 is close !

.. or a proof that there is none

[coloin]

>Can we invent a grid with more of the above than normal -

of the above what ?

ie more of 382 and 392

it seems that they preclude one another rather too conveniently for my liking.

>I will try and dig out a difficult one that I saw once which had a lot of track-backs

Ah...... the grid I had seen has already been noticed by you !
It had "48 unwinds" and not recommended for humans !
. . . | . . 3 | . 6 .
. . . | . . . | . 1 .
. 9 7 | 5 . . | . 8 .
----------------------
. . . | . 9 . | 2 . .
. . 8 | . 7 . | 4 . .
. . 3 | . 6 . | . . .
----------------------
. 1 . | . . 2 | 8 9 .
. 4 . | . . . | . . .
. 5 . | 1 . . | . . .
Sad man solver did it in a microsecond/2 seconds
sudokusolver by logic did it in 82 seconds - [albeit with guesses]

That rules out any need to classify all the grids then - one solution was found very easily here - and this has been regarded as an extreme puzzle.

>surprising is the big number - I can't find them with this high frequency.

Perhaps he has looked harder ! - there are an unmanageable number of possibilities for each grid as you say.

The interesting progress you have made is that we have PROVED some sudokus can be solved in a minimum of 19 and 18 numbers respectivly - and these grids had a degree of symmetry that we thought meant you needed many more solutions. That would tend to indicate that many if not all sudukus can be presented in minimal clues of 18 or less - we just need to look hard enough as you did with the grids above. This is of course challenging.

Has anyone proved that any specific grid cant be reduced to less than 20 ? [I dont think so]
If a respectable few random grids can all be reduced to the 18 or so clues then perhaps this is good evidence.[Can the above puzzle/grid be reduced to 18 ? I wonder]
If a very specific grid can be reduced to 16 clues then we have proved that there is one ! Until then we will never know ....

Looking for a grid with 384s etc
here is this semi one

123 948 675
456 137 982
789 256 134

912
348
567

691
235
874

this has 2 x 384s in B2/B4 and B3/B7 - This has only 2328 solutions - well below the average of 2693.
I will look at these solution grids more
What are these gangsters incidently ?

Regards

[Nick70]

That rules out any need to classify all the grids then - one solution was found very easily here - and this has been regarded as an extreme puzzle.

That was before techniques like forcing chains were refined. That problem isn't extreme by the current standards.

[coloin]

Ok
So whats the current hardest ? Out of interest.

I calculated a ganster 42 with 2x 384s as before - 2502 solutions - not spectacular

The symetrical gangster "1" - unable to do do any box interaction 384s - inherent clash here

By the way Guenter's ganster "1" appears to be Red Ed's "44" - please check this !

[Moschopulus]

Has anyone proved that any specific grid cant be reduced to less than 20 ? [I dont think so]

Suppose we can find a 4x4 sudoku requiring 5 clues.
It might be possible to put 4 of these 4x4 sudokus into a 9x9 in a disjoint way. The result would require at least 4*5=20 clues.

[gfroyle]

Some time ago Gordon tried a setcover method with all
the sets requiring a clue. Seems he gave up on this ?!

I could not find any set covering programs implemented that I could use for experimentation... I also discovered that the number of unavoidable sets seems to grow quite large.. my naive feeling is that the small unavoidable sets are going to be the determining factor, but without a set cover program I can't do the experiments.

(I have too many other tasks on my plate to spend time trying to write a set cover program...)

Gordon