Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Swordfish definition

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
rubylips

Joined: 07 Apr 2005
Posts: 62
:
Location: London

Items
PostPosted: Thu Apr 14, 2005 11:01 pm    Post subject: Swordfish definition Reply with quote

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
View user's profile Send private message Visit poster's website
Tony

Joined: 11 Apr 2005
Posts: 6
:
Location: West Sussex

Items
PostPosted: Fri Apr 15, 2005 9:53 am    Post subject: Re: Swordfish definition Reply with quote

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 Cool

Again, many thanks for the detail here.
Back to top
View user's profile Send private message
IJ

Joined: 15 Apr 2005
Posts: 16
:

Items
PostPosted: Fri Apr 15, 2005 12:29 pm    Post subject: Reply with quote

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 Surprised)
Back to top
View user's profile Send private message
Tony

Joined: 11 Apr 2005
Posts: 6
:
Location: West Sussex

Items
PostPosted: Fri Apr 15, 2005 9:41 pm    Post subject: Reply with quote

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. Cool
Back to top
View user's profile Send private message
rubylips

Joined: 07 Apr 2005
Posts: 62
:
Location: London

Items
PostPosted: Fri Apr 15, 2005 11:20 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Tony

Joined: 11 Apr 2005
Posts: 6
:
Location: West Sussex

Items
PostPosted: Fri Apr 15, 2005 11:51 pm    Post subject: Reply with quote

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 Shocked extend to 4x3 !! The algorithm from IJ is quite adequate in terms of an algorithm definition.
Back to top
View user's profile Send private message
Animator

Joined: 26 Apr 2005
Posts: 18
:

Items
PostPosted: Tue Apr 26, 2005 11:06 am    Post subject: Reply with quote

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
View user's profile Send private message
rubylips

Joined: 07 Apr 2005
Posts: 62
:
Location: London

Items
PostPosted: Tue Apr 26, 2005 12:12 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Animator

Joined: 26 Apr 2005
Posts: 18
:

Items
PostPosted: Tue Apr 26, 2005 12:14 pm    Post subject: Reply with quote

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
View user's profile Send private message
rubylips

Joined: 07 Apr 2005
Posts: 62
:
Location: London

Items
PostPosted: Tue Apr 26, 2005 12:25 pm    Post subject: Reply with quote

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. Embarassed
Back to top
View user's profile Send private message Visit poster's website
fissh

Joined: 08 Jun 2005
Posts: 2
:

Items
PostPosted: Fri Jun 10, 2005 5:25 am    Post subject: Reply with quote

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
View user's profile Send private message
abailes

Joined: 07 Jun 2005
Posts: 2
:
Location: London

Items
PostPosted: Fri Jun 10, 2005 6:01 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
Simes

Joined: 08 Apr 2005
Posts: 71
:
Location: North Yorkshire, UK

Items
PostPosted: Fri Jun 10, 2005 7:23 am    Post subject: Reply with quote

fissh, why can't you just choose one of the forums to post in?

http://www.sudoku.com/forums/viewtopic.php?p=2742&sid=70c04e1868d864433ee09599da915649
_________________
Simes
www.sadmansoftware.com/sudoku
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron