gfroyle wrote: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.

dukuso wrote: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.

dukuso wrote: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.