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 example

 
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: Fri Apr 08, 2005 4:04 pm    Post subject: Swordfish example Reply with quote

Here's an interesting example of a puzzle with a purely logical solution that involves X-Wings and Swordfish:

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


Standard rules take us to the following:

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


where we further deduce:

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

The solver now tells us:

5s must appear in the cells (2,5) and (8,8) or the cells (2,8) and (8,5).
8s must appear in the cells (2,2) and (8,5) or the cells (8,2) and (2,5).
8s must appear in the cells (3,1) and (4,3) or the cells (3,4) and (4,1).

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

Let's analyse these occurrences of X-Wings & Swordfish.

i. X-Wing
The value 5 trivially has two candidate cells in Columns 5 and 8, which allows us to eliminate candidates in Rows 2 and 8.

ii. X-Wing
The value 8 has two candidates in Rows 2 and 8, which allows us to eliminate candidates in Columns 2 and 5 (which leaves 5 as the only candidate for (1,2) ).

iii. Swordfish
The value 8 has two candidates in Column 1 - remember that 2, 6 or 9 goes into (9,1). Here's the good bit: It has two candidates in Column 3 - (4,3) and (9,3) - two in Row 9 - (9,3) and (9,4) - and two in Column 4 - (9,4) and (3,4) - so there must be an 8 in (4,1) or (3,4). The conclusion is that we are free to eliminate 8 as a candidate for (3,7) and (3,9).

However Crying or Very sad it's still not a truly classic example because we could still solve it with X-Wings alone - the Swordfish eliminations aren't necessary in order to solve the puzzle!
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: Fri Apr 08, 2005 4:05 pm    Post subject: Reply with quote

Er, I think there must be a bug in the Emoticons software. I asked for the final one but not the cool guys.
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: Fri Apr 08, 2005 5:37 pm    Post subject: Reply with quote

I think any 8) will be a cool guy unless you disable smilies.
Back to top
View user's profile Send private message Visit poster's website
kudosu
Site Admin
Joined: 04 Apr 2005
Posts: 20
:
Location: London

Items
PostPosted: Fri Apr 08, 2005 10:16 pm    Post subject: Reply with quote

The offending emoticon has been removed. Cool
Back to top
View user's profile Send private message Send e-mail AIM Address
Tony

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

Items
PostPosted: Mon Apr 11, 2005 4:04 am    Post subject: Re: Swordfish example Reply with quote

rubylips wrote:
Here's an interesting example of a puzzle with a purely logical solution that involves X-Wings and Swordfish:

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


Hi,
My own solver can do this one, using as you proposed just X-Wing + everything else I have coded - see log below
Code:

 - - - - - - - - - - - - - - -
Iteration Number  1
 - - - - - - - - - - - - - - -
Testing for Unique Placements
 22 - Digit  6 only candidate for Cell( 4, 5)
 23 - Digit  7 only candidate for Cell( 4, 6)
 24 - Digit  2 only candidate for Cell( 6, 5)
 25 - Digit  9 only candidate for Cell( 6, 4)
Test all Digits for unique to Row/Col/Sq
 26 - Digit  4 Only position in Column( 9) is Cell( 1, 9)
 27 - Cell( 4, 8) = 4
 - - - - - - - - - - - - - - -
Iteration Number  2
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
 28 - Digit  1 Only position in Column( 8) is Cell( 1, 8)
 - - - - - - - - - - - - - - -
Iteration Number  3
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
 29 - Cell( 3, 6) = 1
 30 - Digit  1 Only position in Column( 5) is Cell( 9, 5)
 31 - Digit  3 Only position in Column( 5) is Cell( 1, 5)
 32 - Digit  3 Only position in Row( 3) is Cell( 3, 3)
 - - - - - - - - - - - - - - -
Iteration Number  4
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
 33 - Digit  1 Only position in Column( 2) is Cell( 6, 2)
 34 - Cell( 7, 3) = 1
 35 - Cell( 5, 2) = 3
 36 - Digit  3 Only position in Row( 6) is Cell( 6, 7)
 37 - Cell( 8, 3) = 4
 38 - Cell( 5, 1) = 6
 39 - Digit  7 Only position in Column( 1) is Cell( 1, 1)
 40 - Cell( 5, 3) = 9
 - - - - - - - - - - - - - - -
Iteration Number  5
 - - - - - - - - - - - - - - -
Testing for Unique Placements
 41 - Digit  7 only candidate for Cell( 5, 8)
 42 - Digit  5 only candidate for Cell( 6, 9)
 43 - Digit  7 only candidate for Cell( 6, 3)
Test all Digits for unique to Row/Col/Sq
 44 - Cell( 4, 7) = 1
All Digit =  1 allocated
 45 - Cell( 2, 3) = 2
 46 - Digit  3 Only position in Row( 7) is Cell( 7, 6)
 47 - Cell( 9, 8) = 3
All Digit =  3 allocated
 48 - Digit  4 Only position in Column( 6) is Cell( 2, 6)
 49 - Cell( 7, 4) = 4
All Digit =  4 allocated
 50 - Cell( 2, 7) = 7
 51 - Digit  7 Only position in Column( 9) is Cell( 9, 9)
 52 - Cell( 1, 6) = 9
 - - - - - - - - - - - - - - -
Iteration Number  6
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
 53 - Cell( 1, 4) = 2
 54 - Digit  6 Only position in Row( 2) is Cell( 2, 4)
 55 - Cell( 8, 4) = 7
All Digit =  7 allocated
 - - - - - - - - - - - - - - -
Iteration Number  7
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
Testing only Row/col in Square
Digit 9 occurs only in Row 8 - Square 9
Digit  9 not allowed Cell( 8, 2)
 - - - - - - - - - - - - - - -
Iteration Number  8
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
Testing only Row/col in Square
Testing for Pairs/Triplets [Rows]
Row  7 - Digit 6 is a Pair in the same Square ~ Columns =  7, 9
Digit  6 not allowed Cell( 8, 7)
Testing for Pairs/Triplets [Columns]
 - - - - - - - - - - - - - - -
Iteration Number  9
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
Testing only Row/col in Square
Testing for Pairs/Triplets [Rows]
Testing for Pairs/Triplets [Columns]
Testing for x,y Pairs of Digits [Rows]
Testing for x,y Pairs of Digits [Columns]
Testing Paired candidates [rows]
Candidate Pairs, 58 - row 9 Columns = 3, 4
Digit  5 not allowed Cell( 9, 1)
Digit  8 not allowed Cell( 9, 1)
Digit  5 not allowed Cell( 9, 2)
Digit  8 not allowed Cell( 9, 2)
Testing Paired candidates [columns]
 - - - - - - - - - - - - - - -
Iteration Number  10
 - - - - - - - - - - - - - - -
Testing for Unique Placements
Test all Digits for unique to Row/Col/Sq
Testing only Row/col in Square
Testing for Pairs/Triplets [Rows]
Testing for Pairs/Triplets [Columns]
Testing for x,y Pairs of Digits [Rows]
Testing for x,y Pairs of Digits [Columns]
Testing Paired candidates [rows]
Testing Paired candidates [columns]
Testing for X_Wings [Rows]
X_Wing Rule - Digit   8 at Rows  2 & 8 are a Pairs into Columns =  25
Digit  8 not allowed Cell( 1, 2)
Testing for X_Wings [Columns]
X_Wing Rule - Digit   5 at Columns  5 & 8 are a Pairs into Rows =  28
Digit  5 not allowed Cell( 2, 2)
Digit  5 not allowed Cell( 8, 2)
Digit  5 not allowed Cell( 8, 7)
 - - - - - - - - - - - - - - -
Iteration Number  11
 - - - - - - - - - - - - - - -
Testing for Unique Placements
 56 - Digit  5 only candidate for Cell( 1, 2)
 57 - Digit  8 only candidate for Cell( 1, 7)
 58 - Digit  6 only candidate for Cell( 3, 9)
 59 - Digit  2 only candidate for Cell( 5, 7)
 60 - Digit  8 only candidate for Cell( 5, 9)
 61 - Digit  2 only candidate for Cell( 7, 9)
 62 - Digit  9 only candidate for Cell( 8, 7)
 63 - Digit  5 only candidate for Cell( 8, 8)
 64 - Digit  9 only candidate for Cell( 2, 8)
 65 - Digit  5 only candidate for Cell( 3, 7)
 66 - Digit  5 only candidate for Cell( 7, 1)
 67 - Digit  6 only candidate for Cell( 7, 7)
 68 - Digit  8 only candidate for Cell( 8, 5)
 69 - Digit  8 only candidate for Cell( 9, 3)
 70 - Digit  5 only candidate for Cell( 9, 4)
 71 - Digit  8 only candidate for Cell( 2, 2)
 72 - Digit  5 only candidate for Cell( 2, 5)
 73 - Digit  9 only candidate for Cell( 3, 1)
 74 - Digit  8 only candidate for Cell( 3, 4)
 75 - Digit  8 only candidate for Cell( 4, 1)
All Digit =  8 allocated
 76 - Digit  5 only candidate for Cell( 4, 3)
All Digit =  5 allocated
 77 - Digit  6 only candidate for Cell( 8, 2)
 78 - Digit  2 only candidate for Cell( 8, 6)
 79 - Digit  2 only candidate for Cell( 9, 1)
All Digit =  2 allocated
 80 - Digit  9 only candidate for Cell( 9, 2)
All Digit =  9 allocated
 81 - Digit  6 only candidate for Cell( 9, 6)
All Digit =  6 allocated
 ====================
  Puzzle Solved
 ====================

After the X-Wing rule has been applied the Puzzle collapses to its solution - have some of my other rules elimnated the scenario for Swordfish ?

Do you have a Puzzle that must use Swordfish, so that I can get my head around that one. This one certainly gave the Solver something to chew on - many thanks.
Back to top
View user's profile Send private message
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Wed Apr 13, 2005 4:12 pm    Post subject: Reply with quote

It all seems very quiet on this list - and the previous one is closed down - is there anyone out there.

Regarding rubylips recent swordfish examples, my colouring algorithm now seems to be in agreement and produces similar arguments. Maybe it's the same algorithm in disguise or maybe it's more general. I can't be sure until I get a puzzle that shows the difference.

I've already published my solution to rubylips 8-April.

Here's the colouring solution to the rubylips original swordfish

. . 9 6 3 . . . .
. . . . . . 8 . .
4 5 . . . . . 1
. . . . . . . 7 3
. . . 8 2 5 . . .
1 9 . . . . . . .
. 3 . . . . . 9 6
. . 7 . . . . . .
. . . . 1 4 2 . .

Simple reductions to 51 remaining

8 12 9 6 3 12 7 45 45
37 1267 1236 45 45 129 8 36 29
4 5 36 279 789 2789 36 1 29
56 28 28 1 469 69 456 7 3
37 467 346 8 2 5 9 46 1
1 9 456 347 467 367 456 2 8
25 3 14 257 578 278 14 9 6
259 14 7 2359 569 2369 134 8 45
569 68 568 359 1 4 2 35 7

Colouring process

Conjugate row: digit 4 cells {1,8} {1,9}
Colour: {1,8} (a) {1,9} (b)
Conjugate row: digit 4 cells {2,4} {2,5}
Colour: {2,4} (c) {2,5} (d)
Conjugate row: digit 4 cells {4,5} {4,7}
Colour: {4,5} (e) {4,7} (f)
Conjugate row: digit 4 cells {7,3} {7,7}
Colour: {7,3} (g) {7,7} (h)
Conjugate column: digit 4 cells {5,2} {8,2}
Colour: {5,2} (i) {8,2} (j)
Conjugate column: digit 4 cells {2,4} {6,4}
Colour: {2,4} (c) {6,4} (d)
Conjugate column: digit 4 cells {1,8} {5,8}
Colour: {1,8} (a) {5,8} (b)
Conjugate column: digit 4 cells {1,9} {8,9}
Colour: {1,9} (b) {8,9} (a)
Conjugate box: digit 4 cells {2,4} {2,5}
Colour: {2,4} (c) {2,5} (d)
Conjugate box: digit 4 cells {1,8} {1,9}
Colour: {1,8} (a) {1,9} (b)
Conjugate box: digit 4 cells {7,3} {8,2}
Recolour: {5,2} (i->g)
Recolour: {8,2} (j->h)
Colour: {7,3} (g) {8,2} (h)
Non-conjugates: row 5 colours g b
Non-conjugates: row 8 colours h a
Non-conjugates: column 5 colours d e
Non-conjugates: column 7 colours f h
Non-conjugates: box 5 colours e d
Non-conjugates: box 6 colours f b
Non-conjugates: box 9 colours h a
Mutual exclusion: colours a/b h/g
Recolour: {5,2} (g->a)
Recolour: {7,3} (g->a)
Recolour: {7,7} (h->b)
Recolour: {8,2} (h->b)

Colour map for p=4

. . . . . . . a b
. . . c d . . . .
. . . . . . . . .
. . . . e . f . .
. a . . . . . b .
. . . d . . . . .
. . a . . . b . .
. b . . . . . . a
. . . . . . . . .

Hence eliminations in rows 5,8 for conjugate colours a/b

Row 5 reduction: digit 4 colours a/b cell {5,3} before 346 after 36
Row 8 reduction: digit 4 colours b/a cell {8,7} before 134 after 13

Please post some more swordfishes or I shall be forced to write my own generator.

Regards AMcK
Back to top
View user's profile Send private message Send e-mail
Tony

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

Items
PostPosted: Thu Apr 14, 2005 6:08 am    Post subject: Reply with quote

AMcK wrote:


I've already published my solution to rubylips 8-April.

Here's the colouring solution to the rubylips original swordfish

. . 9 6 3 . . . .
. . . . . . 8 . .
4 5 . . . . . 1
. . . . . . . 7 3
. . . 8 2 5 . . .
1 9 . . . . . . .
. 3 . . . . . 9 6
. . 7 . . . . . .
. . . . 1 4 2 . .
Regards AMcK


Now I am confused Confused - surely the above matrix is not the original puzzle - it has only 21 Digits, 60 remaining - have I missed something.

Are you or Rubyslips able to restate the original must have Swordfish puzzle ?

Thanks,
Tony
Back to top
View user's profile Send private message
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Thu Apr 14, 2005 7:43 am    Post subject: Reply with quote

Nive to know there is someone out there.
Apologies for the confusion.
There are in fact two "swordfish" puzzles set by Rubylips.
The original (to which my previous post refers) was

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

The 8-April one in this thread is

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

Rubylips has published "swordfish" solutions to the parts of the solution that Milobird's 3 rules won't touch.
My "colouring" algorithm is an attempt to generalise the "X-Wings" and "swordfish" processes as far as possible. It does seem to solve any puzzle that X-Wings or swordfish can solve, but that only suggests that it's equivalent.
Hope that resolves the confusion but do let me know if you want better descriptions of the algorithms or transcripts of them in operation.
Regards, AMcK
Back to top
View user's profile Send private message Send e-mail
rubylips

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

Items
PostPosted: Thu Apr 14, 2005 10:42 pm    Post subject: Reply with quote

Sorry for my recent inactivity - I've been in Munich for some beer, sausages and Champions League football. Somehow, Merseyside for the Semi won't seem the same ...

I've yet to devise a 'killer' Swordfish example, by which I mean a 3x3 puzzle that will admit a purely logical solution (no Nishio) if and only if the user solver has implemented the Swordfish pattern. However, I think I have a 4x3 puzzle that will satisfy these criteria - I'll check it tomorrow and post if necessary.

In the meantime, I'll copy the original defintions of the terms 'Nishio' (at least as I use it) and 'Swordfish' from the old Google Sudoku Programmers group.
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