Sudoku Programmers :: View topic - Generalized X-Wing - Does this also work for Swordfish?

FAQ

Memberlist

Usergroups

Profile

Generalized X-Wing - Does this also work for Swordfish?
Goto page Previous 1, 2, 3 Next

Sudoku Programmers Forum Index -> Solving sudoku

View previous topic :: View next topic

Author

Message

rkral

Joined: 21 Oct 2005

Posts: 233

Items

Posted: Thu Nov 03, 2005 8:23 pm Post subject:

Bob Hanson wrote:

What has been shown in rkral's message is NOT a swordfish. It is instead a circular chain

An x-wing is also a circular chain. Does that make it NOT an x-wing?

I was merely suggesting that any set of constraints that limits the placement of three instances of a digit to exactly three columns(rows) is a swordfish pattern. The classical swordfish is constrained to three columns(rows) by three rows(columns). Why can't the constraints be two rows and one box with a conjugate pair?

To simplify, my prior example had three strong pairs (conjugates) all for the same digit. Here is a more general example, with only one strong pair in box 5.

Code:

* 1 1 | * 1 * | 1 1 1
* 1 1 | * 1 * | 1 1 1
1 . . | 1 . 1 | . . .
---------+-----------+---------
* 1 1 | . . 1 | 1 1 1
* 1 1 | 1 . . | 1 1 1
* 1 1 | . . . | 1 1 1
---------+-----------+---------
1 . . | 1 . 1 | . . .
* 1 1 | * 1 * | 1 1 1
* 1 1 | * 1 * | 1 1 1

The dots indicate cells where digit 1 is not a candidate. The 1s indicate cells where digit 1 might be a candidate. The *s indicate cells where 1s can be excluded as candidates.

Bob Hanson wrote:

My point is simply that if you identify the smaller 2x2 pattern, you can be just as successful.

What is a smaller pattern within the above?

Last edited by rkral on Thu Nov 03, 2005 9:58 pm; edited 1 time in total

angusj
Site Admin

Joined: 18 Jun 2005

Posts: 406

Items

Posted: Thu Nov 03, 2005 9:11 pm Post subject:

rkral wrote:

I was merely suggesting that any set of constraints that limits the placement of three instances of a digit to exactly three columns(rows) is a swordfish pattern. The classical swordfish is constrained to three columns(rows) by three rows(columns). Why can't the constraints be two rows and one box with a conjugate pair?

It all boils down to a generally agreed definition - which evidently you see as still open to debate.

Anyhow, somewhat tongue in cheek, and following your argument -
why do we restrain the definition of a dog to a four legged animal that barks? Why not call any four legged animal a dog?

Bob Hanson

Joined: 05 Oct 2005

Posts: 187

Location: St. Olaf College

Items

Posted: Sat Nov 05, 2005 4:23 am Post subject:

One last thought on

Quote:

1) Firstly, are there any situations where looking for X-Wings by boxes is useful? That is situations where other methods would not find the same eliminations.

I now believe that such searches are unnecessary, provided fully logical solution is carried out. My experience with Sudoku Assistant is that it only needs this sort of analysis in order to appear to be especially "human-like." They are, after all, very easy to see, and they prove very common in even most of the harder puzzles. And they can quickly give the clues necessary in "moderately" difficult Sudoku puzzles.

The bottom line is this;

If your methods stop with simple "X/Y-cycle" sort of analysis, then this block business will solve significantly more puzzles. If your methods include or are instead full "hypothesis and proof" either forward or reverse, then you don't need to look for these.

But they are some of the easiest things for humans to use.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

rkral

Joined: 21 Oct 2005

Posts: 233

Items

Posted: Mon Nov 07, 2005 3:12 am Post subject: Re: Generalized X-Wing - Does this also work for Swordfish?

kranser wrote:

Firstly, are there any situations where looking for X-Wings by boxes is useful? That is situations where other methods would not find the same eliminations.

Locked Candidates 2 ( http://www.angusj.com/sudoku/hints.php ) makes looking for x-wing patterns by boxes unnecessary.

Borrowing Bob Hanson's figure from an earlier message ...

Code:

block 1 block 2 block 3
row 1 [ ---- x -----] [ ---- x -----] [ ---- x -----]
row 2 [ ---- x -----] [ ---- x -----] [ ---- x -----]
row 3 [ --- no x ---] [ --- no x ---] [ ---- x -----]

X-wing by boxes finds that blocks 1 and 2 each contain candidates x in both rows 1 and 2 but not row 3. Since each box and each row must contain exactly one x, either b1r1 and b2r2 ... or b1r2 and b2r1 ... contain the true candidates. This allows the safe elimination of candidates x from rows 1 and 2 of block 3.

The well-known Locked Candidates 2 finds candidates x of row 3 only in block 3, and eliminates the same candidates x from rows 1 and 2 of block 3.

Since the latter technique is easier to understand and simpler to program, there is no reason to use x-wing by boxes IMHO.

mathrec

Joined: 15 Jul 2005

Posts: 10

Location: Carlsbad, CA

Items

Posted: Mon Nov 07, 2005 6:11 am Post subject:

I've been looking at short chains that can be used to eliminate one or more possibilities from the board, and I found a general case that is very close to the X-wing. It is different from the "Generalized X-wing" that has been discussed here.

Here's the classic X-wing:

Code:

. * .|. . .|. * .
. * .|. . .|. * .
. * .|. . .|. * .
-----+-----+-----
- A -|- - -|- a -
. * .|. . .|. * .
. * .|. . .|. * .
-----+-----+-----
. * .|. . .|. * .
- B -|- - -|- b -
. * .|. . .|. * .

The configuration that I was looking at is a close cousin:

Code:

. . .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .
-----+-----+-----
- - A|- - -|- a -
. * .|. . .|. . .
. * .|. . .|. . .
-----+-----+-----
. . *|. . .|. . .
- B -|- - -|- b -
. . *|. . .|. . .

Aa and Bb are strong conjugates. Since a and b are weak conjugates, the locations marked * can be reduced to eliminate the candidate value.

Does this pattern have a name? I think of it as an open X-wing, because it has the same pattern of two rows containing only two possible locations for the candidate value.

This generalizes to include cases like this:

Code:

. . .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . .
-----+-----+-----
- - A|- - -|- a -
. . .|. . .|. . .
. . .|. . .|. . .
-----+-----+-----
. . *|. . .|B - -
. . .|. . .|- b -
. . .|. . .|- - -

The essential configuration is a pentagon with conjugate relationships along the sides. If two non-adjacent sides of the pentagon are strong conjugates, then the fifth vertex can be reduced. The classic X-wing and the open X-wing are special cases.

Here's an actual puzzle that can use this method to reduce the 9 at location (1,3). The pentagon is formed (1,3)-(1,4)=(2,5)-(6,5)=(6,3)-(1,3), where the = represents the strong conjugate. (2,5)=(6,5) is also a strong conjugate, but I left that out because it's not essential to the pattern.

Code:

1 57 679 | 59 2 3 | 69 8 4
69 3 2 | 8 49 47 | 1679 5 167
59 4 8 | 1 6 57 | 79 3 2
---------------|---------------|---------------
369 1 4 | 59 7 8 | 2 69 356
3569 8 679 | 2 1 56 | 4 679 3567
2 57 679 | 3 49 46 | 8 1 567
---------------|---------------|---------------
4 6 1 | 7 5 9 | 3 2 8
8 9 5 | 4 3 2 | 167 67 167
7 2 3 | 6 8 1 | 5 4 9

Does this reduction have a name?

angusj
Site Admin

Joined: 18 Jun 2005

Posts: 406

Items

Posted: Mon Nov 07, 2005 7:54 am Post subject:

mathrec wrote:

Does this pattern have a name?

I've called it a Type 2 Multi-color:
http://www.setbb.com/phpbb/viewtopic.php?p=2575&mforum=sudoku#2575

Nick70 has called the simplest subset of this 'multi-color' pattern a turbot fish ( http://sudoku.com/forums/viewtopic.php?t=833 ) - of which yours is a good example.

mathrec

Joined: 15 Jul 2005

Posts: 10

Location: Carlsbad, CA

Items

Posted: Mon Nov 07, 2005 5:21 pm Post subject: Turbo Fish

It is indeed a turbo fish. Thanks, Steve

Bob Hanson

Joined: 05 Oct 2005

Posts: 187

Location: St. Olaf College

Items

Posted: Mon Nov 07, 2005 10:30 pm Post subject:

Code:

As you point out, your pentagon involves

Code:

(r1c3) 9-(w)-9 (r1c4)
| \
| \
| 9* (r2c5)
(w) |
| |
| (x)
| |
| |
(r6c3) 9--------9 (r6c5)
*

which forms an incompatible weak corner on a 4-long strong chain.
The key is in setting the *'d 9 FALSE and checking the implications.
The point about (x) not needing to be strong is well taken, because
the transmission of consequences from the bottom right 9 (set TRUE)
to the one above it is without regard to strength. (Only a F-->T
implication requires a strong edge.

There must be a huge number of such possibilities. Do they all really
have names? This is what Glenn Fowler refers to as an "X-cycle."

Here's another X-cycle that is in your configuration:

Code:

(r1c2)
5-------------5* (r1c4)
|7 9\
| \
| \
| \
| 57 (r3c6)
| |
| |
| (w)
| |
| 4|
5*-----(w)---------56 (r6c6)
7 (r6c2)

r6c6 can't be 5.

The "3D Medusa" idea would allow you to transfer the strongness from these
same-number chains to any other number. Perhaps this is what is called
"advanced coloring"? For example, we also have, starting with the 49 in r2c5:

Code:

(r2c5)
(r2c1) 4---4* (r2c6)
69-----(w)---------9* 7
| |
(w) |
| |
*5---------------------5|
9 (r3c1) 7* (r3c6)

Here again we have a strong chain, this time consisting of 7 edges and 8 nodes:

(r2c5)9*-4-4*-7-7*-5-5*-9(r3c1)

The chain has an even number of nodes, so the two ends are of opposite parity.
They disallow any 9 that is a corner between them. r2c1 must be 6.
This is something like what Glenn calls a "Y-cycle", I think. In the
Sudoku Assistant, this r2c1#9 gets thrown out when the strong chains are made.
The attempt to make the second connection to the same strong chain triggers the
elimination.

See

http://www.stolaf.edu/people/hansonr/sudoku?100023084032800050048160032014078200080210400200300810461759328895432000723681549

If you step through this one, it will show you all three of these.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr

rkral

Joined: 21 Oct 2005

Posts: 233

Items

Posted: Sun Nov 20, 2005 4:34 am Post subject:

angusj wrote:

If you think the the "classical" swordfish consists of conjugate pairs in three rows (or columns) then I'll have to disagree with you.

Since I wrote "consider the following special case of the swordfish", it should be apparent that's not what I think.

Quote:

I can certainly see why you may consider the pattern you've described above a swordfish, but I would argue it's not. Instead I'd leave it in the conjugate 'colors' group of techniques.

Then permit me broaden the pattern a bit to ...

Code:

. * . | * . * | . . .
. * . | * . * | . . .
. a . | a . a | . . .
---------+----------+---------
. * . | . . B | . . .
. * . | b . . | . . .
. * . | . . . | . . .
---------+----------+---------
. c . | c . c | . . .
. * . | * . * | . . .
. * . | * . * | . . .

where a represents the only candidate x locations in row 3, B and b represent conjugate candidate x locations in box 5, and c represents the only candidate x locations in row 7. While it is clear candidate x can be eliminated from columns 2, 4, and 6 (designated by the asterisks), I don't see how conjugate color techniques might cause eliminations,

I plan to study Doug Bowman's fishy cycles, which Doug claims is a generalization of the swordfish and jellyfish patterns. Maybe the above pattern is covered there.

Aside: I recall your post originally asking (paraphrased) "why don't we call any 4-legged animal a dog?" How did you manage to edit that post without "edit information" being displayed today?

Lummox JR

Joined: 07 Sep 2005

Posts: 202

Items

Posted: Sun Nov 20, 2005 7:47 am Post subject:

rkral wrote:

angusj wrote:

If you think the the "classical" swordfish consists of conjugate pairs in three rows (or columns) then I'll have to disagree with you.

Since I wrote "consider the following special case of the swordfish", it should be apparent that's not what I think.

Many do seem to think that, though, so it's always important to be clear on that point.

Quote:

I can certainly see why you may consider the pattern you've described above a swordfish, but I would argue it's not. Instead I'd leave it in the conjugate 'colors' group of techniques.

Then permit me broaden the pattern a bit to ...

Code:

Well, I don't think "extending" the swordfish pattern would be a useful way to look at it, though maybe giving this new technique a name of its own would prove useful. You're quite right that coloring wouldn't pick this up, although extended coloring would. Extended coloring works like supercoloring by adding "filler" colors that have no conjugates, and considering whole groups as potential conjugates of each other. It's a technique I've never used, but the explanation goes something like this:

1) Label row 3 as awx instead of aaa, and row 7 as cyz. Build a list of exclusions, i.e. a!c, x!z, a!w, etc. Also note the sets from which we can draw conjugates: {awx}, {cyz}, {bB}.
2) Using the conjugate rules for propagating exclusions, knowing that w!b and B!z, we know that w!z. Similarly, x!y.
3) Now look at implications. (I don't know how to use this technique with exclusions alone; sorry.) We know that w!y,z so w!{yz} (w excludes a set in which either y or z may be true), and since {yz} is a conjugate of c, w->c. We can't prove c->w, however. What we can prove is that x->c as well. Now since w->c and x->c, {wx}->c. And since {wx} is a conjugate of a, and a!c, c->{wx}. Since c->{wx} and {wx}->c, they are equivalent. And since they are equivalent, a and c must be conjugates. You can therefore eliminate all other choices in column 2. Based on different reasoning you should be able to work out the eliminations in columns 4 and 6.

Another nice method for the above might be the use of inequalities and equations:

a+w+x=1
c+y+z=1
b+B=1

w+b+y<=1 -> w+y<=B
x+B+z<=1 -> x+z<=b

w+x+y+z<=b+B=1

a+w+x>=w+x+y+z
a>=y+z
a+c>=1 -> a+c=1

a+c+w+x+y+z=2
w+x+y+z=1

w+x+y+z+b+B=2
(w+b+y)+(x+B+z)=2
Since w+b+y<=1 and x+B+z<=1:
w+b+y=1
x+B+z=1

Once you have any sum >=1 that shares the same house, you can eliminate the rest of that house. a+c=1 means you can kill the other possibilities in column 2. As you see columns 4 and 6 are only a tad more complicated.

Quote:

I plan to study Doug Bowman's fishy cycles, which Doug claims is a generalization of the swordfish and jellyfish patterns. Maybe the above pattern is covered there.

At the time Doug said that, I believe he was thinking only of those special-case swordfish that do not have 3 candidates in any given column/row, but only have 2 each. Fishy cycles do not generalize the X-fish pattern, so the technique is probably a misnomer at this point. Fishy cycles are based on conjugate chains, X-fish on positional subsets which need not involve conjugates at all. In fact fishy cycles is merely one possible set of patterns under the umbrella of complete simple coloring.

Nick70

Joined: 08 Jun 2005

Posts: 160

Items

Posted: Sun Nov 20, 2005 10:32 am Post subject:

I don't know if it's useful to this discussion, but I posted about skewed swordfishes three months ago in the player's forum I was talking only about the special case with conjugate pairs on every line, however.

angusj
Site Admin

Joined: 18 Jun 2005

Posts: 406

Items

Posted: Sun Nov 20, 2005 11:54 am Post subject:

rkral wrote:

Aside: I recall your post originally asking (paraphrased) "why don't we call any 4-legged animal a dog?" How did you manage to edit that post without "edit information" being displayed today?

The "last edited" message only appears if you edit your post after someone else has responded in the same thread. Is that what you're asking?? (Anyhow, I didn't edit it today if that's what you think.)

Also, having reread my replies to your previous questions "rkral", I now see that what I intended as lighthearted comments could easily be interpreted as me being argumentative which certainly wasn't my intention. Sorry.

rkral

Joined: 21 Oct 2005

Posts: 233

Items

Posted: Sun Nov 20, 2005 7:19 pm Post subject:

Nick70 wrote:

I don't know if it's useful to this discussion, but I posted about skewed swordfishes three months ago in the player's forum

I was talking only about the special case with conjugate pairs on every line, however.

Puzzle #664 of the top870 [edit1: link added] provides an excellent example of a generalized "skewed swordfish", as it has not one conjugate pair.

Code:

...27...9
8........
...4.8..1
32...69..
.....9.3.
7..1....2
.........
.948....6
.789...2.

Using various techniques, we can reach the position:

Code:

...27...9
8..39....
9..468..1
32...69..
....29.3.
7.91.3..2
2..6.7.9.
.94832..6
6789.4.23

With candidates:

Code:

145 13456 1356 | 2 7 15 | 34568 4568 9
8 1456 27 | 3 9 15 | 24567 4567 457
9 35 27 | 4 6 8 | 2357 57 1
---------------------+----------------------+----------------------
3 2 15 | 57 48 6 | 9 14578 4578
145 14568 156 | 57 2 9 | 145678 3 4578
7 4568 9 | 1 48 3 | 4568 4568 2
---------------------+----------------------+----------------------
2 135 135 | 6 15 7 | 48 9 48
15 9 4 | 8 3 2 | 157 157 6
6 7 8 | 9 15 4 | 15 2 3

Displaying only candidate 5:

Code:

5 5 5 | . . 5 | 5 5 .
. 5 . | . . 5 | 5 5 5
. 5 . | . . . | 5 5 .
----------+----------+----------
. . 5 | 5 . . | . 5 5
5 5 5 | 5 . . | 5 . 5
. 5 . | . . . | 5 5 .
----------+----------+----------
. 5 5 | . 5 . | . . .
5 . . | . . . | 5 5 .
. . . | . 5 . | 5 . .

We note that row 3, row 6, and box 9 candidates are constrained to columns 2, 7, and 8. Using Lummox JR's set notation, we assign sets {auv}, {bwx}, and {cyz}, to the constraining rows and box ... and indicate candidate 5 eliminations (*).

Code:

5 * 5 | . . 5 | * * .
. * . | . . 5 | * * 5
. a . | . . . | u v .
----------+----------+----------
. . 5 | 5 . . | . * 5
5 * 5 | 5 . . | * . 5
. b . | . . . | w x .
----------+----------+----------
. * 5 | . 5 . | . . .
5 . . | . . . | c y .
. . . | . 5 . | z . .

Without proof, I hypothesize that candidates may be eliminated in the columns containing the pattern ... UNLESS the candidates are either in the rows or are on the floor containing the box that defined the pattern. IOW the candidate 5 at r7c2 cannot be safely eliminated.

[edit2: Lummox JR later proved that ALL candidate 5s in columns 2, 7, and 8 may be eliminated ... EXCEPT those candidates which defined the pattern.]

Now I'll go off to a quiet corner and see if I can develop a rigorous proof, ala Lummox JR. I won't mind if someone beats me to it. Smile

Last edited by rkral on Mon Nov 21, 2005 12:07 pm; edited 2 times in total

Lummox JR

Joined: 07 Sep 2005

Posts: 202

Items

Posted: Sun Nov 20, 2005 8:20 pm Post subject:

I think I see the pattern now, and I do believe your hypothesis works. a+u+v=1 b+w+x=1 c+y+z=1 a+b<=1 u+w+c+z<=1 v+x+y<=1 (1-b)+u+v>=1 u+v>=b (b-v)+w+c+z<=1 b+w+c+z<=1+v (1-x)+c+z<=1+v c+z<=x+v (1-y)<=x+v x+v+y>=1 Since we know >1 is not possible here, v+x+y=1. u+w+c+z<=1 u+w<=y u+w+v+x<=1 u+v+(1-b)<=1 u+v<=b (1-a)<=b a+b>=1 -> a+b=1 u+v=(1-a) u+v=b u+v+w+x=1 u+v=y u+v+c+z=1 This provides proof of eliminations in columns 2, 6, and 7.

rkral

Joined: 21 Oct 2005

Posts: 233

Items

Posted: Mon Nov 21, 2005 11:54 am Post subject:

Lummox JR wrote:

This provides proof of eliminations in columns 2, [ed: 7, and 8].

Very nicely done. I'll edit my earlier post to show the additional elimination(s).

Quote:

u+v=(1-a)
u+v=b
u+v+w+x=1
u+v=y
u+v+c+z=1

That block of equations contains a typo and should read:
u+v=(1-a)
u+v=b
u+v+w+x=1
u+w=y
u+w+c+z=1

So for columns 2, 7, and 8 respectively, you proved:
a+b=1
u+w+c+z=1
v+x+y=1

And the "equal" instead of the starting "less than or equal" means candidate 5 can exist no where else in that column. Very nice!

Display posts from previous:

	Sudoku Programmers Forum Index -> Solving sudoku	All times are GMT Goto page Previous 1, 2, 3 Next
Page 2 of 3

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