Has anyone noticed that the sudoku puzzles can be thought of as a problem in linear diophantine equations? Namely let the unkowns x_ijk be the "amount" of "color" k in cell ij. Let the coefficient a_ijk be 1 or 0 as color k is or is not possible for cell ij. Then for each k there are 9 row equations are sigma_i(a_ijkx_ijk) = 1, and similarly 9 column equations and 9 "box" equations. In addition there are 81 cell equations sigma_k(a_ijkx_ijk) =1, meaning exactly one color in each cell, so we have 108 equations in 729 unknowns. I assume there exist programs for solving this classical problem. Of course such a program would find ALL solutions of the equations most of might probably have negative entries but it would be interesting to see what the algorithm comes up with. Of course we are only interested in non-negative solutions, and this problem in general is the NP-complete problem of integer programming. On the other hand it might turn out that the sudoku solution is the only solution of the equations. Could someone give it a try on one of the evil problems? On the theological question, is this "using logic": I'd say it's even better, it's using mathematics. You can't get any more logical than that. David At 08:26 PM 7/18/2005, you wrote:
Mon, 18 Jul 2005 09:26:25 -0400 Michael Kleber <michael.kleber@gmail.com>
A central tenet of sudoku puzzles is that they should be solvable "by logic alone", which is to say, without any trial-and-error. This sparks religious battles within the sudoku-solving community, as people argue over whether certain techniques are legitimate logic or just glorified guess-and-check. Of course, what techniques you recognize as legitimate dictates how you rate the difficulty (or even the solvability) of various puzzles.
OK, it's cheating, but I wrote a quick program to solve sudoku puzzles. I tried it out on the examples that were sent in mail to math-fun, as well as a bunch of "evil" ones from websudoku.com
Using only 2 simple rules it never had to backtrack (I guess backtracking would be equivalent to "guess-and-check"). To be perfectly clear, there were times (rare) when there was no square with a unique choice, but choosing randomly at that point never ended up getting me into a dead end.
I didn't do anything clever, just coded up the technique I would use if I were trying to solve it by hand (on paper). That is, I kept a list of possible numbers for each given square. Rule 1 was that if you added a number n to a square at row r, column c, then you remove n from the allowed numbers for all squares in row r, in column c, and in the 3x3 box to with r,c belongs. Rule 2 says that at any point, if there is only one square in a row, or a column, or a 3x3 box that contains some number n as a possible value (e.g. if a row has 4 open squares which could be, respectively (1,2,8 or 9), (1,8, or 9), (1 or 8) and (1 or 9), then the first square would take on the value "2"). At each step in time you choose the square with the fewest allowable values, choose one of them, and then update the constraints using rules 1 and 2.
The code also will backtrack if you ever get to a point where a square has no allowed values. But I never got to such a deadend in my, admittedly small, sample. Is this true of all sudoku puzzles? Or have I just gotten lucky? [I haven't performed the obvious test of going back after success and choosing the *other* value in the cases where there were multiple choices.] I suspect that I've just gotten some lucky examples --- can someone give me an example of a "controversial" puzzle where one would have to backtrack?
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun