|
View previous topic :: View next topic |
Author |
Message |
| rubylips
| Joined: 07 Apr 2005 | Posts: 62 | : | Location: London | Items |
|
Posted: Thu Apr 14, 2005 11:01 pm Post subject: Swordfish definition |
|
|
The following definition of the Swordfish - or Generalized X-Wings - pattern has been copied across from the old Google Sudoku Programmers group.
The first quote is taken from the X-Wings topic.
Quote: | It's possible to generalize X-Wings a little further if we consider
boxes.
Suppose (1,1) and (2,3) are the only candidates for 3 in Box [1,1] and
that (9,1) and (9,3) are the only candidates for 3 in Row 9. X-Wings
reasoning allows us to eliminate any other candidates from Columns 1
and 3, even though the four cells don't form the classic rectangle.
Suppose that:
i. (1,1) and (2,3) are the only candidates for 3 in Box [1,1].
ii. (2,3) and (2,7) are the only candidates for 3 in Row 2.
iii. (2,7) and (3,9) are the only candidates for 3 in Box [1.3]
It's clearly the case the exactly one of (1,1) and (3,9) are 3s, in
which case if (6,1) and (6,9) are the only candidates for 3 in Row 7,
we are able to eliminate candidates from Columns 1 and 9. |
The second is taken from the Swordfish topic.
Quote: | Consider the following puzzle:
Code: | . . 9 | 6 3 . | . . .
. . . | . . . | 8 . .
4 5 . | . . . | . 1 .
----------------------
. . . | . . . | . 7 3
. . . | 8 2 5 | . . .
1 9 . | . . . | . . .
----------------------
. 3 . | . . . | . 9 6
. . 7 | . . . | . . .
. . . | . 1 4 | 2 . . |
Straightforward eliminations take us to:
Code: | 8 . 9 | 6 3 . | 7 . .
. . . | . . . | 8 . .
4 5 . | . . . | . 1 .
----------------------
. . . | 1 . . | . 7 3
. . . | 8 2 5 | 9 . 1
1 9 . | . . . | . 2 8
----------------------
. 3 . | . . . | . 9 6
. . 7 | . . . | . 8 .
. . . | . 1 4 | 2 . 7 |
at which point we further deduce:
The value 3 in Box [2,1] must lie in Row 5.
The value 4 in Box [1,3] must lie in Row 1.
The value 5 in Box [1,3] must lie in Row 1.
The value 5 in Column 7 must lie in Box [2,3].
The value 6 in Box [3,1] must lie in Row 9.
The value 7 in Box [1,2] must lie in Row 3.
The value 8 in Box [3,1] must lie in Row 9.
The values 4 and 5 occupy the cells (1,8) and (1,9) in some order.
The values 4 and 5 occupy the cells (2,4) and (2,5) in some order.
The values 3 and 6 occupy the cells (3,3) and (3,7) in some order.
The values 1 and 4 occupy the cells (7,3) and (7,7) in some order.
The values 3 and 7 occupy the cells (2,1) and (5,1) in some order.
The values 1 and 4 occupy the cells (7,3) and (8,2) in some order.
The value 2 in Column 1 must lie in Box [3,1].
The values 2 and 8 occupy the cells (4,2) and (4,3) in some order.
Think about the 4s.
'The value 4 in Box [1,3] must lie in Row 1' tells us that the only
valid positions for the 4s are (8,9) and (1,9) in Column 9, (1,9) and
(1,8) in Row 1 and (1,8) and (5,8) in Column 8. It follows that exactly
one of (8,9) and (5,8) must be a 4.
'The values 2 and 8 occupy the cells (4,2) and (4,3) in some order'
tells us that the only valid positions for the 4s in Column 2 are (5,2)
and (8,2).
Put the two together and we have a 'Generalized X-Wings' pattern - or a
Swordfish. As the solver tells us, '4s must appear in the cells (5,2)
and (8,9) or the cells (5,8) and (8,2)', so we are able to eliminate
the remaining candidate positions for 4s in Rows 5 and 8. Pure logic,
pure class. (Unfortunately, it's necessary to nishio - now officially a
verb - the 6s in order to complete the puzzle. I'll try to come up with
something better later today.)
I call the long sequences of 2-candidate rows, columns and boxes
'strings' in my code. I see two wings - an upper wing and a lower wing
- separated by struts, which resembles an old biplane. The presence of
string reminded me of the expression 'Flying Stringbag' - the nickname
for the venerable Fairey Swordfish - hence the name. |
|
|
Back to top |
|
|
| Tony
| Joined: 11 Apr 2005 | Posts: 6 | : | Location: West Sussex | Items |
|
Posted: Fri Apr 15, 2005 9:53 am Post subject: Re: Swordfish definition |
|
|
rubylips wrote: |
Consider the following puzzle:
Code: | . . 9 | 6 3 . | . . .
. . . | . . . | 8 . .
4 5 . | . . . | . 1 .
----------------------
. . . | . . . | . 7 3
. . . | 8 2 5 | . . .
1 9 . | . . . | . . .
----------------------
. 3 . | . . . | . 9 6
. . 7 | . . . | . . .
. . . | . 1 4 | 2 . . |
Straightforward eliminations take us to:
Code: | 8 . 9 | 6 3 . | 7 . .
. . . | . . . | 8 . .
4 5 . | . . . | . 1 .
----------------------
. . . | 1 . . | . 7 3
. . . | 8 2 5 | 9 . 1
1 9 . | . . . | . 2 8
----------------------
. 3 . | . . . | . 9 6
. . 7 | . . . | . 8 .
. . . | . 1 4 | 2 . 7 |
|
Becoming clearer but the statement of 4's in column 2 as (5,2) or (8,2) can be made directly since they are the only two choices in that column
You then have the classic X-Wing rectangle, with one of the corners pushed in Code: |
- - - - - - - 4 4
-
-
-
- 4 - - - - - 4 -
-
-
- 4 - - - - - - 4
- |
Since all these 4's are now tied together as a chain/string, we can then elimante any other 4's in the rows 5,8 since the paired connections are in the columns + row 1, which implies row 8 - hence the modified X-Wing.
What I am really looking for is a 'relatively' straightforward way to code this type of pattern recognition
Again, many thanks for the detail here. |
|
Back to top |
|
|
| IJ
| Joined: 15 Apr 2005 | Posts: 16 | : | | Items |
|
Posted: Fri Apr 15, 2005 12:29 pm Post subject: |
|
|
This is a generalisation of the X-wing.
Look for N columns (2 for X-wing, 3 for the Swordfish, 4 for a Jellyfish, 5 for a Squirmbag) with only two candidate cells for a given digit (4 in this example). If these fall on exactly N common rows, and each of those rows has at least 2 candidate cells, then all N rows can be cleared of that digit (except it the defining cells!).
Likewise for N rows with N common columns.
Note - I believe Rubylips comment about generalising X-wing to boxes is a red herring because it would always be solved by rule 1 anyway.
Swordfish is quite tough to program, as you could have any number of columns (say 5) with only two positions for a digit, but you need to test each combination of three of those five columns (123, 124, 125, 134, 135, 145, 234, 235, 245 & 345) to be sure of finding the Swordfish. But if you've coded rule 2 or 3, then this should be a breaze! Or not ) |
|
Back to top |
|
|
| Tony
| Joined: 11 Apr 2005 | Posts: 6 | : | Location: West Sussex | Items |
|
Posted: Fri Apr 15, 2005 9:41 pm Post subject: |
|
|
IJ wrote: | This is a generalisation of the X-wing.
Look for N columns (2 for X-wing, 3 for the Swordfish, 4 for a Jellyfish, 5 for a Squirmbag) with only two candidate cells for a given digit (4 in this example). If these fall on exactly N common rows, and each of those rows has at least 2 candidate cells, then all N rows can be cleared of that digit (except it the defining cells!). |
Thanks - this is exactly the kind of input I was looking for. As you not that easy, but not that Hard either - will give it a go. |
|
Back to top |
|
|
| rubylips
| Joined: 07 Apr 2005 | Posts: 62 | : | Location: London | Items |
|
Posted: Fri Apr 15, 2005 11:20 pm Post subject: |
|
|
I'll provide a pseudo-code implementation of Swordfish if you like but I feel that first I have to provide a better example of a puzzle with a Swordfish pattern. The following puzzle permits a logical solution (no Nishio) if you detect the three-legged Swordfish within - however, it's a 4x3 puzzle!
Code: | .. 1 .. | 11 .. .. | 6 .. .. | .. .. 10
.. .. .. | .. 6 .. | .. .. .. | .. 7 2
.. 2 .. | 8 .. .. | .. 4 .. | 5 .. ..
.. 9 .. | 3 .. .. | .. .. .. | 12 .. ..
------------------------------------------
4 .. .. | 1 5 9 | .. .. .. | .. .. 6
3 .. .. | .. .. 12 | .. .. .. | .. .. 11
10 .. .. | .. .. .. | 8 .. .. | .. .. 1
11 .. .. | .. .. .. | 7 5 2 | .. .. 8
------------------------------------------
.. .. 12 | .. .. .. | .. .. 11 | .. 2 ..
.. .. 6 | .. 7 .. | .. .. 12 | .. 4 ..
8 5 .. | .. .. .. | .. 1 .. | .. .. ..
2 .. .. | .. .. 10 | .. .. 3 | .. 9 ..
|
|
|
Back to top |
|
|
| Tony
| Joined: 11 Apr 2005 | Posts: 6 | : | Location: West Sussex | Items |
|
Posted: Fri Apr 15, 2005 11:51 pm Post subject: |
|
|
rubylips wrote: | The following puzzle permits a logical solution (no Nishio) if you detect the three-legged Swordfish within - however, it's a 4x3 puzzle!
|
Thanks, but I will pass on 4x3. If (and when) I get the solver working for 3x3, then I may extend to 4x3 !! The algorithm from IJ is quite adequate in terms of an algorithm definition. |
|
Back to top |
|
|
| Animator
| Joined: 26 Apr 2005 | Posts: 18 | : | | Items |
|
Posted: Tue Apr 26, 2005 11:06 am Post subject: |
|
|
I find this explenation rather confusing:
Quote: |
'The value 4 in Box [1,3] must lie in Row 1' tells us that the only
valid positions for the 4s are (8,9) and (1,9) in Column 9, (1,9) and
(1,8) in Row 1 and (1,8) and (5,8) in Column 8. It follows that exactly
one of (8,9) and (5,8) must be a 4.
'The values 2 and 8 occupy the cells (4,2) and (4,3) in some order'
tells us that the only valid positions for the 4s in Column 2 are (5,2)
|
Allow me to summarise:
* row 1: valid positions: (1, 8) and (1, 9)
* column 9: valid positions (1, 9) and (8, 9)
* column 8: valid positions: (1, 8) and (5, 8)
Now, if the values 2 and 8 have to occopy (4, 2) and (4, 3), then box (2, 1) has to have a 4 on row 5: column 1 already has one, and row 4 is full, right?
This means that (5, 8) cannot be 4, meaning that (1, 8) has to be 4 (by which you can fill in all other 4's)...
Or am I seeing it wrong? |
|
Back to top |
|
|
| rubylips
| Joined: 07 Apr 2005 | Posts: 62 | : | Location: London | Items |
|
Posted: Tue Apr 26, 2005 12:12 pm Post subject: |
|
|
This post concerns the following position:
Code: | 8 . 9 | 6 3 . | 7 . .
. . . | . . . | 8 . .
4 5 . | . . . | . 1 .
----------------------
. . . | 1 . . | . 7 3
. . . | 8 2 5 | 9 . 1
1 9 . | . . . | . 2 8
----------------------
. 3 . | . . . | . 9 6
. . 7 | . . . | . 8 .
. . . | . 1 4 | 2 . 7 |
Quote: | Allow me to summarise:
* row 1: valid positions: (1, 8) and (1, 9)
* column 9: valid positions (1, 9) and (8, 9)
* column 8: valid positions: (1, 8) and (5, 8) |
Agreed. We infer from these three observations that exactly one of the cells (5,8) and (8,9) must contain the value 4, though we don't know which.
Quote: | Now, if the values 2 and 8 have to occupy (4, 2) and (4, 3), then box (2, 1) has to have a 4 on row 5: column 1 already has one, and row 4 is full, right? |
I don't agree. I don't follow the logic here at all. Look at the final solution - Box [2,1] has its 4 on Row 6.
Code: | 8 1 9 | 6 3 2 | 7 5 4
3 7 2 | 4 5 1 | 8 6 9
4 5 6 | 7 9 8 | 3 1 2
----------------------
5 2 8 | 1 4 9 | 6 7 3
7 6 3 | 8 2 5 | 9 4 1
1 9 4 | 3 7 6 | 5 2 8
----------------------
2 3 1 | 5 8 7 | 4 9 6
9 4 7 | 2 6 3 | 1 8 5
6 8 5 | 9 1 4 | 2 3 7 |
The key is to consider Column 2. At first inspection, there are three candidate positions for the value 4 in Column 2: (4,2), (5,2) and (8,2). However, the observation 'The values 2 and 8 occupy the cells (4,2) and (4,3) in some order' removes (4,2) as a candidate, which means that exactly one of (5,2) and (8,2) must contain the value 4.
Given that exactly one of the pair (5,8) and (8,9) and exactly one of the pair (5,2) and (8,2) must contain the value 4, we infer that:
Quote: | '4s must appear in the cells (5,2) and (8,9) or the cells (5,8) and (8,2)', so we are able to eliminate the remaining candidate positions for 4s in Rows 5 and 8. |
As the original post states, this observation is insufficient to allow a straightforward completion of the puzzle. See the 'Swordfish Compendium' topic on the 'Plaintext Puzzles' forum for better examples. |
|
Back to top |
|
|
| Animator
| Joined: 26 Apr 2005 | Posts: 18 | : | | Items |
|
Posted: Tue Apr 26, 2005 12:14 pm Post subject: |
|
|
Indeed... for some reason I missed cell (6, 3)... silly me
(Should I remove my previous reply or not? (so that others aren't confused by it)) |
|
Back to top |
|
|
| rubylips
| Joined: 07 Apr 2005 | Posts: 62 | : | Location: London | Items |
|
Posted: Tue Apr 26, 2005 12:25 pm Post subject: |
|
|
Personally, I don't like to see messages edited (or - worse still - deleted) after posting, as it confuses things for later readers. Everyone makes mistakes now and again - see the number of faulty swordfish puzzles I've proposed. |
|
Back to top |
|
|
| fissh
| Joined: 08 Jun 2005 | Posts: 2 | : | | Items |
|
Posted: Fri Jun 10, 2005 5:25 am Post subject: |
|
|
Hi!
Who can help me!
I don't understand this: (marked with ???)
Code: |
8 . 9 | 6 3 . | 7 . .
. . . | . . . | 8 . .
4 5 . | . . . | . 1 .
----------------------
. . . | 1 . . | . 7 3
. . . | 8 2 5 | 9 . 1
1 9 . | . . . | . 2 8
----------------------
. 3 . | . . . | . 9 6
. . 7 | . . . | . 8 .
. . . | . 1 4 | 2 . 7
|
OK The value 3 in Box [2,1] must lie in Row 5.
OK The value 4 in Box [1,3] must lie in Row 1.
OK The value 5 in Box [1,3] must lie in Row 1.
OK The value 5 in Column 7 must lie in Box [2,3].
OK The value 6 in Box [3,1] must lie in Row 9.
OK The value 7 in Box [1,2] must lie in Row 3.
OK The value 8 in Box [3,1] must lie in Row 9.
OK The values 4 and 5 occupy the cells (1,8) and (1,9) in some order.
OK The values 4 and 5 occupy the cells (2,4) and (2,5) in some order.
OK The values 3 and 6 occupy the cells (3,3) and (3,7) in some order.
??? The values 1 and 4 occupy the cells (7,3) and (7,7) in some order.
??? The values 3 and 7 occupy the cells (2,1) and (5,1) in some order.
??? The values 1 and 4 occupy the cells (7,3) and (8,2) in some order.
??? The value 2 in Column 1 must lie in Box [3,1].
??? The values 2 and 8 occupy the cells (4,2) and (4,3) in some order. |
|
Back to top |
|
|
| abailes
| Joined: 07 Jun 2005 | Posts: 2 | : | Location: London | Items |
|
Posted: Fri Jun 10, 2005 6:01 am Post subject: |
|
|
Fissh,
If you got the logic of the previous three steps, I don't get why the next ones are any harder.
Taking the first one:
In Row 7, there is only two places that a 1 can go. Not in Column one (because of the 1 in (6,1)), not in the center box because of the 1 there in (9,5). That only leaves (7,3) and (7,7).
Similarly, there are only two places a 4 can go in that row. It cannot go in Column one because of the 4 in (3,1) or in the center box because of the 4 in (9,6).
Given two numbers that can only fit in two places in that row, that is all the logic you need. We've just established that you cannot put them anywhere else and if you put a third number in one of those two cells you will not have enough spaces left to put the 1 and 4 in that row.
Is that enough? |
|
Back to top |
|
|
| Simes
| Joined: 08 Apr 2005 | Posts: 71 | : | Location: North Yorkshire, UK | Items |
|
|
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
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|