[math-fun] sudoku trial and error, NP-completeness
If you want a hard sudoku try . . . | . . 3 | . 6 . . . . | . . . | . 1 . . 9 7 | 5 . . | . 8 . ---------------------- . . . | . 9 . | 2 . . . . 8 | . 7 . | 4 . . . . 3 | . 6 . | . . . ---------------------- . 1 . | . . 2 | 8 9 . . 4 . | . . . | . . . . 5 . | 1 . . | . . . I believe that this one cannot be solved without trial and error (aka guesswork). 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. There is much discussion about whether every sudoku can be solved without resorting to trial and error. I think the above examples show that some sudokus require guesswork, but that's not a proof. None of the puzzles given in newspapers will require guesswork, but there are several levels of difficulty beyond what you find in published newspapers and books. Somebody on a forum quoted the NP-completeness result as being a proof that sudokus requiring guesswork exist. Solving sudoku is NP-complete, as has been mentioned before (see the wikipedia entry). The argument goes that an NP-complete problem requires a non-deterministic algorithm, which is one that has to make a random choice somewhere. This random choice is the guess. Is this a valid argument? I don't know enough about NP-completeness. Gary McGuire
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.
Well, It's certainly possible to solve a Sudoku puzzle without trial and error and guessing. Here's the proof: you can pose the solution of Sudoku as a problem in satisfiability (SAT): specifically you can have one variable for each pair (square,number) (so there are 729 variables). You then write down clauses which do the following: 0) You have 1-clauses, corresponding to the initial placement of the numbers that you're given: (s,n), means that number n is in square s. 1) 2-clauses: for each pair (s_i,n_i) (square and number) that "conflicts" (i.e. can't be present at the same time), you have a clause of the form (not (s_1,n_1)) or (not (s_2,n_2)) 2) For each square on the board (all 81 of them) you have a clause of the form or_i (s,i) You can solve any solvable SAT problem via resolution (which is like Gaussian elimination), and back substitution. This doesn't involve any guesswork. However, it could be exponential (since resolving on a variable can create a large number of new clauses). I'm not saying that this is the best way to do it though! However, if you wish to do it this way, it is certainly best to first do resolution on the subset of 1-clauses and 2-clauses (which is very fast -- there is a linear time algorithm for this). This corresponds to making the standard initial deductions. Victor
"Gary" == Gary McGuire <Gary.McGuire@nuim.ie> writes:
Gary> If you want a hard sudoku try (omitted): Gary> I believe that this one cannot be solved without trial and error Gary> (aka guesswork). It can be. I wrote a small python program to translate sudoku puzzles into DIMACS CNF (conjunctive normal form) used by a lot of SAT solvers. There is a preprocessor called hypre by Fahiem Bacchus which just uses something called "Hyper resolution" -- a limited form of deduction (which it turns out the CNF that I generated is ideal for). So far, the preprocessor -- which makes no guesses -- has solved every sudoku I've thrown at it, including your challenge above (and in much less than 1 second). Victor
participants (3)
-
Gary McGuire -
Michael Kleber -
victor＠idaccr.org