Sudoku
in [Math]
|
Prev: How many Primes?
Next: divisor problem
From: Puppet_Sock on 25 Aug 2005 13:14 Simon Tatham wrote: > Puppet_Sock <puppet_sock(a)hotmail.com> wrote: > > Well, I got quite far with it, but eventually broke down and > > had to guess. Only had about 10 spots left by the time I needed > > to guess though. > > > > So, yes please. > > I'm not sure how you got down to only 10 empty squares and _then_ [snip] For suitable values of "about." I had exactly your grid. Socks
From: r.e.s. on 25 Aug 2005 14:02 "Simon Tatham" <anakin(a)pobox.com> wrote ... > 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?! Well, for one thing, the above comment applies as well if all sudokus for n up to 10 (say) were considered "standard". You might be surprised at the interest some people would have in a small collection of human-usable visual-pattern-based strategies guaranteed adequate to solve every standard-size sudoku without backtracking. --r.e.s.
From: Arthur J. O'Dwyer on 25 Aug 2005 16:07 On Thu, 25 Aug 2005, Simon Tatham wrote: [...] > 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. [...] > If the 45 square has a 4 in it, [...] a problem. Hence, the 45 square > can't be a 4, so must be a 5. Tell me again how this is distinct from "backtracking"? Basically, your method is 1. Fill in a value for cell X. 2. Fill in a value for cells Y, Z,... dependent on X. 3. If at any point you find a contradiction, return to step 1. That looks a lot like backtracking to me! (Not that backtracking is bad; I just don't see why this particular class of backtracking applications is interesting.) -Arthur, Sudoku is crosswording for the illiterate
From: r.e.s. on 25 Aug 2005 19:17 "Arthur J. O'Dwyer" <ajo(a)nospam.andrew.cmu.edu> wrote ... > Tell me again how this is distinct from "backtracking"? Basically, > your method is > > 1. Fill in a value for cell X. > 2. Fill in a value for cells Y, Z,... dependent on X. > 3. If at any point you find a contradiction, return to step 1. > > That looks a lot like backtracking to me! Not to answer for anyone else, but ... On the one hand, there is a proof that a certain general pattern leads to a certain conclusion. On the other hand, there is the application of that fact to draw the corresponding conclusion for a specific instance of the pattern. Would you say the application necessarily involves backtracking just because a proof involves reductio ad absurdum? --r.e.s.
From: Timothy Little on 25 Aug 2005 19:18
Arthur J. O'Dwyer wrote: > > On Thu, 25 Aug 2005, Simon Tatham wrote: >> If the 45 square has a 4 in it, [...] a problem. Hence, the 45 square >> can't be a 4, so must be a 5. > > Tell me again how this is distinct from "backtracking"? I think the difference is that it's backtracking if you actually write down the hypothetical, and not backtracking if you do it in your head. - Tim |