View previous topic :: View next topic |
Author |
Message |
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Tue Sep 06, 2005 9:17 pm Post subject: A very tough "Swordfish" puzzle |
|
|
Here's one for people who enjoy a challenge. I found this one on the Sad Man Software site. http://www.simes.clara.co.uk/programs/sudokutechniques.htm
Code: |
x x 8 x 9 x 1 x 5
x 3 1 6 x x x x x
4 x x x x x x x x
x x x x x 5 x x x
x x 3 x 1 x 6 x x
x x x 4 x x x x x
x x x x x x x x 7
x x x x x 7 4 2 x
8 x 9 x 6 x 3 x x
|
Here are a couple of little hints. The first twelve moves are pretty easy. Then there are three very hard moves. After you find the first fifteen numbers, the rest is a piece of cake. Oh -- the logical solution involves a rather intricate "swordfish" argument involving more than a single digit -- there are two different numbers to look for, and the pairs of one number appear in columns, while the pairs of the other appear in rows.
Good luck! dcb |
|
Back to top |
|
|
Katie
Joined: 05 Aug 2005 Posts: 13 Location: London
|
Posted: Wed Sep 07, 2005 3:58 pm Post subject: |
|
|
Cracked it - and sent you the answer on a post message. Didn't want to post it here as that would spoil the fun for others.
Katie |
|
Back to top |
|
|
someone_somewhere
Joined: 07 Aug 2005 Posts: 275 Location: Munich
|
Posted: Wed Sep 07, 2005 7:59 pm Post subject: |
|
|
Ye, I was just wondering what kind of swordfish it was in that 3-dt example of the site you mentioned. Could not find it, so I was thnking that there is a mistake in that position. Never crossed my mind to look for a "stinky fish".
BTY, I got to the following point for the condidate table:
267 26 8 37 9 23 1 4 5
5 3 1 6 4 28 2789 789 289
4 9 27 1578 2578 128 28 36 36
12679 12468 46 3789 2378 5 2789 13789 2389
279 5 3 789 1 289 6 789 4
1279 128 27 4 2378 6 5 13789 2389
1236 1246 456 13589 358 1389 89 689 7
136 16 56 13589 358 7 4 2 689
8 7 9 2 6 4 3 5 1
Here there are a lot of numbers where the fish is hidding. And when it involves more than one numbers, no wonder that I am color blind and could not spot it.
At least a better hint is wellcomed for a bind and old man, like me.
Thank you in advance, |
|
Back to top |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Wed Sep 07, 2005 9:34 pm Post subject: |
|
|
OK, I will give you a better hint, since you were so kind as to give me some 100 year old single malt whisky. First, though, I should point out a very small error in your table: I think that "2389" in r4c9 ought to say "23689".
The numbers you should look for are "2" (in rows) and "9" (in columns). You can already see one of the pairs of "9"s, in column 6. Unfortunately, you still have too many "2"s on the board to spot the pairs in rows. So you need to get rid of some "2"s.
Try looking carefully at the middle left 3x3 box (the intersection of rows 4, 5, & 6 with columns 1, 2, &3). I think you will find that there are only two cells in this box where a "2" can actually be placed without forcing a contradiction somewhere. Or, to look at it another way, there are two cells in this box such that if one of them does not contain a "2", the other one must contain a "2". This pattern is, I think, a sort of "swordfish" that connects two cells in the same 3x3 box ... a very nice embellishment of the concept.
After you find that, you may be able to isolate a "hidden pair" in the same 3x3 box.
I hope you're having fun! dcb |
|
Back to top |
|
|
chobans
Joined: 21 Aug 2005 Posts: 39
|
Posted: Wed Sep 07, 2005 10:21 pm Post subject: |
|
|
Actually r4c9 is "2389". There is a 6 at r5c7 so 6 can't be one of the option at r4c9.
I... actually took different route of "swordfish". I was able to find THIRTEEN numbers first without problem. It's the next two that caused the problem. I tried to find "traditional" swordfish as described on that site but couldn't really locate one. Then I noticed one thing.
The number "2" in row 1, 5 and 7. In row 5 and 7, 2 appears only twice. But in row 1, it appears three times. But the columns in row 1 that number 2 can appear corresponds to the three columns for row 5 and 7. (column 1, 2 and 6). So I did some more research and found out that this is also a form of "swordfish".
Then after removing the number 2 from other cells in column 1, 2 and 6 (6 cells removed), I was able to get 8 at r2c6 and 1 at r3c6. |
|
Back to top |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Thu Sep 08, 2005 3:24 pm Post subject: Excellent insight |
|
|
chobans wrote: | Actually r4c9 is "2389". There is a 6 at r5c7 so 6 can't be one of the option at r4c9.
I... actually took different route of "swordfish". I was able to find THIRTEEN numbers first without problem. It's the next two that caused the problem. I tried to find "traditional" swordfish as described on that site but couldn't really locate one. Then I noticed one thing.
The number "2" in row 1, 5 and 7. In row 5 and 7, 2 appears only twice. But in row 1, it appears three times. But the columns in row 1 that number 2 can appear corresponds to the three columns for row 5 and 7. (column 1, 2 and 6). So I did some more research and found out that this is also a form of "swordfish".
Then after removing the number 2 from other cells in column 1, 2 and 6 (6 cells removed), I was able to get 8 at r2c6 and 1 at r3c6. |
That's very good, Chobans! Your solution is certainly much simpler and more elegant than the one I had found. As someone somewhere has already observed, I tend to make these things more complicated than they ought to be. My mind is twisted.
Just to be sure I understand what you did, let's go back to the position our friend in Munich had reached:
Code: |
267 26 8 37 9 23 1 4 5
5 3 1 6 4 28 2789 789 289
4 9 27 1578 2578 128 28 36 36
12679 12468 46 3789 2378 5 2789 13789 2389
279 5 3 789 1 289 6 789 4
1279 128 27 4 2378 6 5 13789 2389
1236 1246 456 13589 358 1389 89 689 7
136 16 56 13589 358 7 4 2 689
8 7 9 2 6 4 3 5 1 |
I find Chobans' insight easiest to understand by concentrating on row 5. If we put a "2" in r5c1 then we must also put a "2" in r7c2, because there are only two ways to fit a "2" into row 7. But then we must put a "2" in r1c6, because that's the only place left for a "2" in the first row.
What if we put a "2" in r5c6? That will force a "3" in r1c6 and leave us with an X-Wing formation in r1c1, r1c2 and r7c1, r7c2. Either way we are left with "2"s in one of two places in each of three columns, permitting us to simplify the matrix:
Code: |
267 26 8 37 9 23 1 4 5
5 3 1 6 4 8 2789 789 289
4 9 27 1578 578 1 28 36 36
1679 1468 46 3789 2378 5 2789 13789 2389
279 5 3 789 1 289 6 789 4
179 18 27 4 2378 6 5 13789 2389
1236 1246 456 13589 358 1389 89 689 7
136 16 56 13589 358 7 4 2 689
8 7 9 2 6 4 3 5 1 |
This post is too long already -- I'll write again later to explain what I saw in the middle left box. It's not as elegant as Chobans' approach, but it's still kind of cute.
I'm curious about one thing, Chobans. What was the thirteenth number you found, and how did you locate it? dcb |
|
Back to top |
|
|
chobans
Joined: 21 Aug 2005 Posts: 39
|
Posted: Thu Sep 08, 2005 3:34 pm Post subject: Re: Excellent insight |
|
|
David Bryant wrote: | I'm curious about one thing, Chobans. What was the thirteenth number you found, and how did you locate it? dcb |
Same as the one someone_somewhere had. I had the EXACT thing as he did. He has 34 numbers before he got stuck. And since the start has given us 21 numbers, we both found the exact 13 numbers. |
|
Back to top |
|
|
geoff h
Joined: 07 Aug 2005 Posts: 58 Location: Sydney
|
Posted: Thu Sep 08, 2005 11:50 pm Post subject: |
|
|
I ended up with the same 34 numbers as "chobans"and "someone somewhere" before I got stuck. I eventually solved the puzzle, but only through a bit of trial and error involving the Nr 2s. I could easily see that placing the 2s was the key to the puzzle. However, as I said, it involved a little trial and error, which I don't like using.
However, David, it seems that using your swordfish solution, there is still a bit of trial and error involved. Is this correct? I only ever like placing a number in a cell when I know that logic dictates that that is where it must go. However, your swordfish method seems to suggest some trial and error is needed.
Is this correct or am I missing something?
Cheers. |
|
Back to top |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Fri Sep 09, 2005 1:01 am Post subject: The missing piece |
|
|
There is still a piece missing, Geoff.
I really ought to count more carefully. In my original post I said there were twelve easy moves, then three very hard ones. As Chobans pointed out, that should have been 13 fairly simple moves, followed by three tough ones.
Chobans showed us an elegant way to make two of those moves. He didn't explain the third one. The missing piece is in the middle left box, specifically in row 4, column 1. We assert that that cell cannot validly contain the number "6", and proceed as follows. Here's the table as it stands at this point:
Code: |
267 26 8 37 9 23 1 4 5
5 3 1 6 4 8 2789 789 289
4 9 27 1578 578 1 28 36 36
1679 1468 46 3789 2378 5 2789 13789 2389
279 5 3 789 1 289 6 789 4
179 18 27 4 2378 6 5 13789 2389
1236 1246 456 13589 358 1389 89 689 7
136 16 56 13589 358 7 4 2 689
8 7 9 2 6 4 3 5 1 |
Now suppose that r4c1=6. We have the following chain of inference:
r4c1=6 ==> r4c3=4 (only two possibilities at r4c3)
r4c3=4 ==> r7c3 is not 4 ==> r7c2=4 (only two chances for "4" in row 7)
r7c2=4 ==> r1c2=2 (only two places for "2" in column 2)
r1c2=2 ==> r3c3=7 ==> r1c1=6 (a short forcing chain)
But we began by assuming that r4c1=6, so we've arrived at a contradiction (two "6"s in the same column), and we see that r4c1 cannot be "6". Eliminating "6" from the list of possibilities at r4c1 we see the following possibilities for the middle left box:
179 1468 46
279 --5- --3-
179 18 27
But now r4c2 & r4c3 are the _only_ cells that can contain the values "4" and "6" in the middle left 3x3 box, so those cells contain the pair {4, 6} ... the "8" in this box must fit at row 6, column 2, because there's nowhere else for it to go. Now the matrix looks like this:
Code: |
267 26 8 37 9 23 1 4 5
5 3 1 6 4 8 2789 789 289
4 9 27 1578 578 1 28 36 36
179 46 46 3789 2378 5 2789 13789 2389
279 5 3 789 1 289 6 789 4
179 8 27 4 237 6 5 1379 239
1236 1246 456 13589 358 1389 89 689 7
136 16 56 13589 358 7 4 2 689
8 7 9 2 6 4 3 5 1 |
and I'm sure you'll find the rest of the puzzle fairly easy to complete, Geoff. dcb |
|
Back to top |
|
|
geoff h
Joined: 07 Aug 2005 Posts: 58 Location: Sydney
|
Posted: Fri Sep 09, 2005 4:16 am Post subject: |
|
|
Thanks for your reply David. As I said, I also found the 13 numbers fairly quickly and eventually solved the puzzle through a bit of trial and error in placing the 2s.
I suppose I'm being a bit pedantic, but I only like to put a number in a cell when that number is the only logical possibility and there is no guess work ( or assumptions ) at all. I understand your train of thought involving the chain of inference and thanks for sending the information.
I suppose I still don't like to make a start to the chain by guessing ( or assuming ) a certain number. However, as I said, maybe I'm being a bit too pedantic.
Thanks for your help.
Cheers. |
|
Back to top |
|
|
chobans
Joined: 21 Aug 2005 Posts: 39
|
Posted: Fri Sep 09, 2005 6:28 am Post subject: Re: The missing piece |
|
|
David Bryant wrote: | Chobans showed us an elegant way to make two of those moves. He didn't explain the third one. |
I didn't think the third one was needed since simpler elimination method was sufficient enough to solve the rest. After I got the 8 at r2c6 and 1 at r3c6, I proceeded to row 2.
r2c7 can be 279. r2c8 can be 79. r2c9 can be 29. So I knew I can eliminate 2,7 and 9 from other cells in box 3. So eventhough r3c7 can be 2 or 8, after eliminating 2, I knew that it could only be an 8 in that cell.
After that it was pretty much clear sailing. |
|
Back to top |
|
|
David Bryant
Joined: 29 Jul 2005 Posts: 559 Location: Denver, Colorado
|
Posted: Fri Sep 09, 2005 4:06 pm Post subject: Eliminating Possibilities |
|
|
geoff h wrote: | ...
I suppose I'm being a bit pedantic, but I only like to put a number in a cell when that number is the only logical possibility and there is no guess work ( or assumptions ) at all. I understand your train of thought involving the chain of inference and thanks for sending the information.
I suppose I still don't like to make a start to the chain by guessing ( or assuming ) a certain number. However, as I said, maybe I'm being a bit too pedantic. ...
|
Not to put too fine a point on it, Geoff, but from the perspective of formal logic, there is absolutely no difference between "the only logical possibility" and "guess work." Consider this very simple example.
Clearly a "1" has to go in the first position. It's the "only logical possibility." But I can arrive at the same conclusion by reasoning in the negative:
Assume c1=2 -- contradiction.
Assume c1=3 -- contradiction.
Assume c1=4 -- contradiction.
Assume c1=5 -- contradiction.
Assume c1=6 -- contradiction.
Assume c1=7 -- contradiction.
Assume c1=8 -- contradiction.
Assume c1=9 -- contradiction.
Therefore c1=1.
This is in fact the chain of thought that flashes through your mind in an instant when you see "the only logical possibility."
The only way to solve a Sudoku puzzle is by noticing the possible contradictions and avoiding all of them. Sometimes the possible contradictions are easy to spot. Sometimes they're very subtle. I think that's what distinguishes the easier puzzles from the harder ones. dcb |
|
Back to top |
|
|
jiger Guest
|
Posted: Sun Sep 11, 2005 1:02 pm Post subject: Other puzzles - a very tough swordfishpuzzle |
|
|
David Bryant wrote:
>The only way to solve a Sudoku puzzle is by noticing the possible contradictions..
In r 1/c 4 there should obviously be a 3 or a 7 (after having introduced the first 13 digits)
If you try with a 7, you will end up with no rome for an 8 in the upper right 3x3 block. Thus it must be a 3.
The rest is more or less a piece of cake. Thus you only need to arrive at one difficult move after the first 13.
Jiger - beginner |
|
Back to top |
|
|
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
|