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

Michael B Greenwald wrote:

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.

Wow. How many times in a row can you flip Heads? Better yet, want to come pick lottery numbers for me? :-) Certainly you've just been getting lucky. The published puzzles are guaranteed to have only one solution, so every time you arbitrarily choose one of two possible values for a square, you should have a 50-50 chance of reaching an impossible position.

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

Here's an example of a line of reasoning that you'll miss: add two more empty boxes to the above example, like so: {1,2,8,9}, {1,8,9}, {1,8}, {1,9}, {2,3,4}, {2,3,4} It's still the case that the first box must contain the 2, because the boxes {1,8,9}, {1,8}, {1,9} certainly account for all of the 1,8,9 among them in some order. There are extended discussions of computer solving techniques -- start at the giant user forum at sudoku.com and follow links from there, I think. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.

Tue, 19 Jul 2005 10:22:15 -0400 Michael Kleber <michael.kleber@gmail.com> Michael B Greenwald wrote:

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.

Wow. How many times in a row can you flip Heads? Better yet, want to come pick lottery numbers for me? :-) Certainly you've just been getting lucky. The published puzzles are guaranteed to have only one solution, so every time you arbitrarily choose one of two possible values for a square, you should have a 50-50 chance of reaching an impossible position. The choices last night didn't show up in published puzzles, they were in ones my kids made for me. Last night no choices had showed up in the 4 or 5 "evil" examples from the web site, or in the 3 examples from math-fun. I tried again for a few minutes this morning, and got a backtracking case. However, it seems that the categories "evil" is not hard in the sense of forcing this algorithm to backtrack --- in my very small sample, a relatively small fraction of evil puzzles have any backtracking (just 1 out of 7). Again, this could be luck.

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

Here's an example of a line of reasoning that you'll miss: add two more empty boxes to the above example, like so: {1,2,8,9}, {1,8,9}, {1,8}, {1,9}, {2,3,4}, {2,3,4} It's still the case that the first box must contain the 2, because the boxes {1,8,9}, {1,8}, {1,9} certainly account for all of the 1,8,9 among them in some order. Yes, this line of reasoning could lead to something the program will miss, but this particular example doesn't work because of the rule that says "choose the square with fewest options first". There are extended discussions of computer solving techniques -- start at the giant user forum at sudoku.com and follow links from there, I think. Thanks. I will look there, although I'm not looking for computer solving techniques, I was trying to understand what you meant when you mentioned "logic" vs. "guess-and-check". Another question: does anyone know the minimal number of squares needed to uniquely determine a solution?