|
View previous topic :: View next topic |
Author |
Message |
| rubylips
| Joined: 07 Apr 2005 | Posts: 62 | : | Location: London | Items |
|
Posted: Fri Apr 08, 2005 4:04 pm Post subject: Swordfish example |
|
|
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 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 |
|
|
| rubylips
| Joined: 07 Apr 2005 | Posts: 62 | : | Location: London | Items |
|
Posted: Fri Apr 08, 2005 4:05 pm Post subject: |
|
|
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 |
|
|
| Simes
| Joined: 08 Apr 2005 | Posts: 71 | : | Location: North Yorkshire, UK | Items |
|
Posted: Fri Apr 08, 2005 5:37 pm Post subject: |
|
|
I think any 8) will be a cool guy unless you disable smilies. |
|
Back to top |
|
|
| kudosu Site Admin
| Joined: 04 Apr 2005 | Posts: 20 | : | Location: London | Items |
|
Posted: Fri Apr 08, 2005 10:16 pm Post subject: |
|
|
The offending emoticon has been removed. |
|
Back to top |
|
|
| Tony
| Joined: 11 Apr 2005 | Posts: 6 | : | Location: West Sussex | Items |
|
Posted: Mon Apr 11, 2005 4:04 am Post subject: Re: Swordfish example |
|
|
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 |
|
|
| AMcK
| Joined: 07 Apr 2005 | Posts: 89 | : | Location: Cambridge | Items |
|
Posted: Wed Apr 13, 2005 4:12 pm Post subject: |
|
|
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 |
|
|
| Tony
| Joined: 11 Apr 2005 | Posts: 6 | : | Location: West Sussex | Items |
|
Posted: Thu Apr 14, 2005 6:08 am Post subject: |
|
|
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 - 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 |
|
|
| AMcK
| Joined: 07 Apr 2005 | Posts: 89 | : | Location: Cambridge | Items |
|
Posted: Thu Apr 14, 2005 7:43 am Post subject: |
|
|
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 |
|
|
| rubylips
| Joined: 07 Apr 2005 | Posts: 62 | : | Location: London | Items |
|
Posted: Thu Apr 14, 2005 10:42 pm Post subject: |
|
|
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 |
|
|
|
|
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
|