Sudoku solving with matricies and/or diophantine equations

[Jonny_trigonometry]

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 let's me solve the problem...

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.

 

[EnumaElish]

I remember seeing a lengthy thread on this game in these forums -- unless it was another game but I couldn't tell the difference.

 

[benorin]

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

http://www.dkmsoftware.com/sudoku/

 

[Jonny_trigonometry]

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.

 

[hypermorphism]

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.

 

[fourier jr]

look i dug up a old sudoku thread rather than start a new one of my own!


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.

 

[Sartak]

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.

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.

 

[neurocomp2003]

www.websudoku.com

 

[rachmaninoff]

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.

 

[Hurkyl]

Even for the hardest sudokus you don't have to make any "assumptions". You can solve these with strictly positive statements.

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

 

[0rthodontist]

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.

 

[bao_ho]

http://www.frontiernet.net/~fys/hugi/hcompo.htm

 

[neurocomp2003]

rachiminoff: it isn't a question of "how to solve it" its a question of "how fast you can solve it"

 

[forest]

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?

 

[mathman]

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.

 

[Nimz]

In case anyone is interested, the June 2006 issue of Scientific American has a Sudoku article.

 

[Tzar]

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?

 

[rcgldr]

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

sudoku.htm

 

[rcgldr]

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?

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

 

[shelly88]

In case anyone is interested, the June 2006 issue of Scientific American has a Sudoku article.

Well I am 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.

 

[SW VandeCarr]

Here's a paper out of the California Institute of Technology entitled "Iterative Decoding for Sudoku and Latin Square Codes" which (the authors claim) presents a new class of erasure-correcting codes.

http://leecenter.caltech.edu/workshop08/papers/mceliece2.pdf

 

[Ben1220]

I think I have heard that solving a suduko is an NP problem, is this true? Perhaps this would explain why creating good suduko solving program is difficult.

 

[SW VandeCarr]

.

http://leecenter.caltech.edu/workshop08/papers/mceliece2.pdf

Ben1220

The above paper proposes an algorithm (Sec 4) which contains conditional statements (Def 2). Therefore you could say it's an NP problem (non-deterministic Turing Machine), but there's no reason, I would think, that it couldn't be a P (deterministic Turing Machine) problem given there exists a unique solution for a given puzzle. After all, if the algorithm works, then you've identified a deterministic Turing Machine solution.

 

[Hurkyl]

P isn't "solvable by deterministic TM". P is "solvable by deterministic TM in polynomial time".

 

[SW VandeCarr]

P isn't "solvable by deterministic TM". P is "solvable by deterministic TM in polynomial time".

I know. I wasn't attempting to give a full definition. I just wanted to be clear about the relevant distinction between P and NP in this context. In any case, do you agree that Sudoku type puzzles with unique solutions are really P, not NP?

 

[Hurkyl]

In any case, do you agree that Sudoku type puzzles with unique solutions are really P, not NP?

I would be surprised if it were P. But it's not something I know for sure.

 

[bpet]

I would be surprised if it were P. But it's not something I know for sure.

Since there's always less than (9!)⁹ possibilities to test wouldn't that make it O(1)?

 

[Hurkyl]

Since there's always less than (9!)⁹ possibilities to test wouldn't that make it O(1)?

I assumed we're talking about generalized sudoku, with an NxN grid of NxN squares.

 

[ygolo]

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

sudoku.htm

This is a pretty brute force method. It simply stores all possibilities in the open squares, loops over all the solved squares, eliminating the number in the solved squares from the appropriate open squares, then loops over the open squares to see if they can then be moved the solved square category (when only one possibility remains). This process is just repeated till all the squares are solved.

If a human attempted this method, it would turn an already tedious class of puzzles even more tedious.

I think it would be interesting to restrict viable algorithms to the use of only 7 position-number pairs available in "working memory," forcing the rest to be done on "paper."

In other words, pretend your machine only has 7 registers with three 3-bit fields in each register (nominally the x-pos, the y-pos, and a number--but can be used for other purposes). If it needs more memory, it will have to write out the data onto "paper", and the address (in a indirect addressing mode) of the "paper data" will need to be kept in one of the 7 registers available.

You can design both the algorithm, and the instruction-set for the machine. But the instructions cannot "cheat" by implicitly using more memory (I.O.W if the instruction were represented as a circuit, it would have no feedback. The input and output would be a register ("working memory") or indirectly addressed memory ("paper").)