Ken Roberts wrote:
Bottom line: The following snippet of reasoning, if embedded in some suitable calculus which starts with "a" as a symbol and cranks thru to determine "f"=9, would not be described as "guessing". [...] So the challenge is to devise a suitable methodology. That is what seems appealing in the sudoku problems.
I agree entirely. It may even be possible to describe what properties a presentation-of-a-solving-methodology would need to have in order to gain acceptance. Since sudoku is a pencil-and-paper game and is in any case trivial on a computer, it would have to be feasible to carry out the solving method "by hand." From a practical point of view, one should be able to use it to solve the puzzle "in place", without extra scratch paper. We can formalize this as the requirement that the amount of storage used to run the algorithm should be bounded by some constant times the size of the original puzzle. (This clearly allows, for example, the natural form of "marking up" the puzzle by writing down which digits may appear in each square.) Of course, this doesn't preclude exhaustive search; a depth-first search can easily be implemented in constant space. A limit on run-time would take care of this, and is clearly desirable, but seems less natural somehow. Perhaps we could impose some limit on the number of times each of the allowed storage spaces is written to? That's the "don't do too much erasing" rule. Hmm, but now it occurs to me that it's not clear to me whether the rules above allow one to search a grid to determine locations where one can apply "double forcing chains":
If a=1 then b=5, c=8, f=9 If a=9 then d=2, e=8, f=9 Therefore, no matter what, f=9.
But perhaps they are easy to find and I'm just being dense. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.