A revival of Broken Wings

Advanced methods and approaches for solving Sudoku puzzles

Postby Obi-Wahn » Fri Jan 19, 2007 9:36 pm

Here's the last broken wing I found in my 21 examples.

Code: Select all
NoFish20
.---------------.---------------.---------------.
| 38   34   248 | 1    9    7   | 23   5    6   |
| 1    357  2567| 368  35   4   | 23   78   9   |
| 3567 9    567 | 368  2    56  | 1    78   4   |
:---------------+---------------+---------------:
| 2    6    3   | 4    1    8   | 5    9    7   |
| 57   8    157 | 9    35   2   | 4    6    13  |
| 9    45   145 | 36   7    56  | 8    2    13  |
:---------------+---------------+---------------:
| 68   1    68  | 5    4    9   | 7    3    2   |
| 357  357  57  | 2    6    1   | 9    4    8   |
| 4    2    9   | 7    8    3   | 6    1    5   |
'---------------'---------------'---------------'

  .  .  . | .  .  . | .  .  .
  .  5  5 | .  5  . | .  .  .
 *5  . @5 | .  . *5 | .  .  .
 ---------+---------+---------
  .  .  . | .  .  . | .  .  .
 *5  . @5 | .  5  . | .  .  .
  . *5 @5 | .  . *5 | .  .  .
 ---------+---------+---------
  .  .  . | .  .  . | .  .  .
 @5  5 -5 | .  .  . | .  .  .
  .  .  . | .  .  . | .  .  .


I finally managed to program a routine for broken wings into my solver. It allows any odd number of conjugated links, even grouped ones, but it doesn't find any broken wings in these examples that I didn't find manually.
So that still leaves 16 of the puzzles unsolvable.

BTW, I tried to solve an archive of 539 template solvable puzzles. 535 of them can be solved with ultimate fish, 200 can be solved with broken wings instead.

@Myth Jellies: I'll take some time to dig into your broken swordfish and try to understand what you are doing there.:)

Myth Jellies wrote:Perhaps now that we have gotten used to avoiding deadly patterns using URs, we will be a little more comfortable avoiding the deadly pattern represented by the broken wing.

The deadly pattern in URs is of a different kind. If it was true, the puzzle would have multiple solutions. If the deadly pattern in the Broken Wing was true, the puzzle would be unsolvable. So the only assumption is, that the puzzle has a solution, it's not a uniqueness exploit.
User avatar
Obi-Wahn
 
Posts: 63
Joined: 05 January 2007
Location: Darmstadt, Germany

Postby Myth Jellies » Fri Jan 19, 2007 11:29 pm

Obi-Wahn wrote:@Myth Jellies: I'll take some time to dig into your broken swordfish and try to understand what you are doing there.:)

In these cases, broken swordfish is identical to broken wing. I just found it easier manually to look for a swordfish group with four cells in one box, and it was easier to use the swordfish representation in a chain rather than inventing a new representation for a potential odd conjugate ring deadly pattern.

It is possible that there is a broken mutant fish that is degenerate with these broken swordfish that better maps the house subsets to the set of candidates that can be eliminated when you have a broken wing.

I also note that your grouped broken wing example (NoFish 12) can not be explained as a broken swordfish, though, again it might be some broken mutant.

Obi-Wahn wrote:
Myth Jellies wrote:Perhaps now that we have gotten used to avoiding deadly patterns using URs, we will be a little more comfortable avoiding the deadly pattern represented by the broken wing.

The deadly pattern in URs is of a different kind. If it was true, the puzzle would have multiple solutions. If the deadly pattern in the Broken Wing was true, the puzzle would be unsolvable. So the only assumption is, that the puzzle has a solution, it's not a uniqueness exploit.


I was not suggesting that Broken Wing is a uniqueness based technique. I was suggesting that some of the same techniques used to avoid deadly uniqueness based patterns could be used to avoid deadly odd conjugate ring patterns, and that their existence might make broken wing deductions more palatable.

By the way, did anyone else note that the filter on the 7's for NoFish 9 looks an awful lot like the outline of a fish (a grinning fish at that). Considering how hard that deduction turned to to be for me, I think that is just taunting.
Code: Select all
  7  7  7 | .  .  7 | 7  .  .
  .  7  . | 7  .  . | .  7  .
  7  .  . | 7  .  . | .  .  7
 ---------+---------+---------
  .  7  . | .  .  . | .  .  7
  .  .  . | .  .  . | .  .  .
  .  7  7 | .  .  . | 7  .  7
 ---------+---------+---------
  7  .  7 | .  .  7 | .  7  7
  7  7  . | 7  .  . | .  7  .
  7  .  . |-7  .  7 | 7  .  .

Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Fri Jan 19, 2007 11:56 pm

Myth Jellies wrote:
Code: Select all
 a2  .  . | .  .  2 | . -2  2
  . X2  . | .  .  2 | .  .  2
 X2  .  . | . X2  . | .  . a2
 ---------+---------+---------
  .  .  . | .  .  . | .  .  .
  . X2  . | . X2  . | .  .  .
  .  .  2 | 2  .  . | .  .  .
 ---------+---------+---------
  2  .  . | .  .  2 | . B2  .
  .  .  2 | 2  .  . | .  .  .
  .  .  . | . A2  2 | . b2b-2
I have noticed that these broken wings are examples of impossible swordfish groups. When this is true, you have a few options. You can assume one of the cells outside the group sharing a row with the group is true; you can do the same for columns; or you can assume one of the candidates outside the fish group breaking the odd loop of conjugates is true.

I don't understand what you mean by the first two options. Would you please illustrate and/or expand on these?

Myth Jellies wrote:Of course if we know one of a set of candidates must be true, we can group them and form a strong link.

Rather than strong link shouldn't that be strong inference?

TIA, Ron
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Sat Jan 20, 2007 12:36 am

[Withdrawn]
Last edited by daj95376 on Sat Jan 20, 2007 9:56 pm, edited 2 times in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Myth Jellies » Sat Jan 20, 2007 4:27 am

ronk wrote:
Myth Jellies wrote:I have noticed that these broken wings are examples of impossible swordfish groups. When this is true, you have a few options. You can assume one of the cells outside the group sharing a row with the group is true; you can do the same for columns; or you can assume one of the candidates outside the fish group breaking the odd loop of conjugates is true.

I don't understand what you mean by the first two options. Would you please illustrate and/or expand on these?


Sure, given that you know the candidates marked with an X form a broken swordfish group (one where you cannot have three true candidates), you know that at least one of the candidates marked with an R (sharing a row with the broken fish group) must be true. You also know that at least one of the candidates sharing a column with the broken fish group must be true. Broken Wing tells you that at least one of the candidates marked with a W must be true.
Code: Select all
 C2W .  . | .  .  2 | . -2  2
  . X2  . | .  . R2 | .  . R2
 X2  .  . | . X2  . | .  . R2W
 ---------+---------+---------
  .  .  . | .  .  . | .  .  .
  . X2  . | . X2  . | .  .  .
  .  .  2 | 2  .  . | .  .  .
 ---------+---------+---------
 C2  .  . | .  .  2 | .  2  .
  .  .  2 | 2  .  . | .  .  .
  .  .  . | . C2W 2 | .  2 -2



ronk wrote:
Myth Jellies wrote:Of course if we know one of a set of candidates must be true, we can group them and form a strong link.

Rather than strong link shouldn't that be strong inference?

TIA, Ron


That distinction was really only made to placate Jeff. I don't consider it really that bothersome if people interchange them?
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Sat Jan 20, 2007 6:36 am

Myth Jellies wrote:given that you know the candidates marked with an X form a broken swordfish group (one where you cannot have three true candidates), you know that at least one of the candidates marked with an R (sharing a row with the broken fish group) must be true. ........

Thanks for the description. The methods seemed rather than obsure at first, but make total sense after some thought.

Myth Jellies wrote:
ronk wrote:
Myth Jellies wrote:Of course if we know one of a set of candidates must be true, we can group them and form a strong link.

Rather than strong link shouldn't that be strong inference?

That distinction was really only made to placate Jeff. I don't consider it really that bothersome if people interchange them?

I actually prefer the three terms weak link for "if A is true, then B is false", strong link for "if A is false, then B is true", and conjugate link for a link where both "if ... then ..." statements apply. But most people use strong link to mean conjugate link.

IOW I think inference removes the ambiguity.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Sat Jan 20, 2007 10:17 am

I agree with your idea of three distinct links

Though it is basically equivalent to your defs, I like...

Weak Link - At most one element is true
Strong Link - At least one element is true
Conjugate Link - Exactly one element is true (probably assumes two elements).

This is more general as it allows you to link more than two elements. This makes it easier to follow and create net logic. When you think of a strong link this way, it is easy to see why, if you have more than two elements, you can move an element from one side of a strong link to the other as is convenient. This is how I made my AIC net deduction for NoFish 9.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby wapati » Sat Jan 20, 2007 7:17 pm

Cool topic.

I had just read it and then spotted a puzzle where it is a shortcut, but other patterns can prevail. Original:

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

....3..5..8.7....6..58.9....12.8.7..5..9.2..1..7.1.56....1.83..1....4.8..4..2....


Code: Select all
.---------------.---------------.---------------.
| 679  67   14  | 2    3    16  | 49   5    8   |
| 239  8    14  | 7    45   15  | 29   239  6   |
|*236  236  5   | 8   *46   9   | 124  1237 37  |
:---------------+---------------+---------------:
| 4    1    2   | 56   8    56  | 7    39   39  |
| 5    36   36  | 9    7    2   | 8    4    1   |
| 8    9    7   | 4    1    3   | 5    6    2   |
:---------------+---------------+---------------:
| 27   5   *69  | 1   *69   8   | 3    27   4   |
| 1    27   39  | 356  59   4   | 26   8    57  |
|*36   4    8   | 356  2    7   | 169  19   59  |
'---------------'---------------'---------------'


Here I would have used a kite , a sword and a finned sword.
wapati
2010 Supporter
 
Posts: 527
Joined: 13 September 2006
Location: Brampton, Ontario, Canada

Postby Obi-Wahn » Sat Jan 20, 2007 10:13 pm

In NoFish8 I have found two almost finned fish with the candidates preventing the fish patterns being weakly linked:
Code: Select all
Without r4c5:

  .  .  . | 2 *2  . | .  2  .
  .  .  . |*2  . *2 | .  . *2
  .  .  . | .  .  . | .  .  .
 ---------+---------+---------
  . *2  . | . @2  . | .  . *2
  2  .  . | 2  .  2 | 2  2  .
  2 -2  . | 2 #2  2 | .  .  .
 ---------+---------+---------
  .  .  . | 2  .  2 | 2  2  .
  2  2  . | 2 *2  . | 2  2  .
  . *2  . |*2  .  . | .  .  .

Finned Mutant Jellyfish r249c5/c29b28 with fin r6c5


Without r4c9:

  .  .  . | 2  2  . | .  2  .
  .  .  . |-2  . *2 | .  . *2
  .  .  . | .  .  . | .  .  .
 ---------+---------+---------
  . *2  . | . *2  . | .  . @2
  2  .  . |-2  . *2 | 2  2  .
  2 -2  . |-2 -2 *2 | .  .  .
 ---------+---------+---------
  .  .  . |-2  . *2 | 2  2  .
  2 -2  . |-2 -2  . | 2  2  .
  . *2  . |*2  .  . | .  .  .

Mutant Jellyfish r49c69/r2c2b58 (actually a combination of a Swordfish and a Cyclopsfish)

Since not both candidates preventing the two fish patterns can be true, the two fish patterns cannot both be false. So the exclusion r6c2<>2 common to both patterns is valid.

I'm trying to combine both patterns into one, but this involves some weird ideas about allowing the same sector to be added multiple times to the base set or the cover set ...
User avatar
Obi-Wahn
 
Posts: 63
Joined: 05 January 2007
Location: Darmstadt, Germany

Postby ronk » Sat Jan 20, 2007 10:40 pm

Obi-Wahn wrote:Since not both candidates preventing the two fish patterns can be true, the two fish patterns cannot both be false. So the exclusion r6c2<>2 common to both patterns is valid.

Very very nice. It makes the "intersecting" x-wing exclusions here and here seem simple.:)
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby daj95376 » Thu Mar 29, 2007 12:01 am

Well, after ronk mentioned my "intersecting" X-Wing comments, this thread suddenly went quiet. I have that effect on people.:D

Anyway, I've been reviewing the NoFish puzzles. Two cells prevent a finned X-Wing from performing the desired elimination in NoFish8. Maybe something more can be made of it than my results.

Code: Select all
# sd-Kraken X-Wing c15/r68 w/ [r1c5]|[r4c5]|[r5c1]
#
# [r1c5] => [r2c9] => [r4c2]           => ![r6c2]
# [r4c5] => [r2c9] => [r1c4] => [r9c2] => ![r6c2]
# [r5c2]                               => ![r6c2]
*-----------------------------------*
|  .  .  .  |  2 @2  .  |  .  2  .  |
|  .  .  .  |  2  .  2  |  .  .  2  |
|  .  .  2  |  .  .  .  |  .  .  .  |
|-----------+-----------+-----------|
|  .  2  .  |  . @2  .  |  .  .  2  |
| #2  .  .  |  2  .  2  |  2  2  .  |
| *2 -2  .  |  2 *2  2  |  .  .  .  |
|-----------+-----------+-----------|
|  .  .  .  |  2  .  2  |  2  2  .  |
| *2  2  .  |  2 *2  .  |  2  2  .  |
|  .  2  .  |  2  .  .  |  .  .  .  |
*-----------------------------------*
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby daj95376 » Thu Mar 29, 2007 4:30 am

Decomposing NoFish9 using fish:

Code: Select all
# Leviathan r1234678/c1234789 w/ [r1c6],[r7c6]
#
# [r7c6] => ![r9c4] (trivial)
#
# (a) [r1c6] => ![r23c4]     => ...
# (b) Sashimi X-Wing r24/c29 => ...
# (c) [r2c8],[r3c1]          => ...
# (d) Sashimi X-Wing r58/c29 => [r7c3] => [r8c4] => ![r9c4] (non-trivial)
*-----------------------------------*
| *7 *7 *7  |  .  . @7  | *7  .  .  |
|  . *7  .  | *7  .  .  |  . *7  .  |
| *7  .  .  | *7  .  .  |  .  . *7  |
|-----------+-----------+-----------|
|  . *7  .  |  .  .  .  |  .  . *7  |
|  .  .  .  |  . *7  .  |  .  .  .  |
|  . *7 *7  |  .  .  .  | *7  . *7  |
|-----------+-----------+-----------|
| *7  . *7  |  .  . #7  |  . *7 *7  |
| *7 *7  .  | *7  .  .  |  . *7  .  |
|  7  .  .  | -7  .  7  |  7  .  .  |
*-----------------------------------*

What I find interesting is: [r23c4]=7 -or- [r1c6]=7,[r2c8]=7,[r3c1]=7

OR ... puzzle can be viewed as complex DIC: [r23c4] | ([r1c6] => [r8c4]) => ![r9c4]
Last edited by daj95376 on Thu Mar 29, 2007 1:44 am, edited 1 time in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby Mike Barker » Thu Mar 29, 2007 5:11 am

I've just implemented Obi-Wahn's "endo fin" approach and was checking things out. It turns out the NoFish7 actually is a fish with 1's. It just happens to be an Endofin Mutant Whale! Here she blows:
Code: Select all
NoFish7
Endofin Mutant Whale: r368c26b5/r4c37b128,endofin=r6c4: r3c1457|r6c344|r8c3457|r24c2|r1279c6|r4c45 => r9c4<>1
+--------------+----------------------+-----------------+
| 123   8  57  |     6      4    125* |   9   12   237  |
|   6  12* 57  |   358      9   1258* | 157    4  2378  |
| 123*  9   4  |  1358* 12358*     7  |  15*   6   238  |
+--------------+----------------------+-----------------+
|   7  15*  9  |   158*   158*     6  |   2    3     4  |
|   8  25   3  |     9     25      4  |   6    7     1  |
|   4   6  12* |   12*@     7      3  |   8    9     5  |
+--------------+----------------------+-----------------+
|  12   7   8  |     4      6    125* |   3  125     9  |
|   5   4  12* |  1237*    13*     9  |  17*   8     6  |
|   9   3   6  | 578-1   1258   1258* |   4  125    27  |
+--------------+----------------------+-----------------+


[Edit: Updated per Ron's correction]
Last edited by Mike Barker on Thu Mar 29, 2007 9:25 pm, edited 1 time in total.
Mike Barker
 
Posts: 458
Joined: 22 January 2006

Postby daj95376 » Thu Mar 29, 2007 5:29 am

[Edit: Question withdrawn. I realized that a Skyscraper explained everything. Just too dense to see it. Thanks wapati, your comment put me on the right track.]
Last edited by daj95376 on Thu Mar 29, 2007 1:24 pm, edited 6 times in total.
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby wapati » Thu Mar 29, 2007 6:04 am

It is 3 overlapping sashimis. Good to remember that you should mark eliminations and keep looking and then do tham all at once.
wapati
2010 Supporter
 
Posts: 527
Joined: 13 September 2006
Location: Brampton, Ontario, Canada

PreviousNext

Return to Advanced solving techniques