Sudoku
in [Math]
|
Prev: How many Primes?
Next: divisor problem
From: Torkel Franzen on 18 Aug 2005 12:54 Volker <newsgroups(a)vsiep.de> writes: > > SuDokus from the Daily SuDoku are always solvable using > > logic alone. You should never have to employ trial and > > error tactics. Again, we can't speak for puzzles from > > other sources. > I think, that points out the situation. OK, so they supply problems in a particular subset of these constraint problems.
From: Torkel Franzen on 18 Aug 2005 13:32 "Russell" <russell(a)mdli.com> writes: > When you write something that you later have to erase, > isn't that guessing? Maybe you are arguing over words. Some constraint problems can be solved by constraint propagation in linear time. The general class of finite constraint problems is NP-complete, and so we are reduced to guessing and testing, with various refinements. Presumably the situation is the same with the special class of sudoku problems, so that the supplier quoted earlier takes care to only deliver problems in the first category.
From: Dave Rusin on 18 Aug 2005 14:39 In article <de2c67$mnt$1(a)wisteria.csv.warwick.ac.uk>, <mareg(a)mimosa.csv.warwick.ac.uk> wrote: >According to my understanding of the rules of Sudoku, you are not >supposed to use backtracking at all when solving them. I thought I overheard a conversation in which it was explained that each Sudoku puzzle can be cast in the form of a covering-subset problem, and that such problems can be treated as a linear-programming problem. This then admits a solution which does not require backtracking (although the simplex algorithm is arguably comparable to backtracking anyway: "try something and then do the best you can from there"). I don't actually understand either step of that half-remembered discussion. Can someone step up to the plate and fill in the details? dave
From: Russell on 18 Aug 2005 15:48 Torkel Franzen wrote: > "Russell" <russell(a)mdli.com> writes: > > > When you write something that you later have to erase, > > isn't that guessing? Maybe you are arguing over words. > > Some constraint problems can be solved by constraint propagation > in linear time. The general class of finite constraint problems > is NP-complete, and so we are reduced to guessing and testing, with > various refinements. Presumably the situation is the same with the > special class of sudoku problems, so that the supplier quoted > earlier takes care to only deliver problems in the first category. I'm not sure I follow you, so I look forward to some possible learning here. I should add that I'm not very familiar (at all) with sodoku. At least in one puzzle that I know -- minesweeper -- I can see how there are two categories: puzzles for which guessing is required, and those for which (after an intial move, say, in the upper left corner) logic alone suffices. Puzzles of the former type, which is nearly all of them, do not have unique solutions in any practical sense so I am not considering them. It is puzzles of the latter type that (IIRC) are thought to be NP-complete, and surely, there is a wide range of difficulty possible in them. I am sure there are many for which I would not be able to find the logic to justify my next move, at some step. To the extent that the analogy applies, are you saying that logically-solvable minesweepers (i.e. ones with unique solutions) can be divided into two sharp sub-categories, easy and hard? I don't see how that can be done. Sure, you could pick some limited set of rules, and say that some minesweepers are solvable by those rules and some are not; but a *complete* set of rules must solve the entire set (else it is not complete). Right?
From: on 18 Aug 2005 18:44
In article <de2kln$fef$1(a)news.math.niu.edu>, rusin(a)vesuvius.math.niu.edu (Dave Rusin) writes: >In article <de2c67$mnt$1(a)wisteria.csv.warwick.ac.uk>, > <mareg(a)mimosa.csv.warwick.ac.uk> wrote: > >>According to my understanding of the rules of Sudoku, you are not >>supposed to use backtracking at all when solving them. > >I thought I overheard a conversation in which it was explained that >each Sudoku puzzle can be cast in the form of a covering-subset >problem, and that such problems can be treated as a linear-programming >problem. This then admits a solution which does not require >backtracking (although the simplex algorithm is arguably comparable >to backtracking anyway: "try something and then do the best you can >from there"). > >I don't actually understand either step of that half-remembered >discussion. Can someone step up to the plate and fill in the details? Not really, but I think that there is a clear distinction between backtracking and non-backtracking methods of solving a Sudoku puzzle. You often reach a point where you know that some number, 3, say, must go in one of two squares. In the backtracking approach, you guess one of them and carry on solving under that assumption. If you guessed right, you may solve the problem (although you will have to try the other possibility if you want to verify that the solution is unique), but if you guessed wrong, then you will have to erase everything from the guess onwards, and go back and try the other possibility. Of course, you may make further guesses later on, leading to a typical backtrack search tree. With the non-backtracking approach, you just note the fact that 3 may go in one of those two places. You may decide to mark this somehow by writing a small number 3 in the corner of the two squares in question. These are not guesses, they are just alternative possibilities. The idea is to try and make further deductions which will eventually enable you to put some numbers in with certainty. Derek Holt. |