Sudoku
in [Math]
|
Prev: How many Primes?
Next: divisor problem
From: Timothy Little on 23 Aug 2005 18:00 George wrote: > When confronted with a puzzle that no existing techniques can solve, > they come up with a new "technique" which solves that puzzle. > Applying these rather complicated techniques is slower in practice > than trial-and-error, for humans anyway. There is always a logical solution. It's just that the logical propositions that need to be manipulated may get very complicated. Of course, guessing itself can be expressed as a logical rule: "(A in {3,4} and (A=3 implies ... implies F)) implies A=4" is a perfectly logical derivation. You can even write little appropriate symbols in the corners of the squares if you don't like erasing, and can't hold the intermediate steps in your head. Once all the empty squares have the right sort of symbols in their corners, you've logically derived the correct answer. > It may turn out that for 9x9 sudoku, there is some array of > "techniques" that solves all puzzles, but this will be because 9x9 > is too small. I'm sure that for n^2 x n^2 sudoku guessing is > required. It is NP-complete after all. NP-completeness doesn't imply guessing, one reason being that there isn't a well defined distinction between guessing and other reasoning. > Of course, all puzzles in newspapers can be solved by the basic > techniques. Some puzzle-setters guarantee this in the small print. > I assume they have a solver program that tries only the basic > tricks, and they check that each puzzle can be solved by this solver > before printing it. It would suffice to work backward from a completed solution, asking "which square can I recover from the basic tricks" at each step. If the answer is "none", you have a minimal starting position. - Tim
From: Darko Aleksic on 23 Aug 2005 18:44 On Tue, 23 Aug 2005 22:00:19 +0000 (UTC), Timothy Little <tim-usenet(a)little-possums.net> wrote: >George wrote: >> When confronted with a puzzle that no existing techniques can solve, >> they come up with a new "technique" which solves that puzzle. >> Applying these rather complicated techniques is slower in practice >> than trial-and-error, for humans anyway. > >There is always a logical solution. It's just that the logical >propositions that need to be manipulated may get very complicated. > >Of course, guessing itself can be expressed as a logical rule: >"(A in {3,4} and (A=3 implies ... implies F)) implies A=4" is a >perfectly logical derivation. > >You can even write little appropriate symbols in the corners of the >squares if you don't like erasing, and can't hold the intermediate >steps in your head. Once all the empty squares have the right sort of >symbols in their corners, you've logically derived the correct answer. > > >> It may turn out that for 9x9 sudoku, there is some array of >> "techniques" that solves all puzzles, but this will be because 9x9 >> is too small. I'm sure that for n^2 x n^2 sudoku guessing is >> required. It is NP-complete after all. > >NP-completeness doesn't imply guessing, one reason being that there >isn't a well defined distinction between guessing and other reasoning. > > >> Of course, all puzzles in newspapers can be solved by the basic >> techniques. Some puzzle-setters guarantee this in the small print. >> I assume they have a solver program that tries only the basic >> tricks, and they check that each puzzle can be solved by this solver >> before printing it. > >It would suffice to work backward from a completed solution, asking >"which square can I recover from the basic tricks" at each step. If >the answer is "none", you have a minimal starting position. > > >- Tim Well, this reminds me of the original Rubic Cube craze. I learned how to "solve" it (by using some "algorithms" - when this square is here and that one is over there, you do these moves). Then I saw a clip from some competition and the guy would look at the cube for 30 secs and when they started timing he would solve it in some bizzare (read: small) number of moves. They were doing it in 15-20 secs time after time, iirc. My best time doing it the "old-fashioned" way was 48secs (and I was really lucky in that case, usually it would take more than 1:20). Now, I know that people like Kasparov and Karpov are rare (even they could see maybe 7-8 moves tops, but chess has more possibilities), but these guys seemed to be able to see those 20-30 moves in that (alotted?) time of 30 secs just fine. I don't know if it was the fact that I was young and impressionable, but the fact that they could *see* the solution even before they started solving the Cube was something that scared me, just because I couldn't see it. Darko
From: Simon Tatham on 24 Aug 2005 11:15 <mareg(a)mimosa.csv.warwick.ac.uk> wrote: > 1) The only number that can go in this square is 3. > 2) The only place where the 5 in row 7 can go is here. [...] > 3) The 3 in row 5 must go in column 1 or 3. In either case, this forces > the 3 in row 6 to go in column 5. > 4) The 3 and the 7 in row 5 must go in columns 1 and 3. Hence no other > number can go in either of these places, which then enables you to place > another number somewhere else. Other than guessing and backtracking, these were the only solution techniques I knew of as well - until this week. On Monday, however, Gareth Taylor and I independently invented a non-recursive deductive technique (in a different context) which I then realised could also be applied to Sudoku, and which is not contained in the above list. Hence, it renders some puzzles non-recursively soluble which I'd previously believed to require recursion. So, if anyone's interested in unusually hard Sudoku, it should be a challenge to solve this one _without_ backtracking: 6 3 | 5 | 8 1 7 | 2 | 5 | 3 | 1 ------+-------+------ 3 | 5 | 6 1 | | 4 5 | 6 | 9 ------+-------+------ 7 | 2 | 4 | 9 | 8 1 9 | 4 | 3 6 I'm curious to know whether anyone else has used this technique before. I'd be happy if I turned out to have discovered an entirely new class of hard Sudoku, but I recognise that it's more than likely that I haven't :-) (I'm not being seriously secretive: I will describe the technique if asked. I just thought I'd leave it out of this posting, simply because it seems a bit silly to post a puzzle _and_ its solution!) -- Simon Tatham "loop, infinite _see_ infinite loop" <anakin(a)pobox.com> - Index, Borland Pascal Language Guide
From: Puppet_Sock on 24 Aug 2005 14:31 Simon Tatham wrote: > <mareg(a)mimosa.csv.warwick.ac.uk> wrote: > > 1) The only number that can go in this square is 3. > > 2) The only place where the 5 in row 7 can go is here. > [...] > > 3) The 3 in row 5 must go in column 1 or 3. In either case, this forces > > the 3 in row 6 to go in column 5. > > 4) The 3 and the 7 in row 5 must go in columns 1 and 3. Hence no other > > number can go in either of these places, which then enables you to place > > another number somewhere else. > > Other than guessing and backtracking, these were the only solution > techniques I knew of as well - until this week. > > On Monday, however, Gareth Taylor and I independently invented a > non-recursive deductive technique (in a different context) which I > then realised could also be applied to Sudoku, and which is not > contained in the above list. Hence, it renders some puzzles > non-recursively soluble which I'd previously believed to require > recursion. > > So, if anyone's interested in unusually hard Sudoku, it should be a > challenge to solve this one _without_ backtracking: > > 6 3 | 5 | 8 > 1 7 | 2 | > 5 | 3 | 1 > ------+-------+------ > 3 | 5 | 6 > 1 | | 4 > 5 | 6 | 9 > ------+-------+------ > 7 | 2 | 4 > | 9 | 8 1 > 9 | 4 | 3 6 > > I'm curious to know whether anyone else has used this technique > before. I'd be happy if I turned out to have discovered an entirely > new class of hard Sudoku, but I recognise that it's more than likely > that I haven't :-) > > (I'm not being seriously secretive: I will describe the technique if > asked. I just thought I'd leave it out of this posting, simply > because it seems a bit silly to post a puzzle _and_ its solution!) 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. Socks
From: Simon Tatham on 24 Aug 2005 16:07
> Simon Tatham wrote: >> (I'm not being seriously secretive: I will describe the technique if >> asked. I just thought I'd leave it out of this posting, simply >> because it seems a bit silly to post a puzzle _and_ its solution!) 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_ needed to guess; when I tried it, I got to the following position before running out of ordinary things to do and having to resort to something interesting. (And my automated solver agrees that there's nothing ordinary left to do in this position.) 6 3 | 5 b | a 8 7 1 7 | 2 | 3 5 | 3 | 1 ------+-------+------ 3 7 | 5 d | c 6 8 1 6 | | 4 2 5 | 6 | 3 9 ------+-------+------ 7 8 1 | 2 | 4 9 5 4 3 6 | 9 7 5 | 8 1 2 5 9 2 | 4 | 3 7 6 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 (although we don't know which yet), and that means d (which is in line with both b and c) cannot be a 1. Therefore it's a 9, and the rest of the solution follows easily. -- Simon Tatham "I'm going to pull his head off. Ear by ear." <anakin(a)pobox.com> - a games teacher |