In the example below, I don't really see an essential difference between the method described, and algebra. Suppose one is asked to determine x, knowing that (x + 3)*2 + x + (x + 5) = (25 - 2) Disguised as a suitable word problem - eg, "The twins and their older brother and younger sister have their birthdays on the same day of the year. Julia is three years younger than Wilma; Sam is two years older than Grace. This year, from a box of 25 birthday candles, almost half the candles were needed for the cupcakes for the twins. After all four cupcakes were decorated only two candles were left over. How old is Julia?" First there is interpretation, involving cultural norms. Then trial and error will determine the various ages. Or, one can use "algebra" aka "magic" to write symbols that disguise the guessing. When pressed, the mystic says "I supposed that, whatever Julia's age was,..." To which the questioner will say, "Oh, you guessed!" And the mystic replies, "No guessing was involved!" and starts to mumble about unknowns, formulas, laws of distribution, association and transposition, and maybe redundant information or integer solutions... 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". We only call it guessing if we have to substitute "1" for "a" at an intermediate stage because our calculus is weak.
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.
So the challenge is to devise a suitable methodology. That is what seems appealing in the sudoku problems. [from prior messages]
Here's another almost completed example:
193 852 746 854 763 912 672 419 853
938 147 625 246 ... 371 517 236 489
78. 6.. .34 465 3.. .97 32. .74 .68
This is easily completed by making a guess. But I cannot see any way to complete it without making a guess.
This gets into the territory where people argue about what "making a guess" means (which is the cultural phenomenon that I thought was interesting enough to start the sudoku thread in the first place). If you naively write down which numbers are possible in each square, you get, among others:
. . . | . . . | . . . . . . | . . . | . . . . . . | . . . | . . . --------------+------------------+------------ . . . | . . . | . . . . . . | . f:8,9 c:5,8 | . . . . . . | . . . | . . . --------------+------------------+------------ . . a:1,9 | . d:2,9 b:1,5 | . . . . . . | . e:2,8 . | . . . . . . | . . . | . . .
The sudoku technique called "forcing chains" uses the following reasoning:
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.
I understand that people have developed coloring methods which make this type of deductive step easy to spot. But there is still, er, "lively debate" over whether this counts as guess work -- you certainly do assume something which in the end turns out to be false, though from just the information above, you can't tell which assumption is the bad one.
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.
participants (2)
-
Ken Roberts -
Michael Kleber