Sudoku
in [Math]
|
Prev: How many Primes?
Next: divisor problem
From: mensanator@aol.compost on 18 Aug 2005 19:59 mareg(a)mimosa.csv.warwick.ac.uk wrote: > 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. And some other number must go in the other square, right? > > 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. Wouldn't you write both numbers in the corner? > These are not guesses, they are just alternative possibilities. And knowing one, forces the other. > The idea is to try and make further deductions which will eventually > enable you to put some numbers in with certainty. So what happens when ALL the blank squares end up with multiple numbers in the corners? Don't you have to guess at that point? Or are they saying that should never happen on a proper Sudoku, that there must be some logic I'm overlooking that tells me which number to pick? > > Derek Holt.
From: Torkel Franzen on 18 Aug 2005 21:50 "Russell" <russell(a)mdli.com> writes: > 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? No, my comment was quite superficial. Sudoku problems are constraint problems, and some such problems are solvable by various constraint propagation algorithms that swiftly eliminate possibilities by looking at subsets of the constraint set. I would guess that this corresponds to what was described as sudoku problems that don't call for guessing, but only for logical reasoning, and that the supplier quoted has some scheme for generating problems solvable by some particular constraint propagation algorithm. There is no hard division.
From: Russell on 18 Aug 2005 22:46 Torkel Franzen wrote: > "Russell" <russell(a)mdli.com> writes: > > > 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? > > No, my comment was quite superficial. Sudoku problems are constraint > problems, and some such problems are solvable by various constraint > propagation algorithms that swiftly eliminate possibilities by looking > at subsets of the constraint set. I would guess that this corresponds > to what was described as sudoku problems that don't call for guessing, > but only for logical reasoning, and that the supplier quoted has some > scheme for generating problems solvable by some particular constraint > propagation algorithm. There is no hard division. Thanks, that's pretty much what I was thinking. I found it interesting that there is such a clearly perceived difference between the guessing approach and the "logical" approach, as noted by Derek Holt. And so, I wondered what basis (if any) it had in a more formal mathematical sense. I think it's that when one guesses, one can make do with a much smaller subset of knowable constraints, indeed a minimal subset suffices. But by the logical approach, the sky's the limit (for all we know -- though as you say, there probably is some fixed set of constraints used in the generation). This makes the puzzle much more appealing. I suppose at the high end it gets boring again -- when you have memorized all possible starting configurations and can treat each one as a single constraint. :-)
From: John R Jones on 19 Aug 2005 09:24 Russell wrote: > Torkel Franzen wrote: > > "Russell" <russell(a)mdli.com> writes: > > > > > 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? > > > > No, my comment was quite superficial. ...> > Thanks, that's pretty much what I was thinking. I > found it interesting that there is such a clearly > perceived difference between the guessing approach > and the "logical" approach, as noted by Derek Holt. > And so, I wondered what basis (if any) it had in a > more formal mathematical sense. ... Hmm, I think I will just post to rec.puzzles in future ;-) I sit corrected on the rules of sudoku, although I find it unusual that the method of solving should be a part of the puzzle. Backtracking is frequently used in crosswords by the less gifted (indeed so) and only prize puzzles forbid crossings out. I think backtracking is one of the most useful mind tools for all kinds of problem since it allows the non- omniscient the opportunity to make some progress (reduce constraints etc). Isnt the mathematical thought behind this akin to the old proof by construction versus proof by contradiction? The former corresponding to solution by application of pure logic and more and more arcane rules; the latter by postulating square x is a 3 leads to a contradiction hence square x is not a 3. Please discuss using one side of the electron only. JJ
From: Timothy Little on 19 Aug 2005 19:30
John R Jones wrote: > I sit corrected on the rules of sudoku, although I find it unusual that > the method of solving should be a part of the puzzle. Backtracking is > frequently used in crosswords by the less gifted (indeed so) and only > prize puzzles forbid crossings out. What's the real difference between "this square could be 3 or 5, let's see what follows if it's 3" versus "this square could be 3 or 5, let's see what follows in both cases at once"? It just seems to be sequential versus parallel deduction, with the one most likely to find the solution varying depending upon the circumstances. Surely part of the skill with such puzzles is determining which approach is most fruitful in a given situation? Where's the skill otherwise? - Tim |