Is there any math way to solve a Sudoku

  • Thread starter eljose
  • Start date
  • #26
81
0
http://www.javaonthebrain.com/java/sudokuspoiler/ has a program in java that solves sudokus very quickly. I placed the numbers from one of those evil puzzles into the spoiler, and it reported that it took 15 milliseconds to solve.

The spoiler on that website only tells you one possible solution, though. If there are multiple solutions, it apparently takes the first one it finds. Although it doesn't mention that there may be multiple solutions, it will state when there is no solution.
 
  • #27
1,090
6
I thought each Sudoku, by defintion, has a unique solution?
 
  • #28
shmoe
Science Advisor
Homework Helper
1,992
1
A unique solution is usually one of the conditions for it to be a sudoku. However, if you were to write a program thats trying to solve one inputed by a user you don't begin with a guarantee that this is the case. Rather than try to list them all if the input allows multiple solutions, it would be simpler to put out the first solution found (listing them all would be impossible in some cases, it will actually take an empty board as input)..
 
  • #29
Sudoku

The better algorithms for solving sudoku on computers use
a combination of logic together with brute force, when the logic
can no longer get any further.
I use that technique in mine, so that I can provide a single step
help function that follows normal reasoning at least for all the easier
puzzles, that can be solved by straight logic.

Dave
http://www.sudokuoftheday.co.uk
 
  • #30
mathman
Science Advisor
7,955
498
I thought each Sudoku, by defintion, has a unique solution?

Try the soduko I posted previously in this thread. It has three solutions.
 
  • #31
mathman
Science Advisor
7,955
498
(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.
 
  • #32
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
 
  • #33
1,090
6
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 :smile:
 
  • #34
498
0
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
 
  • #35
2,000
5
Did anybody made some 3D or higher D problems?
 
  • #36
FYI: June 2006 issue of Scientific American has an article titled "The science behind suduko". Just putting it out there.
 

Related Threads on Is there any math way to solve a Sudoku

  • Last Post
Replies
4
Views
2K
Replies
3
Views
2K
Replies
5
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
13
Views
906
  • Last Post
Replies
4
Views
1K
Replies
1
Views
2K
Replies
6
Views
4K
Top