Gary McGuire wrote:
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. ( Here's a description of the technique from a sudoku program's web site, which says pretty much the same thing as the above: http://www.simes.clara.co.uk/programs/sudokutechnique7.htm )
Somebody on a forum quoted the NP-completeness result as being a proof that sudokus requiring guesswork exist.
The NP-completeness result is for arbitrary n^2-by-n^2 grids, of course. It has no implications whatsoever for the 9-by-9 special case (which is, of course, solvable in constant time, by just checking against all 6.6 sextillion possible filled-in grids). But without any reason to think otherwise, I would certainly expect that some sudoku require guessing -- assuming you can find a definition of "guessing" which makes that nontrivial. --Michael Kleber -- It is very dark and after 2000. If you continue you are likely to be eaten by a bleen.