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   

Killer Swordfish example
Goto page 1, 2, 3, 4  Next
 
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: Sat Apr 16, 2005 11:50 pm    Post subject: Killer Swordfish example Reply with quote

Here's a 'killer' Swordfish example, by which I mean a 3x3 puzzle that will admit a logical solution if and only if you find the swordfish that lurks within:

Code:
 . . . | . . . | . . .
 . . 9 | . 1 8 | 3 2 .
 7 . 4 | 5 . . | . . 1
----------------------
 . 6 . | . 3 . | . . .
 . 2 . | . . . | . 4 .
 . . . | . 7 . | . 5 .
----------------------
 3 . . | . . 9 | 7 . 6
 . 9 5 | 1 6 . | 8 . .
 . . . | . . . | . . .


Standard rules take us to the following point:

Code:
 . . . | . . . | . . .
 6 5 9 | . 1 8 | 3 2 .
 7 . 4 | 5 2 . | 9 . 1
----------------------
 . 6 . | . 3 . | . . .
 . 2 . | . . . | . 4 .
 . . . | . 7 . | . 5 .
----------------------
 3 . . | . 5 9 | 7 1 6
 . 9 5 | 1 6 7 | 8 3 .
 1 7 6 | . . . | . 9 .


where we make further eliminations based upon the following observations:

The value 8 in Box [3,2] must lie in Row 9.
The values 3 and 7 occupy the cells (5,3) and (5,9) in some order.
The values 4 and 5 occupy the cells (1,7) and (9,7) in some order.
The value 2 in Box [2,3] must lie in Column 7.

Now consider the 4s. There are two candidate positions in Row 2 - the cells (2,4) and (2,9). More interestingly, consider Row 7, where there are two candidate cells - (7,4) and (7,2). Furthermore, there are two candidate cells in each of Box [3,1] - (7,2) and (8,1) - and Row 8 - (8,1) and (8,9). It follows that exactly one of the cells (7,4) and (8,9) must contain a 4. We now have the classic X-Wings/Swordfish construction - 4s must occupy the cells (2,4) and (8,9) or the cells (2,9) and (7,4), which enables us to eliminate the value 4 as a candidate for the remaining cells in Columns 4 and 9.

Even after all that effort, we're still not left with a clear move! We have to make further eliminations based upon the following observations:

The value 4 in Column 6 must lie in Box [2,2].
The values 4 and 5 occupy the cells (4,1) and (4,6) in some order.
The values 1, 2, 4 and 5 occupy the cells (4,6), (5,6), (6,6) and (9,6) in some order.

before we see that the value 2 is the only candidate for the cell (9,6), after which all is straightforward.

I think that it's safe to say that this is the toughest 'purely logical' puzzle we've yet seen.
Back to top
View user's profile Send private message Visit poster's website
Simes

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

Items
PostPosted: Sun Apr 17, 2005 12:32 pm    Post subject: Reply with quote

Sorry rubylips, but you don't need swordfish to solve this puzzle.

I was about to try and implement swordfish, and thought I'd see how far I'd get without it. The answer was all the way.

Here's the log:

Note: Cell coordinates are in (column,row) format
(2,2) = 5 : only possible value for this cell
(8,7) = 1 : only possible value for this cell
(8,8) = 3 : only possible value for this cell
(8,9) = 9 : only possible value for this cell
(2,9) = 7 : only cell in column 2 that can contain 7
(5,7) = 5 : only cell in row 7 that can contain 5
(6,8) = 7 : only cell in row 8 that can contain 7
block 1: row 1 must contain 2, removing 2 from candidates for cell(s) (4,1)(5,1)(6,1)
block 6: column 7 must contain 6, removing 6 from candidates for cell(s) (7,1)(7,3)
(1,2) = 6 : only possible value for this cell
(7,3) = 9 : only possible value for this cell
(3,9) = 6 : only cell in column 3 that can contain 6
(1,9) = 1 : only cell in row 9 that can contain 1
block 7: row 7 must contain 8, removing 8 from candidates for cell(s) (4,7)
blocks 1 and 7 must contain 2 in columns 1 and 3 - removing 2 from candidates for cell(s) (1,9)(3,9)
(5,3) = 2 : only possible value for this cell
X-Wing found for rows 1 and 9 in columns 5 and 7 for 4 - updating cell(s) (4,1)(6,1)(9,1)(1,9)(2,9)(4,9)(6,9)(9,9)
X-Wing found for columns 5 and 7 in rows 1 and 9 for 4 - updating cell(s) (5,7)
column 6: unique subset 236 in cells (6,1)(6,3)(6,9) - updating candidates for cell(s) (6,4)(6,5)(6,6)
column 6: unique subset 36 in cells (6,1)(6,3) - updating candidates for cell(s) (6,9)
column 7: unique subset 126 in cells (7,4)(7,5)(7,6) - updating candidates for cell(s) (7,9)
row 5: unique subset 15689 in cells (1,5)(4,5)(5,5)(6,5)(7,5) - updating candidates for cell(s) (3,5)(9,5)
block 2: unique subset 36 in cells (6,1)(6,3) - updating candidates for cell(s) (4,1)
block 5: unique subset 145 in cells (6,4)(6,5)(6,6) - updating candidates for cell(s) (4,4)(4,6)
block 6: unique subset 126 in cells (7,4)(7,5)(7,6) - updating candidates for cell(s) (9,4)(9,6)
(6,9) = 2 : only possible value for this cell
(9,9) = 5 : only possible value for this cell
(4,9) = 3 : only cell in column 4 that can contain 3
(7,1) = 5 : only cell in column 7 that can contain 5
(9,8) = 2 : only cell in column 9 that can contain 2
(5,1) = 4 : only cell in row 1 that can contain 4
(9,2) = 4 : only cell in row 2 that can contain 4
(3,7) = 2 : only cell in row 7 that can contain 2
(1,8) = 4 : only cell in row 8 that can contain 4
(7,9) = 4 : only cell in row 9 that can contain 4
(5,9) = 8 : only cell in row 9 that can contain 8
(1,1) = 2 : only cell in block 1 that can contain 2
(2,6) = 4 : only cell in block 4 that can contain 4
(2,7) = 8 : only cell in block 7 that can contain 8
(4,1) = 9 : only cell in block 2 that can contain 9
(6,4) = 4 : only cell in block 5 that can contain 4
(5,5) = 9 : only cell in block 5 that can contain 9
(4,7) = 4 : only cell in block 8 that can contain 4
block 1: column 3 must contain 8, removing 8 from candidates for cell(s) (3,4)(3,6)
block 1: row 1 must contain 8, removing 8 from candidates for cell(s) (8,1)(9,1)
block 4: column 3 must contain 1, removing 1 from candidates for cell(s) (3,1)
block 4: column 3 must contain 3, removing 3 from candidates for cell(s) (3,1)
block 5: row 5 must contain 5, removing 5 from candidates for cell(s) (1,5)
block 3: column 8 must contain 8, removing 8 from candidates for cell(s) (8,4)
blocks 3 and 6 must contain 7 in columns 8 and 9 - removing 7 from candidates for cell(s) (9,2)
blocks 4 and 6 must contain 3 in rows 5 and 6 - removing from 3 candidate for cell(s) (2,6)
(1,5) = 8 : only possible value for this cell
(1,6) = 9 : only possible value for this cell
(2,3) = 3 : only possible value for this cell
(3,1) = 8 : only possible value for this cell
(4,2) = 7 : only possible value for this cell
(4,5) = 6 : only possible value for this cell
(6,3) = 6 : only possible value for this cell
(6,6) = 1 : only possible value for this cell
(7,5) = 1 : only possible value for this cell
(8,3) = 8 : only possible value for this cell
(8,4) = 7 : only possible value for this cell
(9,1) = 7 : only possible value for this cell
(9,5) = 3 : only possible value for this cell
(9,6) = 8 : only possible value for this cell
(1,4) = 5 : only cell in column 1 that can contain 5
(2,1) = 1 : only cell in column 2 that can contain 1
(3,4) = 1 : only cell in column 3 that can contain 1
(3,6) = 3 : only cell in column 3 that can contain 3
(3,5) = 7 : only cell in column 3 that can contain 7
(4,4) = 8 : only cell in column 4 that can contain 8
(6,1) = 3 : only cell in column 6 that can contain 3
(6,5) = 5 : only cell in column 6 that can contain 5
(7,6) = 6 : only cell in column 7 that can contain 6
(8,1) = 6 : only cell in column 8 that can contain 6
(9,4) = 9 : only cell in column 9 that can contain 9
(7,4) = 2 : only cell in row 4 that can contain 2
(4,6) = 2 : only cell in row 6 that can contain 2
Completed
Back to top
View user's profile Send private message Visit poster's website
IJ

Joined: 15 Apr 2005
Posts: 16
:

Items
PostPosted: Sun Apr 17, 2005 2:46 pm    Post subject: Reply with quote

Yep, mine solved it too - Back to that question of how to set a puzzle of a given difficulty! Sad to say that I haven't had any bright ideas yet...
Back to top
View user's profile Send private message
rubylips

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

Items
PostPosted: Sun Apr 17, 2005 2:58 pm    Post subject: Reply with quote

You're right! The puzzle's more of a prod with a feather duster than a killer. You have to admit, though, that the swordfish is more elegant than the X-Wing combined with the various other deductions.

Back to the drawing board ...
Back to top
View user's profile Send private message Visit poster's website
rubylips

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

Items
PostPosted: Sun Apr 17, 2005 9:46 pm    Post subject: Reply with quote

I'm back with yet another attempt but, as I've learned my lesson from last time, I'll label it 'Prime Suspect' instead of 'Killer'.

Consider the following puzzle:

Code:
 . . . | 4 7 . | 6 . .
 . . 4 | . . . | 3 . 5
 9 2 . | . . . | . . .
----------------------
 . 3 1 | . . . | . . .
 . . . | 9 3 6 | . . .
 . . . | . . . | 2 8 .
----------------------
 . . . | . . . | . 1 6
 4 . 8 | . . . | 9 . .
 . . 7 | . 5 2 | . . .


Standard rules take us as far as:

Code:
 . . . | 4 7 9 | 6 2 .
 . . 4 | . . . | 3 9 5
 9 2 6 | . . . | . . .
----------------------
 . 3 1 | . . . | . 6 9
 . . . | 9 3 6 | . . .
 . . 9 | . . . | 2 8 3
----------------------
 . 5 . | 8 9 4 | 7 1 6
 4 . 8 | . . . | 9 5 2
 . 9 7 | . 5 2 | . 3 .


Whereupon we further deduce:

The value 2 in Box [2,1] must lie in Row 5.
The value 7 in Row 5 must lie in Box [2,3].
The value 8 in Box [2,1] must lie in Row 5.
The values 3 and 5 occupy the cells (1,1) and (1,3) in some order.
The values 2 and 6 occupy the cells (2,4) and (2,5) in some order.
The values 3 and 5 occupy the cells (3,4) and (3,6) in some order.
The values 3 and 7 occupy the cells (8,4) and (8,6) in some order.

We now have a swordfish in the 1s. There are two candidate positions in Column 6 - (2,6) and (6,6). (The apparent candidate positions (3,6) and (8.6) have been eliminated in our further deductions). More interestingly, we have two candidate positions in Column 1 - (2,1) and (9,1) - two in Row 9 - (9,1) and (9,4) - and two in Column 4 - (9,4) and (6,4). It follows that exactly one of the cells (2,1) and (6,4) must be occupied by a 1, which gives us the required construction - 1s must appear in the cells (2,6) and (6,4) or the cells (2,1) and (6,6) - to eliminate 1s as candidates elsewhere in Rows 2 and 6. The value 4 is left as the only candidate for (6,5), after which all is plain sailing.

Were we to fail to spot the swordfish, we'd be forced to use Nishio (this is a trivial statement since Swordfish is a special case of Nishio) or to guess - there's no X-Wings construction here.

Gentlemen of the jury, I rest my case. I await your verdict with interest.
Back to top
View user's profile Send private message Visit poster's website
IJ

Joined: 15 Apr 2005
Posts: 16
:

Items
PostPosted: Mon Apr 18, 2005 8:28 am    Post subject: IJ Reply with quote

It's a good'un - well done.
Back to top
View user's profile Send private message
Simes

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

Items
PostPosted: Mon Apr 18, 2005 8:43 am    Post subject: Reply with quote

Seconded!
Back to top
View user's profile Send private message Visit poster's website
rubylips

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

Items
PostPosted: Mon Apr 18, 2005 10:31 am    Post subject: Reply with quote

Here's another swordfish puzzle. It's been left as an exercise to the reader.

Code:
 . 6 . | . . 4 | 9 1 .
 . . 4 | . . . | . . .
 3 . . | 5 . 8 | . . .
----------------------
 . . . | . 4 . | . . 3
 5 . . | . . . | . . 7
 2 . . | . 9 . | . . .
----------------------
 . . . | 7 . 2 | . . 5
 . . . | . . . | 8 . .
 . 1 3 | 8 . . | . 6 .
Back to top
View user's profile Send private message Visit poster's website
Simes

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

Items
PostPosted: Mon Apr 18, 2005 12:06 pm    Post subject: Reply with quote

errr... this latest one doesn't need swordfish. Confused
Back to top
View user's profile Send private message Visit poster's website
IJ

Joined: 15 Apr 2005
Posts: 16
:

Items
PostPosted: Mon Apr 18, 2005 1:31 pm    Post subject: Reply with quote

Seconded!
Back to top
View user's profile Send private message
rubylips

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

Items
PostPosted: Mon Apr 18, 2005 1:40 pm    Post subject: Reply with quote

Zut Alors! Shocked I agree that the first example could be solved throughout swordfish but I don't see it for this one - I'd be grateful if you could check my analysis as I fear I might have a bug in my solver.

It's straightforward to make it to here:

Code:
 . 6 5 | 3 . 4 | 9 1 .
 . . 4 | 9 . . | 3 5 .
 3 . . | 5 . 8 | . . .
----------------------
 . . . | . 4 . | . . 3
 5 4 . | . 8 3 | . . 7
 2 3 . | 6 9 . | . . 1
----------------------
 . . . | 7 . 2 | 1 . 5
 . 5 2 | 4 . . | 8 . 9
 . 1 3 | 8 5 9 | . 6 .


Whereupon we note:

The value 6 in Box [1,3] must lie in Column 9.
The value 7 in Box [1,2] must lie in Column 5.

which leads to the 3-leg swordfish observation:

7s must appear in the cells (3,7) and (9,1) or the cells (3,8) and (9,7).

The resulting eliminations in Rows 3 and 9 allow us to make the further elimnation:

The value 7 in Box [2,1] must lie in Column 3.

after which we deduce:

The cell (2,2) is the only candidate for the value 7 in Column 2.

and it's plain sailing from here.

Were swordfish unavailable, we could, I believe, only make progress with help from Nishio, as follows:

The move (1,1):= 7 would make it impossible to place the remaining 7s.

which would give us:

The value 8 is the only candidate for the cell (1,1).

after which all would be plain sailing. However, I don't see how the problem could be solved without Swordfish or Nishio.

Thanks for your time.
Back to top
View user's profile Send private message Visit poster's website
IJ

Joined: 15 Apr 2005
Posts: 16
:

Items
PostPosted: Mon Apr 18, 2005 1:58 pm    Post subject: Reply with quote

My solver doesn't provide a log, so I don't know how it did it, but it only has X-wings and my pattern for Nishio (i.e. the Jacko). I'll see if I can work out what it did and get back if no one else does in the mean time...
Back to top
View user's profile Send private message
Simes

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

Items
PostPosted: Mon Apr 18, 2005 2:03 pm    Post subject: Reply with quote

Here's my log:
Code:
Note: Cell coordinates are in (column,row) format
(5,9) = 5 : only possible value for this cell
(6,9) = 9 : only possible value for this cell
(4,8) = 4 : only cell in column 4 that can contain 4
(4,2) = 9 : only cell in column 4 that can contain 9
(5,5) = 8 : only cell in column 5 that can contain 8
(9,8) = 9 : only cell in column 9 that can contain 9
(3,1) = 5 : only cell in row 1 that can contain 5
(2,8) = 5 : only cell in row 8 that can contain 5
(3,8) = 2 : only cell in block 7 that can contain 2
(7,7) = 1 : only cell in block 9 that can contain 1
block 4: column 2 must contain 4, removing 4 from candidates for cell(s) (2,7)
block 7: column 1 must contain 7, removing 7 from candidates for cell(s) (1,1)(1,2)(1,4)
block 5: column 4 must contain 2, removing 2 from candidates for cell(s) (4,1)
block 5: column 6 must contain 7, removing 7 from candidates for cell(s) (6,2)
block 3: row 2 must contain 3, removing 3 from candidates for cell(s) (5,2)(6,2)
block 6: row 6 must contain 1, removing 1 from candidates for cell(s) (3,6)(4,6)(6,6)
block 9: column 8 must contain 3, removing 3 from candidates for cell(s) (8,2)
blocks 4 and 7 must contain 6 in columns 1 and 3 - removing 6 from candidates for cell(s) (3,8)
blocks 2 and 8 must contain 1 in columns 5 and 6 - removing 1 from candidates for cell(s) (6,4)(5,5)(6,5)
blocks 1 and 3 must contain 8 in rows 1 and 2 - removing 8 from candidate for cell(s) (3,1)
blocks 7 and 9 must contain 4 in rows 7 and 9 - removing 4 from candidate for cell(s) (7,7)
blocks 7 and 9 must contain 7 in rows 8 and 9 - removing 7 from candidate for cell(s) (2,8)(3,8)
blocks 8 and 9 must contain 3 in rows 7 and 8 - removing from 3 candidate for cell(s) (4,8)(7,7)
(1,1) = 8 : only possible value for this cell
(1,2) = 1 : only possible value for this cell
(4,1) = 3 : only possible value for this cell
(4,6) = 6 : only possible value for this cell
(6,2) = 6 : only possible value for this cell
(6,5) = 3 : only possible value for this cell
(6,8) = 1 : only possible value for this cell
(9,1) = 2 : only possible value for this cell
(9,2) = 8 : only possible value for this cell
(9,9) = 4 : only possible value for this cell
(1,7) = 4 : only cell in column 1 that can contain 4
(2,6) = 3 : only cell in column 2 that can contain 3
(5,3) = 1 : only cell in column 5 that can contain 1
(7,2) = 3 : only cell in column 7 that can contain 3
(9,6) = 1 : only cell in column 9 that can contain 1
(9,3) = 6 : only cell in column 9 that can contain 6
(5,1) = 7 : only cell in row 1 that can contain 7
(8,2) = 5 : only cell in row 2 that can contain 5
(2,3) = 2 : only cell in row 3 that can contain 2
(7,9) = 2 : only cell in row 9 that can contain 2
(3,3) = 9 : only cell in block 1 that can contain 9
(2,5) = 4 : only cell in block 4 that can contain 4
(2,7) = 9 : only cell in block 7 that can contain 9
(5,2) = 2 : only cell in block 2 that can contain 2
(8,8) = 7 : only cell in block 9 that can contain 7
block 1: column 2 must contain 7, removing 7 from candidates for cell(s) (2,4)
block 4: row 4 must contain 9, removing 9 from candidates for cell(s) (8,4)
block 7: column 3 must contain 8, removing 8 from candidates for cell(s) (3,4)(3,6)
block 9: row 7 must contain 3, removing 3 from candidates for cell(s) (5,7)
blocks 4 and 7 must contain 6 in columns 1 and 3 - removing 6 from candidates for cell(s) (1,7)
blocks 4 and 5 must contain 7 in rows 4 and 6 - removing from 7 candidate for cell(s) (2,6)
(1,8) = 6 : only possible value for this cell
(1,9) = 7 : only possible value for this cell
(2,2) = 7 : only possible value for this cell
(2,4) = 8 : only possible value for this cell
(3,6) = 7 : only possible value for this cell
(3,7) = 8 : only possible value for this cell
(5,7) = 6 : only possible value for this cell
(5,8) = 3 : only possible value for this cell
(6,6) = 5 : only possible value for this cell
(7,5) = 6 : only possible value for this cell
(7,6) = 4 : only possible value for this cell
(8,3) = 4 : only possible value for this cell
(8,4) = 2 : only possible value for this cell
(8,5) = 9 : only possible value for this cell
(8,6) = 8 : only possible value for this cell
(8,7) = 3 : only possible value for this cell
(1,4) = 9 : only cell in column 1 that can contain 9
(3,4) = 6 : only cell in column 3 that can contain 6
(4,5) = 2 : only cell in column 4 that can contain 2
(6,4) = 7 : only cell in column 6 that can contain 7
(7,4) = 5 : only cell in column 7 that can contain 5
(7,3) = 7 : only cell in column 7 that can contain 7
(4,4) = 1 : only cell in row 4 that can contain 1
(3,5) = 1 : only cell in row 5 that can contain 1
Completed
Back to top
View user's profile Send private message Visit poster's website
Simes

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

Items
PostPosted: Mon Apr 18, 2005 2:04 pm    Post subject: Reply with quote

Jacko?!
Back to top
View user's profile Send private message Visit poster's website
IJ

Joined: 15 Apr 2005
Posts: 16
:

Items
PostPosted: Mon Apr 18, 2005 2:09 pm    Post subject: Reply with quote

Ok, firstly all the candidate cells for 7 in box 7 are in column 1, this puts an 8 in r1c1...

And there's an X-wing of 6s in rows 4 & 6

and another X-wing of 7s in cols 3 & 6
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Goto page 1, 2, 3, 4  Next
Page 1 of 4

 
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