What's thу quick way to find that there is no solutions?

Everything about Sudoku that doesn't fit in one of the other sections

What's thу quick way to find that there is no solutions?

Postby george k » Sun Jul 15, 2007 5:28 pm

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
george k
 
Posts: 4
Joined: 05 January 2007

Postby daj95376 » Sun Jul 15, 2007 6:48 pm

Given your example, it appears that you need to implement checks for an invalid grid. After two Hidden Singles in <9>, you get [b9]<>9 invalid!

Code: Select all
*-----------------------*
| 1 . . | . 2 . | . . 4 |
| . . . | 9 . . | . . . |
| . . . | . 3 . | 9 . . |
|-------+-------+-------|
| . 2 . | . . . | . . . |
| 5 . . | . 1 . | . . 2 |
| . . . | . . . | . 5 . |
|-------+-------+-------|
| . . 9 | . . . | . . . |
| . . . | . . 9 | . . . |
| 6 . . | . 4 . | . . 1 |
*-----------------------*

r1c2    =  9     Hidden Single
r5c8    =  9     Hidden Single

Pass Y:   <9>    Templates      0
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ab » Sun Jul 15, 2007 9:37 pm

This is a wild guess but what happens to your recursion algorithm when it finds a cell with no candidates? I reckon that's what's happening here and it's causing problems for your program.
ab
 
Posts: 451
Joined: 06 September 2005

Re: What's thу quick way to find that there is no solutions

Postby ravel » Mon Jul 16, 2007 7:19 am

george k wrote:I'm trying to proove practically that 17 is the minimum number of opened cells allowing to find unique solution.
What do you mean with proving practically ? If you mean, that you want to try all 16 clues combinations (the possibilities to reduce them are very restricted), one life will not be enough.
At the time it is not even completely proved, that a 10 cell sudoku cant be unique. Maybe you should start here.

See here for published source of DLX solvers. Also gsf's sudocoup is extremely fast (but i am missing a download link now).
ravel
 
Posts: 998
Joined: 21 February 2006

Postby george k » Mon Jul 16, 2007 9:19 am

Yes, I want to try all 16 clues, but my method is not brutal force. I know how to reduce the amount of combinations and how to parallelize the computations so the combination explosion will not be so terrible:) . I do hope it is efficient. I hope that there are lots of people, who'd agree to leave their computer working all night long to find out 16-clue sudoku or help to proove that there is no one. By the way, if it is prooved, no 10-clues-correct sudoku can be found.
So now I'm trying to determine correct algorithm and later it will be published.
Thank you for the links!
george k
 
Posts: 4
Joined: 05 January 2007

Postby ravel » Mon Jul 16, 2007 9:23 am

george k wrote:By the way, if it is prooved, no 10-clues-correct sudoku can be found.
I dont understand. There is already a proof for 10-clues ?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby george k » Mon Jul 16, 2007 9:25 am

ab wrote:This is a wild guess but what happens to your recursion algorithm when it finds a cell with no candidates? I reckon that's what's happening here and it's causing problems for your program.

When it finds no candidates it stops.
There were no explicit grid validation, but now I'm implementing ZeroSolutionsValidation and hope this will help to increase the speed.
george k
 
Posts: 4
Joined: 05 January 2007

Postby george k » Mon Jul 16, 2007 9:31 am

ravel wrote:
george k wrote:By the way, if it is prooved, no 10-clues-correct sudoku can be found.
I dont understand. There is already a proof for 10-clues ?

No there is no, but if no-existanse of 16-clues sudoku proved, no-existanse if 10-clues sudoku will be proved automatically.
george k
 
Posts: 4
Joined: 05 January 2007

Re: What's thу quick way to find that there is no solutions

Postby Havard » Mon Jul 16, 2007 6:23 pm

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
Havard
 
Posts: 377
Joined: 25 December 2005

Postby coloin » Tue Jul 17, 2007 6:04 pm

Nice try Havard !

I think all 16 clue attempts have been either multisolution or invalid [by definition]

With only 7 of the 9 clue numbers this will reveal one or several [2-clue] unavoidable sets in the 18 spaces envolving the other 2 rookeries. Similarly the lack of a clue in two rows in a band reveals another 18 clue unavoidable[s] envolving those 18 spaces of the 27 spaces in the band.

At any rate for inserting 16 clues most [? 95%] of the time you will get at least 8 clue numbers and cover all the [18] doublerows in the 6 bands. perhaps.

Having said that I think your estimate is close !

Heres mine

Number of ways to insert 16 clues from a valid grid = 81!/[81-16]! * 1/16!
Number of esentially different grids = 5*10^9
Average number of grid solutions for 16 clues = approx 4 million [range 2 - billions]


Number of essentially different ways to fill in 16 clues =

[3*10^16] * [ 5 *10^9] / [ 4*10^6] = approx 4*10^19

C
coloin
 
Posts: 1662
Joined: 05 May 2005


Return to General