Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is there any math way to solve a Sudoku

  1. Mar 14, 2006 #1
    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: Mar 14, 2006
  2. jcsd
  3. Mar 14, 2006 #2

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Sudoku's are NP-Complete. That means that there are no known easy ways to do them.
     
  4. Mar 14, 2006 #3
    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?
     
  5. Mar 14, 2006 #4

    Pengwuino

    User Avatar
    Gold Member

    How long does it take to brute-force a Sudoku puzzle on average?
     
  6. Mar 14, 2006 #5
    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...
     
  7. Mar 14, 2006 #6

    ranger

    User Avatar
    Gold Member

    I'm not sure about the Xeon, but at 3 GHz a Pentium 4 can do about 600 million additions per second!
     
  8. Mar 14, 2006 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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:
     
  9. Mar 14, 2006 #8

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  10. Mar 14, 2006 #9
    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?
     
  11. Mar 15, 2006 #10

    Pengwuino

    User Avatar
    Gold Member

    5-20 minutes?

    I know people who can do it in 3
     
  12. Mar 15, 2006 #11
    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.
     
  13. Mar 15, 2006 #12

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  14. Mar 15, 2006 #13

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  15. Mar 15, 2006 #14

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    '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.
     
  16. Mar 15, 2006 #15

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  17. Mar 15, 2006 #16
    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.
     
  18. Mar 15, 2006 #17
    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?
     
  19. Mar 15, 2006 #18

    Pengwuino

    User Avatar
    Gold Member

    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.
     
  20. Mar 15, 2006 #19
    ah ... print some "evil sudokus" from websudoku.com and give them to your friends...See if they can finish those in 3minutes.
     
  21. Mar 15, 2006 #20
    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Is there any math way to solve a Sudoku
  1. Solve any equation! (Replies: 4)

Loading...