Sudoku
in [Math]
|
Prev: How many Primes?
Next: divisor problem
From: Simon Tatham on 25 Aug 2005 04:18 r.e.s. <r.s(a)ZZmindspring.com> wrote: > Isn't this just an example of a so-called "forcing chain"? > (e.g. see http://www.simes.clara.co.uk/programs/sudokutechnique7.htm) Hmm. I suppose it could be seen that way, although that's not how I saw it. I saw it as a special case of a rather different pattern, which I currently describe as `mutual neighbour analysis'. Rather than being a chain of arbitrary length, this pattern involves finding two non-adjacent squares and a bunch of their mutual neighbours, and observing that placing a particular number in one of the end squares forces all the neighbours to take values which cause a contradiction in the other end square. The important thing about this is that it doesn't have to be limited to only two mutual neighbours. Consider this hypothetical case: +---+---+---+ |123| | | +---+---+---+ | | | | +---+---+---+ | | |34 | +===+===+===+ | | |45 | +---+---+---+ |124| | | +---+---+---+ |124| | | +---+---+---+ If the 45 square has a 4 in it, then the 34 square must be a 3, and the two 124 squares must be 1 and 2 in some order, and hence the 123 square is a problem. Hence, the 45 square can't be a 4, so must be a 5. It seems to me that this doesn't fall into the `forcing chain' pattern, because it isn't a linear chain of single cells; but it does fall into my `mutual neighbours' pattern. The simple example I showed yesterday appears to fall into both. > It seems to me that these examples support the idea that when > people say a sudoku "requires guessing" (backtracking), what it > amounts to is that the patterns (forcing chains, etc.) necessary > to solve it are simply not among those they recognise. Certainly many of these patterns are things which could have been solved by recursion but can be done more efficiently if you can spot the pattern. However, I'm less convinced that _all_ backtracking- requiring Sudoku can be reduced to this sort of pattern, due to the claim on Wikipedia that Sudoku is NP-complete: if this is true, then it _cannot_ be possible to solve any Sudoku by simple pattern searching techniques, because there must come a point at which the required chains of inference become bounded only by the grid size. -- Simon Tatham "A defensive weapon is one with my finger on the <anakin(a)pobox.com> trigger. An offensive weapon is one with yours."
From: r.e.s. on 25 Aug 2005 07:13 "Simon Tatham" <anakin(a)pobox.com> wrote ... > Rather than being a chain of arbitrary length, this pattern involves > finding two non-adjacent squares and a bunch of their mutual > neighbours, and observing that placing a particular number in one of > the end squares forces all the neighbours to take values which cause > a contradiction in the other end square. > > The important thing about this is that it doesn't have to be limited > to only two mutual neighbours. Consider this hypothetical case: > > +---+---+---+ > |123| | | > +---+---+---+ > | | | | > +---+---+---+ > | | |34 | > +===+===+===+ > | | |45 | > +---+---+---+ > |124| | | > +---+---+---+ > |124| | | > +---+---+---+ > > If the 45 square has a 4 in it, then the 34 square must be a 3, and > the two 124 squares must be 1 and 2 in some order, and hence the 123 > square is a problem. Hence, the 45 square can't be a 4, so must be a > 5. > > It seems to me that this doesn't fall into the `forcing chain' > pattern, because it isn't a linear chain of single cells I'm unfamiliar with many details, but apparently the concept of "forcing chain" includes the following type that appears in your example, where each of the three candidates for cell A (say) leads to the conclusion that X=5: +---+---+---+ A |123| | | +---+---+---+ | | | | +---+---+---+ | | |34 | D +===+===+===+ | | |45 | X +---+---+---+ B |124| | | +---+---+---+ C |124| | | +---+---+---+ A in {1,2,3}. A=1 => B in {2,4} AND C in {2,4} => X<>4 => X=5. A=2 => B in {1,4} AND C in {1,4} => X<>4 => X=5. A=3 => D=4 => X<>4 => X=5. Therefore X=5. (I don't know whether the general pattern you describe can always be reduced to such a general type of forcing chain.) > Certainly many of these patterns are things which could have been > solved by recursion but can be done more efficiently if you can spot > the pattern. However, I'm less convinced that _all_ backtracking- > requiring Sudoku can be reduced to this sort of pattern, due to the > claim on Wikipedia that Sudoku is NP-complete: if this is true, then > it _cannot_ be possible to solve any Sudoku by simple pattern > searching techniques, because there must come a point at which the > required chains of inference become bounded only by the grid size. I believe there is a misunderstanding, in that the NP-completeness of the game, as mentioned at http://en.wikipedia.org/wiki/Sudoku, refers to the *general* case of n^2 x n^2 boards of n x n blocks -- it does not apply to a specific n, such as the standard n=3. --r.e.s.
From: Timothy Little on 25 Aug 2005 08:23 Simon Tatham wrote: > I'm less convinced that _all_ backtracking- requiring Sudoku can be > reduced to this sort of pattern, due to the claim on Wikipedia that > Sudoku is NP-complete: if this is true, then it _cannot_ be possible > to solve any Sudoku by simple pattern searching techniques, because > there must come a point at which the required chains of inference > become bounded only by the grid size. You've proved that P != NP, and furthermore that there exist problems in NP that require exponential time? Even if true, it would just mean that you might need a book of patterns that increases with grid size faster than polynomial. Or it could be that there are always a polynomial number of simple patterns, but determining those patterns for large grids takes longer than polynomial time. But we haven't even proved P != NP, yet. - Tim
From: Simon Tatham on 25 Aug 2005 08:32 r.e.s. <r.s(a)ZZmindspring.com> wrote: > I believe there is a misunderstanding, in that the NP-completeness > of the game, as mentioned at http://en.wikipedia.org/wiki/Sudoku, > refers to the *general* case of n^2 x n^2 boards of n x n blocks -- > it does not apply to a specific n, such as the standard n=3. Well, of course; I've been talking about arbitrary-size Sudoku all along. What possible interest could there be in restricting myself to a single size?! -- Simon Tatham "A defensive weapon is one with my finger on the <anakin(a)pobox.com> trigger. An offensive weapon is one with yours."
From: Patrick Hamlyn on 25 Aug 2005 11:49
Ed Murphy <emurphy42(a)socal.rr.com> wrote: >On Thu, 25 Aug 2005 01:21:01 +0000, Patrick Hamlyn wrote: > >> Simon Tatham <anakin(a)pobox.com> wrote: >> >>>I've marked four squares a, b, c and d in the above diagram. Their >>>possible values are: >>> >>> - a could be 2 or 9 >>> - b could be 1 or 9 >>> - c could be 1 or 2 >>> - d could be 1 or 9. >>> >>>The important points are that each of b and c is in line with a; each can >>>contain one of the possible numbers in a; and each can also contain a 1. >>>Therefore, if neither of b and c were 1 then between them they'd contain >>>a 2 and a 9, and there would be no remaining number to put in a; hence at >>>least one of b and c must be a 1 >> >> It might be easier to just note that if you have ab >> cd >> fillable with only 3 values, then one value must be repeated on a >> diagonal, the only possibility being 1 on a and d. > >This is wrong in multiple ways: > >* a cannot be 1 (given) > >* d cannot be 1 (deduced) > >* the point is not that one value must be repeated on some diagonal, > but rather that one value must appear on a specific diagonal, and > thus be absent from the other > The point *is* that a value must be repeated, since there are three possible values covering four points. It is furthermore true that the repeated values must be on a diagonal, since orthogonal points may not have the same value. The fact that I inadvertently rearranged the labelling of a,b,c,d from the original is minor, irrelevant and easily seen beyond with the smallest *positive* effort. And I wasn't solving the general case, I was pointing out a simpler application of logic which could be used on this one. I don't have to solve the general case just because *you* think it's the only way to do it. -- Patrick Hamlyn posting from Perth, Western Australia Windsurfing capital of the Southern Hemisphere Moderator: polyforms group (polyforms-subscribe(a)egroups.com) |