Is there any math way to solve a Sudoku

  • Thread starter eljose
  • Start date
  • #1
492
0
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"...:rolleyes: :rolleyes: ( 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.
 
Last edited:

Answers and Replies

  • #2
NateTG
Science Advisor
Homework Helper
2,450
6
eljose said:
I didn,t know where to put this question...my doubt is if there is an exact math way to solve a "Sudoku"...:rolleyes: :rolleyes: ( 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.
 
  • #3
479
2
[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?
 
  • #4
Pengwuino
Gold Member
5,009
16
How long does it take to brute-force a Sudoku puzzle on average?
 
  • #5
479
2
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...
 
  • #6
ranger
Gold Member
1,680
1
z-component said:
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!
 
  • #7
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,950
19
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. :smile: 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). :smile:
 
  • #8
NateTG
Science Advisor
Homework Helper
2,450
6
Hurkyl said:
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). :smile:

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.
 
  • #9
1,356
2
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?
 
  • #10
Pengwuino
Gold Member
5,009
16
5-20 minutes?

I know people who can do it in 3
 
  • #11
1,090
6
Pengwuino said:
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.
 
  • #12
matt grime
Science Advisor
Homework Helper
9,420
4
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.
 
  • #13
NateTG
Science Advisor
Homework Helper
2,450
6
matt grime said:
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.
 
  • #14
matt grime
Science Advisor
Homework Helper
9,420
4
'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.
 
  • #15
NateTG
Science Advisor
Homework Helper
2,450
6
matt grime said:
'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.
 
  • #16
138
26
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.
 
  • #17
1,356
2
pengiwuino...3 mins to solve an evil sudoku( from websudoku.com)??? thats 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?
 
  • #18
Pengwuino
Gold Member
5,009
16
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.
 
  • #19
1,356
2
ah ... print some "evil sudokus" from websudoku.com and give them to your friends...See if they can finish those in 3minutes.
 
  • #20
1,090
6
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.
 
  • #21
22
0
mattmns said:
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 :approve:
 

Attachments

  • SUDOKU.PNG
    SUDOKU.PNG
    5.8 KB · Views: 441
  • #22
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
10,025
134
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.
 
  • #23
138
26
neurocomp2003 said:
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.
 
  • #24
1,356
2
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.
 
  • #25
22
0
Popey said:
No that hard at all :approve:

Actually, this was a cheat
:biggrin:
 
Last edited:

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
905
  • Last Post
Replies
4
Views
1K
Replies
1
Views
2K
Replies
6
Views
4K
Top