Is there any math way to solve a Sudoku

[eljose]

Is there any math way to solve a "Sudoku"

I didn,t know where to put this question...my doubt is if there is an exact math way to solve a "Sudoku"... ( i don,t think is necessary to explain the game isn,t it?) as far as i know Euler himself "invented" the game about 300 years ago..my question is if he did know any formula to solve any "Sudoku" or if there is a math algorithm formula or something to solve the "Sudoku" whatever is it...i am not interested in computer program to solve sudoku but a manual algorithm for their solution... thanks in advance.

 

[NateTG]

I didn,t know where to put this question...my doubt is if there is an exact math way to solve a "Sudoku"... ( i don,t think is necessary to explain the game doesn,t it?) as far as i know Euler himself "invented" the game about 300 years ago..my question is if he did know any formula to solve any "Sudoku" or if there is a math algorithm formula or something to solve the "Sudoku" whatever is it...i am not interested in computer program to solve sudoku but a manual algorithm for their solution... thanks in advance.

Sudoku's are NP-Complete. That means that there are no known easy ways to do them.

 

[z-component]

[Sudoku] was designed anonymously by Howard Garns...

(snip)

...likely inspired by the Latin square invention of Leonhard Euler...

Source: http://en.wikipedia.org/wiki/Sudoku

Not a mathematical way, but computer programs are used to find solutions using a brute force method. But what fun is that?

On another note, what does "designed anonymously by [name]" mean?

 

[Pengwuino]

How long does it take to brute-force a Sudoku puzzle on average?

 

[z-component]

I'm not sure, but like all brute forcing programs, the time depends on the speed of the processor. That Wiki article says a well-written program could be so efficient as to eliminate combinations until there's one left for each cell and then use the previous information for more eliminations. I wonder how long it'd take to solve a whole book of puzzles using the newest Intel Xeon processors...

 

[ranger]

I wonder how long it'd take to solve a whole book of puzzles using the newest Intel Xeon processors...

I'm not sure about the Xeon, but at 3 GHz a Pentium 4 can do about 600 million additions per second!

 

[Hurkyl]

Well, solving it "mathematically" is a rather vague term.

Certainly you could model the problem in a mathematical fashion. You could set it up as a linear programming problem, or a system of algebraic equations. Neither approach is likely to be efficient.

I would (essentially) set it up as a collection of boolean formulas, and run the program I've written written for the purpose of solving puzzles of this genre when (essentially) modeled as a collection of boolean formulas. Of course, most people would call it clever brute force, so *shrug*.

(And I've never tried it on sudoku, but I would expect it most to be solved rather instantly)


And a technical note: the general Sudoku problem is NP-complete. (or at least I'd believe so) The 9x9 Sudoku problem is O(1).

 

[NateTG]

And a technical note: the general Sudoku problem is NP-complete. (or at least I'd believe so) The 9x9 Sudoku problem is O(1).

It's very easy to show that it's closely related to latin square/quasigroup completion. I haven't actually seen any proof that the 'single solution only' subset is NP-complete though.

Of course the 9x9 sudoku is constant order, it's just a good sized constant.

I've seen it suggested that 9x9 sudokus will usually have a 2-field back door. So, brute force type tactics are going to be pretty effective for those.

 

[neurocomp2003]

takes 5-20 minutes to solve the advance 9x9 sudokus. There is an algorithmic method to solving it, and i consider algorithms to be mathematical
Is the brute force method people are mentioning just trying every combination?

 

[Pengwuino]

5-20 minutes?

I know people who can do it in 3

 

[mattmns]

5-20 minutes?

I know people who can do it in 3

People who can solve an advanced sudoku in 3 minutes? Go to www.websudoku.com and check out an "evil" puzzle. I would certainly like to see someone solve one of those in 3 minutes.

 

[matt grime]

Of course there is an algorithmic (mathematical) way of solving them, eljose, otherwsie they wouldn't be solvable at all. You can program it relatively easily, I'm led to believe. An interesting question is then to decide how hard a sudoku can be (minimal number of specified entries), I think 17 is the lowest bound from memory.

 

[NateTG]

Of course there is an algorithmic (mathematical) way of solving them, eljose, otherwsie they wouldn't be solvable at all. You can program it relatively easily, I'm led to believe. An interesting question is then to decide how hard a sudoku can be (minimal number of specified entries), I think 17 is the lowest bound from memory.

The number of entries is not strongly related to how difficult a sudoku is to solve. Supposedly many of the 17 entry sudokus are fairily easy to solve.

 

[matt grime]

'hard' or otherwise is a purely subjective opinion. Every sudoku is exactly as hard as anyother in some sense; some are just quicker to solve than others. I was purely using 'hard' to refer to the number of starting entries.

 

[NateTG]

'hard' or otherwise is a purely subjective opinion. Every sudoku is exactly as hard as anyother in some sense; some are just quicker to solve than others. I was purely using 'hard' to refer to the number of starting entries.

Well, there are, of course, unsolvable sudoku which are clearly harder to complete than solvable ones.

Generally, 'harder' refers to the techniques that would be communly used to solve the sudoku, rather than the number of starting cells.

 

[pi-r8]

I've actually written a computer program for solving sudokus. All it does is keep track of all the possible numbers that could be in a space, and eliminate them one by one until only one is left. It runs almost instantaneously, and as far as I can tell it solves all but the very toughest sudokus, which I think will require a guess at some point.

 

[neurocomp2003]

pengiwuino...3 mins to solve an evil sudoku( from websudoku.com)? that's nuts...i gues they ain't watching tv while doing it.

Pi-r8...none of the tougher sudoku's require a guess.Sometimes you must apply a "pigeonhole"(or rather n in n boxes technique)...which might be tough to code...my best guess would be to code for a bipartition.
Another technique is to simulate chess like strats for each # separately.

what does 17 entries mean? on a 9x9?

 

[Pengwuino]

No it's not "evil sudoku", its just the ones they print in our universities newspapre and its only the MW ones that aren't that hard.

 

[neurocomp2003]

ah ... print some "evil sudokus" from websudoku.com and give them to your friends...See if they can finish those in 3minutes.

 

[mattmns]

Yeah, anyone can solve the easy puzzles in a few minutes.

And neurocomp, I think the 17 is referring to the number of entries given at the start of a puzzle.

 

[Popey]

People who can solve an advanced sudoku in 3 minutes? Go to www.websudoku.com and check out an "evil" puzzle. I would certainly like to see someone solve one of those in 3 minutes.

No that hard at all

 

[arildno]

As for sudoku "hardness", my subjective opinion is the following:
The longer the chain of reasoning must be in order to eliminate a particular choice, the "harder" is the sudoku. (and also, the number of possible branches you need to consider)

Of course, one might say that sudokus aren't hard at all, they merely require patience of you.

 

[pi-r8]

Pi-r8...none of the tougher sudoku's require a guess.Sometimes you must apply a "pigeonhole"(or rather n in n boxes technique)...which might be tough to code...my best guess would be to code for a bipartition.
Another technique is to simulate chess like strats for each # separately.

I'm not sure what you mean by pigeonhole, or n in n boxes. Is it something like noticing that there's only two places a number can go, so you try one and see if it leads to a contradiction? Because that's what I mean by guessing. I'm sure I could code that with a selfreferencing function, but it's been a while since I've used one of those so I've kind of forgotten how.

 

[neurocomp2003]

no... if you have 157*15*17*147*489...in a row/column/3x3 box...
then you know that the 4 goes in the box with 147...because
of teh n in n boxes(n=3 in this case) 157*15*17...
this would be harder to code for but if you keep track of what goes in a row and column then you can.

 

[Popey]

No that hard at all

Actually, this was a cheat

 

[Nimz]

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.

 

[mattmns]

I thought each Sudoku, by defintion, has a unique solution?

 

[shmoe]

A unique solution is usually one of the conditions for it to be a sudoku. However, if you were to write a program that's 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)..

 

[davidecullen]

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

 

[mathman]

I thought each Sudoku, by defintion, has a unique solution?

Try the soduko I posted previously in this thread. It has three solutions.

 

[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.