george k wrote:Hi everyone.
I'm trying to proove practically that 17 is the minimum number of opened cells allowing to find unique solution. I've invented a method, which allows to reduce the number of variants.
From time to time my genereator generates 16-cells sudoku, that doesn't have any solutions, however prooving this fact leads to explosion of combinations.
My program uses recursion, when it can not apply any other non-recursive methods. So when sudoku has tones of solutions, the program detects this very quickly and stops. Sudokus with no solutions makes too much recursive calls.
How to reduce it?
Programm finds the empty cell with the minimum candidates and starts the recursion.
THe example of sudoku with no solutions:
- Code: Select all
1 0 0 0 2 0 0 0 4
0 0 0 9 0 0 0 0 0
0 0 0 0 3 0 9 0 0
0 2 0 0 0 0 0 0 0
5 0 0 0 1 0 0 0 2
0 0 0 0 0 0 0 5 0
0 0 9 0 0 0 0 0 0
0 0 0 0 0 9 0 0 0
6 0 0 0 4 0 0 0 1
This is better left to math-people, but it could be interesting to see what you are up against here.
I though I would try to use a simplified template-perspective.
Keeping in mind that no two rows or columns in a chute can be left empty in a template, any legal template would first have to make sure this rule is followed. The least clues that can achieve this is 6:
- Code: Select all
X . . | . . . | . . .
. . . | . X . | . . .
. . . | . . . | . . .
---------------------
. . . | X . . | . . .
. . . | . . . | . X .
. . . | . . . | . . .
---------------------
. . . | . . . | X . .
. X . | . . . | . . .
. . . | . . . | . . .
Now no chute has two empty rows or columns.
if we make the (very simplified and wrong, but if anything careful) assumption that every sudokutemplate that is valid, has to be able to be reduced to this particular 6-clue template, then we get (81-6)! / (81-16)! = 3,0 * 10^18 possible ways of placing our reminding clues in the template.
Of course, 6^8*2 of these are equivalent, so really there are about
9,0 * 10^11 different 16 clue templates available to us. (sorry for this very crude maths, I am sure the math guys (RedEd?) will give you the exact number!)
Now for filling in the numbers! If we first fix the first 8 numbers in the 16 clue template(1 to 8), we can still place 8 numbers in any combination between 1 and 9 in the remaining template cells, or 9^8 = 43,046,721 combinations, that will give you a cool total of 3,6 * 10^18 different combinations to check for.
Now gfs' solver is the fastest I know of, and he can do roughly 5000 puzzle-checks per second. Now, that means that checking all 16 puzzles would take around 7 * 10^14 seconds, or about 22 million years...
Of course this example is full of holes, but I would be interested if you could explain how you can reduce the number of possibilities with a lot more, since 10 years probably won't do you any good either.
I would also be interested to see an actual proper calculation of the same problem! How many different 16 clue "valid" (no obvious errors, like two empty rows in the same band) are there?
Havard
