The New Sudoku Players' Forum

[dukuso]

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

you could just use a simple greedy algo and ignore the large sets,
that would give some good bounds at least.

[gfroyle]

Well, I confess to being flummoxed and disheartened at this stage..

I now have a collection of over 1 million 18-clue Sudoku - all guaranteed to be inequivalent (not just different, but actually inequivalent) and 4425 17-clue Sudoku, but just cannot seem to find a 16, no matter what I do

I have over 22000 18-clue Sudokus that use each number exactly twice, and a variety of other patterns .. for the 17-clue Sudokus, the most popular number-pattern is for three numbers to be used once, four used twice and two three times. There is a SINGLE one that I have found that uses 5 numbers once each, and 4 numbers three times each...

Other than that, I don't know where to go from here..

gordon

[gfroyle]

you could just use a simple greedy algo and ignore the large sets,
that would give some good bounds at least.

The bounds are in the wrong direction for finding a lower bound on the size of the critical set... what we need is something that says "EVERY hitting set has size at least X" whereas the greedy algorithm just gives something that is too large, but with no guarantees that there do not exist (much) smaller ones...

[Moschopulus]

I now have a collection of over 1 million 18-clue Sudoku - all guaranteed to be inequivalent (not just different, but actually inequivalent) and 4425 17-clue Sudoku, but just cannot seem to find a 16, no matter what I do

Perhaps because a 16 does not exist.

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.

I see now what you did. First of all the 3 obvious unavoidable sets (Latin subsquares) in each band bring us down to 9^9 possibilities.
Now you used another 9 obvious unavoidable sets from the stacks, giving another 9^9 possibilities, and you wrote a program to find the intersection of these two sets of possibilities. It turned out there were 1296 configurations in the intersection.
How long did that take on your computer?

This doesn't work for the 1,1,1-42,42,42 grid because we only have the 9 unavoidable sets from the bands. So you chose randomly from the 9^9 possibilities there. You could have tried to find more unavoidable sets in that case, to reduce the number of possibilties, but you didn't bother.

These unavoidable sets are really "double" unavoidable sets in the sense that *two* clues are required from each set, not just one.

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

How long did this take on your computer?
I just want to have an idea of how long it took to prove that this particular grid does not have an 18 clue puzzle.

Your procedure for searching for a k=18 clue puzzle in this grid went as follows:
1. you found a small number of unavoidable sets (in this example there were 18, they were obvious, and they were double unavoidable)
2. you found all possible clue placements consistent with the unavoidable sets (in this case there were 1296)
3. you checked each of the 1296 for multiple solutions.

Please correct me if I'm wrong.
What are the chances of automating this for k=16, and getting a working algorithm?
We would want to find a small number of unavoidable sets in step 1, such that the number of possible clue placements arising in step 2 is small.
Some play-off here, maybe introduce a cutoff number of clue placements like 1300 - once you are under that then go to step 3.
Then each of these possible clue placements is checked in step 3.

If this can be done in a short time for one grid, perhaps we can run through some set of grids, with small symmetry group say. I know running through all grids is not feasible.

[dukuso]

18 clues: 1 million
17 clues: 4400
16 clues, 2 solutions : 1

hmm, that doesn't already look too much discouraging.
How many with 19-clues ?

Maybe one day you'll get one of these 64-processor machines...
Or we can speed it up a little.


Yes the bound is in the wrong direction for proving that there
is no 16clue sudoku with a grid, but it give some hints
which grids are worth to be searched for a 16 and which not.

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


Moschopulus' description looks good to me.
generating the 1296 sudokus took 2 minutes
with a slow Basic-program.
Solving them took half an hour, because some had so many solutions.


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

and here is the 416-gang for Coloin:
http://magictour.free.fr/NPP416

entered as 9 minicolumns, with frequency

my 44-gangsters are also written in minicolumns, the minimal
representants of each class, sorted lexicographically

[coloin]

Thanks for the 416 .... Edit - this is different from the min lex classification by gsf

Have you checked the ganstser G 1 = 44 Red Ed - if it is we need to have a definitive definition before we get totally mixed up [ie is a 42 a 43]


Dont be downhearted you lot !

Sympathies to Gfroyle though - he has worked very hard.

I dont think we have looked hard enough in the right direction - there are a lot of solutions out there !

We have got a lot of 17ers - all solvable by humans - and we have a whole load of computing power which can solve really difficult grids in milliseconds - I think we just havnt found the right puzzle.

Now...Ive done a bit of analysis on some grids
I manufactured one with two "284s" in B1...B2/B4... B3/B7

Now my initial one as posted yesterday had 2328 solutions - but this had a few of our unwanted [or are they] pairs. I transposed them advantageously - sometimes the number of clues shot up - but I have got it down to 2126 solutions - which is getting pretty low I feel - and Im working on which of these is will be a good grid.

I analysed a few examples of a few other complete grids - it is the whole grid that matters - and from a B12347 with 2999 completions I placed four other strategic boxes which resuled in 18 box combos :
4 x 384
4 x 392
9 x 400
0 x 432
1 x 448

which has an average at 397.33

It had a good few number pairings though

[Someone has calulated the average overall ratios in a large number of grids is 27:54:162:1:36 overall 403.2]

Now the 432 only occurs in those useless symetrical repeating grids [I think]. So the easy way to get the average down in one stroke is to find a grid without a 448 - [all three rows have one number from each column]

This might be an easy step forward.

There are pairs in these so called tighter grids - and these dont make the grid attractive .......but ..... I think I can agree with Moschopulus that paradoxically we might use some or all? of these to our advantage in reducing the options for our 16 clues - although I appreciate it is not ideal - it is optimistic though !

[Moschopulus]

For a 20 clue example I suggested using a 4x4 sudoku grid that requires 5 clues.

Now that I've looked, I can't find such a thing. Do they exist?

Or is it true that every 4x4 grid has a 4 clue puzzle in it.

Also, 4 clues seems to be the minimum. I can't find any examples with 3 clues. Do they exist?

Surely everything is known about 4x4 sudokus.

[Moschopulus]

Moschopulus' description looks good to me.
generating the 1296 sudokus took 2 minutes
with a slow Basic-program.
Solving them took half an hour, because some had so many solutions.

Thanks for that. So it would be a few minutes if we didn't want the exact number of solutions. You can stop as soon as you get 2 solutions, and go on to the next one.

Any chance of you trying this for some other grid? It would be nice to pick a grid at random and prove it has no 16 in it, with this "algorithm".

[coloin]

I dont know how long it would take to prove that - a long time

The mathematics of the 2x2/4x4 grids was less challenging for the experts !
It is on the programmers side -

There supposedly are 288 solutions--some felt it was 192--but the powers that be decreed it was 288.

There are only 2 unique ones

http://www.setbb.com/phpbb/viewtopic.php?t=27&mforum=sudoku

minimum number for completion - dunnno - !

On your last point about using the paired clues - I think we need as much help from the 16 as possible so therefore "wasting" a clue is going to hamper us - but I think it is worth a try.

Anything to cheer Gfroyle up - [may be the cricket will]

I m still struggling to get a grid without a 448 - they just keep appearing !
Colin

[dukuso]

I should have taken the 416-gang, not the 44-gang, when I
examined how many clues are needed for a band.

edit: no, 44-gang was right. We assumed that 2 bands were filled
plus some clues. This determines the gangster(44).

I can download Frazers gangsters and determine their numbers.
Frazers gangsters have these indices in my alphabetical list:

33,31,15,25,37,38,18,36,32,20,27,23,17,11,24,29,35,39,22,21,
10,28,14,16,34,42,41,12,26,4,13,43,30,9,3,8,7,6,19,2,40,44,5,1

(BTW. I couldn't edit nor post here some hours ago, seems it's fixed now)

running the 1296 through my solver and interrupting after
2 solutions takes 0.3sec.

A good strategy to find few-clue-sudokus for a given grid
could be first to fill the small unavoidable sets randomly,
then put the other clues randomly.

Or examine how many clues have to go into 6*9-subsudokus
or into the subsets formed by 3,4,5.. symbols.

Coloins 12347-5689 partition into blocks could also be useful,
but I still prefer the chutes-partition.

[coloin]

Bad news ...good news......bad news

Frazer gave us this:
"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 in Gordon's grid, we have:

B1vB5: (4), B1vB6: (4), B1vB8: (4), B1vB9: (4), B2vB4: (4), B2vB6: (4), B2vB7: (2), B2vB9: (4), B3vB4: (5), B3vB5: (4), B3vB7: (4), B3vB8: (4), B4vB8: (3), B4vB9: (4), B5vB7: (5), B5vB9: (4), B6vB7: (4), B6vB8: (3).

Rather than 27:54:162:1:36 for 384,...,448, we have 1:2:13:0:2, averaging 403.56, a little higher than overall average 403.2"



Its good apart from the fact that the box combinations is not the same both ways !

Therefore there are 36 box combinations rather than 18 - might explain why Gfroyes grid was so apparently unspectacular.

This makes things more complicated - but maybe is good as it gives us scope for finding a more special grid.

However I have a sneaking suspision that this tight grid when found will be riddled with pairs - as per Gfroyle.

Cautious optimism then - we will just have to use those pair clues!

[dukuso]

384 vs. 448 etc.
that doesn't look so much different to me.
So, why do you expect some breakthrough from
classifying these ?

[Moschopulus]

Since there are only two 4x4 sudokus up to equivalence, I can answer my own questions. The grids are

1234 1234
3412 3421
2143 2143
4321 4312

Since the questions concern properties that are invariant under equivalence we can answer the questions by checking each case (not very satisfactory but there you are).

Question 1: is 4 the minimum number of clues?

Yes. Both grids can be partitioned into four unavoidable sets of size 4, e.g.

12..
....
21..
....

Each unavoidable set requires one clue, so at least 4 clues are needed.

Question 2: is there a grid with no 4 clue puzzle?

No. Both of these grids have 4 clue puzzles, e.g.

1... 1...
...2 ..2.
..4. ...3
.3.. 4...


Back to the drawing board to find a 20 clue 9x9 grid.
If the symmetry principle is correct, it may not exist. The most symmetric grid has a 19.

[Moschopulus]

I should have taken the 416-gang, not the 44-gang, when I
examined how many clues are needed for a band.

I understand the gang of 44. Every band of 3 rows is equivalent to one of 44 particular bands. And no two of these 44 are equivalent.

Can you explain where the number 416 comes from please, whenever you have time.

Also the numbers 384...448, what are they referring to?

[dukuso]

I should have taken the 416-gang, not the 44-gang, when I
examined how many clues are needed for a band.

I understand the gang of 44. Every band of 3 rows is equivalent to one of 44 particular bands. And no two of these 44 are equivalent.

Can you explain where the number 416 comes from please, whenever you have time.

Also the numbers 384...448, what are they referring to?

consider 2 bands equivalent, if one can be transformed into the
other by a sequence of
(1) permuting the 9 symbols
(2) permuting the columns in one of the stacks
(3) permuting the order of the stacks (=boxes here)
(4) permuting the 3 rows
9!*6^3*6*6 operations in total.

this gives 416 equivalence classes

if you also allow:
(5) permute the 3 cells in any of the 9 minicolumns

then you get 44 equivalence classes.
Note, that (5) doesn't necessarily give valid sudoku bands.

The number of solutions how to extend a band into a full sudoku-grid
only depends on the 44gang-class of the band.


the number of latin-subsquares, symbol-cycles, solutions, subsudokus, etc.
(all typical sudoku properties) depend just on the 416gang class
of the band.
So, these are the "isomorphismclasses" of sudoku-bands.


the 384,448... refer to Coloin's proposed method to improve
the search for a 16-clues-sudoku by comparing box-box
interaction. I haven't followed this so closely and am not sure
how useful it will be. Ask him for further explanation....


we should transfer this to the math-thread