Is there any math way to solve a Sudoku

[mathman]

(Note: I had posted it on another thread about Sudoku - here it is)

For those interested in sudoku anomaly, I hit upon a sudoku puzzle (evil from the website mentioned by rachmaninoff) that has 3 solutions.

xxx 9xx 547
xx3 17x xxx
xxx xxx 1xx

x3x xxx x52
xx4 x6x 7xx
15x xxx x9x

xx1 xxx xxx
xxx x27 6xx
865 xx9 xxx

It is evil puzzle 7,520,432,503.

 

[davidecullen]

Unique Solutions

Obviously it is possible to set puzzles that don't have a single unique solution. There are many discussions on the internet regarding whether or not these are valid puzzles. Personally I don't think they are as the whole point of a puzzle is for you to reach a single solution. If you take it to the extreme you can say that a completely empty board is a valid Sudoku puzzle with rather a lot of solutions. I have come across a few sites that present puzzles with multiple solutions. I can only think that the reason for this, is the computing time required to check. Websudoku claims to have billions of puzzles. It is very fast for a computer program to solve a single sudoku puzzle for a single solution, but it gets very slow to check all possible combinations in order to ensure that there is no second solution. It would have taken websudoku rather a long time to generate billions of puzzles that definitely have just one unique solution. On my site I only present puzzles with a unique solution. My generator program produces less than a thousand puzzles in 24 hours when it's checking for uniqueness. At that rate it would take me nearly 3000 years to produce as many puzzles as websudoku.

Regards,
Dave
dave@sudokuoftheday.co.uk
http://www.sudokuoftheday.co.uk

 

[mattmns]

A month ago I was working a sudoku from the paper, and the issue of uniqueness came up in the logic in what I thought was an interesting way.

There was the following (sorry for how bad this will look):

(139)**|***|**(39)
(39)**|***|**(39)
***|***|***
...

That is, the top left corner could be a 1, 3, or 9, top right corner could be 3, or 9, etc. Rest don't matter.

Now, if we can assume the solution is unique then we know that the top left has to be a 1. Why? Assume the top left was not a 1, then there would be two solutions (flipping the 3's and 9's), but we assumed there was a unique solution. In "real" (unique) sudoku we could assume this, but in non-unique sudoku this is useless. I just thought that it was interesting

 

[chronon]

Although NP complete problems seem to require exponential time in the worst case, in practice many are solvable fairly quickly. For example I wrote a Boolean formula applet , solving SAT3 with 26 variables. This generally takes 100- 200 steps rather than 2^26

 

[MeJennifer]

Did anybody made some 3D or higher D problems?

 

[buddyholly9999]

FYI: June 2006 issue of Scientific American has an article titled "The science behind suduko". Just putting it out there.