The New Sudoku Players' Forum

[dukuso]

>Unfortunately i dont have the time to try this myself,
>so i just want to post my idea, how you could determine,
>if a given grid contains a 16 clue sudoku:

>Three numbers in the grid define a "subsudoku". You have
>only 27 cells and three numbers. Looking at three subsudokus
>(with all 9 numbers then), there must be at least two of
>them with maximum 7 clues for a 16 clue sudoku of the whole grid.
>There are about a million possibilities for up to 7 clues
>for a subsudoku.

and we have about 100000 equivalence-classes of "3-subsudokus"

>It should be possible to check for all
>of them (in short computing time), which lead to a unique
>subsudoku. Save them. Do the same for the other two subsudokus.
>For at least two of them you now have a list of subsudoku
>clues (hopefully not more than thousands). Now combine
>each two of two lists and verify, if they solve the 6
>numbers subsudoku uniquely. If so, save the clues (and
>forget the rest).
>With those ones now, reduce the 27 clues of the third
>subsudoku (with a backtracking algorithm) to a minimum.
>If there is a 16 clue, you should find it this way.
>Of course i know, this is not a big help to find a 16 clue,
>but just a way to eliminate many grids.


how do you separate the 3 subsudokus ? They are only
there when you have the full grid.
When you just see the 16 clues, you don't know which of the
81 cells go into which of the subsudokus.

Their cells are given primarily by the positions of the
clues with one of the 3 numbers making the subsudoku,
but also by the other clues, which may not be included
in that region. Once you are given the partition
of the full grid into 3 subsudokus of 27 cells,
then it's much easier to solve and you need fewer clues,
of course.

We could just consider 2 colors of clues, those having 1,2,3 (say)
and the others. Would they uniquely determine the 27 cells
of the 1,2,3-subsudoku ? Consider 7 positive and 9 negative clues.
Can we find lots of configurations which determine the
class uniquely ? And use them as a base to extend into a 16-sudoku ?

[coloin]

I have been trying with little success to fill in 16 clues.

I have been using one of Gfroyles grids.
Initially I tried to do it in two stages:
1. Solve the grid with respect to an approximation of 5*10^9 essentially different grids - this was done empirically with 9! in a box and 72^2 covered with a couple of hints. Hopefully do it in 13 clues !
2.Remove these clues and extra clues not needed due to pairs. Add three more clues to solve the grid to the 6*10^21! . Easy .

However it didnt work - the inherent problem is that each clue is only of a specific value in terms of low solution rate when it is taken with all the clues already present. If you remove a single clue - all the potential advantages of any remaining clue get wiped !

There are a high number of solutions - too high - right up to the last two or three clues.

If we were able to catalogue all the 5*10^9 grids and determine which were the most valuable [minimal] clues for each clue position we might be able start off and complete the first stage. Unfortunatly the size of this file [10Gbyte ?] precludes analysis.

Would a reduced random sample of the 5*10^9 be representative ?

Is it possible to add up these numbers or calculate solution rates wrt this sample ?

What sort of variation is there in clue frequency early on in the grid compilation ? 0.5%- 10% for each clue position ?

I have found that a clue tends to reduce solution rates by 9 fairly easily - but towards the completion of the grid - a reduction by 12 is common. In 17 grids a particular clue may have final "value" ranging from x10 - x200000 solution reduction.

The first clue picked determines the second and so on .........and it will be that a particular combination of three or more clues is particularly good.

Darn difficult

[Wolfgang]

and we have about 100000 equivalence-classes of "3-subsudokus"

Not more? How much of them need less than 7 clues to be unique (any 16 clue sudoku can be split into 3 3-subsudokus with maximum 6 clues [Edit:] - if there are not 5 clues of one number)?

[Wolfgang]

Made a quick hack now to check a few 3-subsudokus for being unique with 2 clues. I took them out of 4 of the 17-clues and 4 "normal" sudokus. The first number is, how much of the 96 3-subsudokus are not unique with 2 clues, the second is, how much pairs of 2 clues at all in the sudoku make a subsudoku unique:

gfroyles 1,1000,19197,2002 (btw 2000 and 2001 seem to have no solution)
31/3396, 42/4056, 50/3073, 32/3073

4 others:
44/2877, 32/2700, 54/2700, 50/2121

If this is characteristic in general, i would assume that full grids with more than 3000 2-clues for the 3-subsudokus are better candidates for low clue sudokus than others.
Cant do more myself to verify it (my hack is terrible slow)
[Edit:] Due to another old hack line the numbers above are not quite correct (but 2000 and 2001 are). I had hoped the pairs could give me a good heuristic for full grids, but after looking at one closer i dont have a good idea.

[Moschopulus]

Made a quick hack now to check a few 3-subsudokus for being unique with 2 clues.

Just to clarify, when you say "3-subsudoku" you mean the 27 cells which are all the cells containing 3 given digits.

Are you choosing 2 clues from these 27? And how many clues in total? 56? Are you choosing these 2 and all other cells? And then you are seeing if there is a unique solution?

Your plan might find a 16 clue puzzle, but it won't prove that a grid does not have a 16, am I right?

By the way, I don't like the term "subsudoku" here since a subsudoku should be a sudoku by itself, but these are not. Perhaps call it the 138-set if the digits are 1,3,8, or something like that.

[Pappocom]

The term I use for the set comprising all the (say) 3s in a solution is rookery - since rooks sitting on power lines will always (I understand) spread themselves out to keep their space.

So, a grid in Classic Sudoku consists of 9 mutually-exclusive rookeries.

- Wayne

[gfroyle]

gfroyles 1,1000,19197,2002 (btw 2000 and 2001 seem to have no solution)
.

What do you mean by "have no solution"? Do you mean that you think that they are not valid Sudokus because they have no completions? If this were true, it would be a very serious bug in my programs...

Could you actually post the grid that concerns you, because I have checked all the ones that i have posted online and as far as I am concerned, they are all OK.

Thanks

gordon

[angusj]

gfroyles 1,1000,19197,2002 (btw 2000 and 2001 seem to have no solution)

If you're referring to the puzzles here - http://www.csse.uwa.edu.au/~gordon/sudoku17 - then puzzles 2000 & 2001 seem fine to me.

[Wolfgang]

gfroyles 1,1000,19197,2002 (btw 2000 and 2001 seem to have no solution)
.

I had already edited my post above, had found the bug in my program.

[dukuso]

The term I use for the set comprising all the (say) 3s in a solution is rookery - since rooks sitting on power lines will always (I understand) spread themselves out to keep their space.

So, a grid in Classic Sudoku consists of 9 mutually-exclusive rookeries.

- Wayne

not exactly rooks, since we also have the blocks-constraint.
Can't we create a name for a (fairy)chess-like piece which moves
along rows,columns,blocks ?

maybe sudoku-hopper or sudoker or such ?
other suggestions...

[Wolfgang]

Just to clarify, when you say "3-subsudoku" you mean the 27 cells which are all the cells containing 3 given digits.

Are you choosing 2 clues from these 27? And how many clues in total? 56? Are you choosing these 2 and all other cells? And then you are seeing if there is a unique solution?

yes

Your plan might find a 16 clue puzzle, but it won't prove that a grid does not have a 16, am I right?

By the way, I don't like the term "subsudoku" here since a subsudoku should be a sudoku by itself, but these are not. Perhaps call it the 138-set if the digits are 1,3,8, or something like that.

With Pappocoms notation i would call it a 3-rookery. You have 84 of them in a full grid. The clues of each 3 numbers (1,2,3 up to 7,8,9) in every unique sudoku neccessarily make each 3-rookery unique.
But if you combine all clues that are sufficient for the 84 3-rookeries, this is not sufficient for the whole sudoku to be unique.
My first plan was to prove for many grids that already the 3-rookeries would need too much clues, but in the meantime i realised that this is too time consuming for the most grids.
My second plan was to look for few clues for all the 3-rookeries, which should be easier than to find those clues for the whole grid, and take them as a basis for a low clue sudoku. Eg in the 17-clue i looked at, 15 of the clues are necessary for making all 3-rookeries unique.
But i did not investigate that further. It could also be possible that you find only 10 clues for all 3-rookeries, but the minimum sudoku still requires 20 clues.

[dukuso]

isn't it 84 , not 96 ? (9 choose3)


I think, the idea with the rookerys looks promising.

Or would look promising, if there were a 16s...

[Wolfgang]

isn't it 84 , not 96 ? (9 choose3)

Yes of course, thanks

[Moschopulus]

I check equivalence by forming the following graph.

81 vertices representing the 81 positions.
One vertex for each row, joined to the 9 positions in its row
One vertex for each col, joined to the 9 positions in its col.
One vertex for each horizontal block, joined to the three row vertices in that block.
One vertex for each vertical block, joined to the three column vertices in that block.
One vertex representing "horizontal" joined to the three vertices representing horizontal blocks.
One vertex representing "vertical" joined to the three vertices representing vertical blocks.
One base vertex joined to the two "direction" vertices [actually, this is superfluous now I think about it!]

9 vertices representing symbols, each joined to a position vertex if that position contains that symbol.

What do unavoidable sets look like in this graph?
Can I find them with nauty?

[evert]

Is it true that any puzzle - if it has next grid as unique solution:

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;

has at least 18 clues?

For example at least 2 clues must be in the group

Code: Select all

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

in the upper horizontal band.
Otherwise they can be exchanged in the solution of the puzzle.
And there are 9 of these groups.

Probably it has been mentioned somewhere here and I missed it.