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

Sudoku solving with matricies and/or diophantine equations

  1. Oct 30, 2005 #1
    I was wondering if there is a way to solve these puzzles with matricies and/or diophantine equations:

    http://www.sudoku.com/

    If you define the basis as nine orthogonal vectors, and input the given initial values to the corresponding places in a 9X9 matrix, and also brake it up into 9 3X3 matricies, and also use the fact that the cross product of all values in each 3X3 matrix (amongst themselves) = 0, and also the cross products in the set of values in each column and row of the 9X9 matrix = 0. could you find a way to solve the puzzle for uniquie values using linear algebra?

    You could also approach it with a set of diophantine equations. In the 9X9 matrix, the set of values in each row and column must add up to 45, and also the values in each 3X3 matrix must add to 45.

    I just can't put these ideas together in a way that lets me solve the problem... :cry:

    the reason why I put it in this section is because I think there is some combinatorical apporach too. Maybe I should've put it in a different section.
     
    Last edited: Oct 31, 2005
  2. jcsd
  3. Oct 31, 2005 #2

    EnumaElish

    User Avatar
    Science Advisor
    Homework Helper

    I remember seeing a lengthy thread on this game in these forums -- unless it was another game but I couldn't tell the difference.
     
  4. Nov 2, 2005 #3

    benorin

    User Avatar
    Homework Helper

    Go to this web site for a free online interactive version of this sudoku game:

    http://www.dkmsoftware.com/sudoku/
     
  5. Nov 2, 2005 #4
    I've tried figuring this out, and I'm going to conclude that there is no way to solve these things analytically, and you have to use a guess and check method. I got to the point where you need at least 54 equations to simultaneously solve.
     
  6. Nov 2, 2005 #5
    The long method (just putting all possibilities within each box and seeing where one number is unique) doesn't involve any guessing. You can write a computer program to solve these.
     
  7. Jan 1, 2006 #6
    look i dug up a old sudoku thread rather than start a new one of my own! :biggrin:


    i looked at it as some sort of 'rook problem'; think of each number as a rook on a 9x9 chessboard. that means you want to have exactly one number from 1..9 in a given row/column, just like placing 9 rooks on a 9x9 chessboard in a way that makes it impossible for them to attack each other. it's like you've got 9 colours, and 9 rooks of each colour (there are 9 1s, 9 2s, etc), and any given column & row must have exactly one rook of each colour in it. then figure out a way to put all 81 of them onto a chessboard so that rooks of the same colour can't attack each other. that's sudoku. what i usually do is start with all the 1s (it doesn't matter where you start of course) put a 1 in each 3x3 "square", paying attention to whether or not a given row/column already has the same number in it. that way it's easy to narrow down what slots i can't place the number in.
     
  8. Jan 25, 2006 #7
    Of course, this method (simple elimination) only works for the easiest Sudoku boards. Harder boards require more complex methods. One such method is assuming a tile to be one of its possibilities and then continuing on until you reach a contradiction.
     
  9. Jan 25, 2006 #8
  10. Jan 26, 2006 #9
    Even for the hardest sudokus you don't have to make any "assumptions". You can solve these with strictly positive statements.

    For example, go to www.websudoku.com, and select "Evil", and choose the seed 6,388,359,848 (that's what I got randomly). Just starting in the leftmost column - 12379 are used, so the remaining numbers must be precisely 4568. Two of these are in the lower-left box - which already has 2578 in it (ruling out 5 and 8!); thus the bottom two squares of the left column must be 4 and 6 in some order. But the second-lowest row already has a 4 - so the order must be 6, then 4 (going down).

    You never have to make guesses if the sudoku has a unique solution.
     
    Last edited by a moderator: Jan 26, 2006
  11. Jan 26, 2006 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    True -- you can solve all Sudokus with positive statements, if you know all the theorems of the form "If this is the initial problem, then that is the solution!"

    But that's entirely useless from a practical point of view. :tongue: On harder ones, you're generally going to have to make deductions of the form "If I place a 2 there, then blah, then blah, then there's nothing that can go in that other square!" and such.
     
  12. Jan 26, 2006 #11

    0rthodontist

    User Avatar
    Science Advisor

    This is the first problem in the course on Artificial Intelligence at my school. Unfortunately I haven't taken the course so I can't help you. But that's the subject area.
     
  13. Jan 28, 2006 #12
  14. Jan 28, 2006 #13
    rachiminoff: it isn't a question of "how to solve it" its a question of "how fast you can solve it"
     
  15. May 3, 2006 #14
    I've tried working out the total number of possible sudoku puzzles there are. It didn't occur to me to use orthagonal vectors to solve it. I thought of matricies, but they didn't seem promising.

    I seemed to be getting somewhere with factorals, but soon found the whole thing could not be easily solved using factorals alone.

    I then created a smaller "sudoku," 4X4 with 4 2X2 boxes. I haven't yet found fime to eplore this "sudoku," but it should be easier to work with.

    I'm thinking of using 4!^2 as the possibilities without any limitations. Then, for example, subract permutations of the possibilities that don't work.

    Any ideas?
     
  16. May 9, 2006 #15

    mathman

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  17. May 24, 2006 #16
    In case anyone is interested, the June 2006 issue of Scientific American has a Sudoku article.
     
  18. Jun 8, 2006 #17
    The main problem of tyring to solve sudoku through matrices is the fact that the solution needs only to contain numbers 1 through to 9. This restriction can't be expressed in matrix form, I think.... OR can anyone think of a way of doing that?
     
  19. Jun 9, 2006 #18

    rcgldr

    User Avatar
    Homework Helper

    This site has a sudoko solver that explains in detail all the rules used to solve the puzzles.

    sudoku.htm
     
  20. Jun 9, 2006 #19

    rcgldr

    User Avatar
    Homework Helper

    Back in the days when I used APL (A Programming Language), a common method was to setup a multi-dimensional object, where the indices were the values, and every location was initially set to a 1. Then as known facts were applied, sub-sets of the tensor (the APL name for multi-dimentional objects) were zeroed out. After all known facts from the puzzle were input, then deductive logic algorithms were applied to continue zeroing out sub-sets.

    In this case, you'd start off with a 3 dimensional 9x9x9 "tensor" with a 1 in every location, the last dimension would represent the values 1 thorugh 9 for each of the 81 squares of Sodoku. Then start replacing 1's with 0's based on known facts, the rules of Sudoku, and deductive algorithms until you were left with only a single 1 in each of the 81 vectors representing the values 1 through 9 for each box of the puzzle. For APL, this method was common, as it was easier to deal with multi-dimensional objects than variable sized sets of numbers.

    I did a similar thing for solving deductive reasong puzzles, like "who owns the zebra and who drinks the water", although I never implemented an algorithm for X is "next to" Y (I would handle these manually).
     
    Last edited: Jun 10, 2006
  21. Nov 27, 2009 #20
    Re: Sudoku

    Well im interested howver you didn't post a link to this article, I realize this is an older thread but does anyone by chance have it? This is a very intersting discusion btw, just thought I'd pop in and say hello to everyone.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Sudoku solving with matricies and/or diophantine equations
  1. Problem Solving (Replies: 0)

  2. Solve this? (Replies: 3)

Loading...