The New Sudoku Players' Forum

by **Mike Barker** » Wed Oct 25, 2006 5:43 am

Like I said constraint subsets are pretty weird. Here are three examples:

Code: Select all: 3x3 Constraint Set (r67,c3): r6c145|r7c26|r458c3 => r5c6<>1 +----------------+------------------+---------------------+ | 19 159 37 | 1368 1578 4 | 2 356789 1358 | | 8 125 37 | 1236 1257 9 | 1346 3567 1345 | | 129 6 4 | 1238 1578 178 | 1389 35789 1358 | +----------------+------------------+---------------------+ | 3 4 128* | 7 1268 5 | 168 268 9 | | 5 7 128* | 9 4 6-1 | 1368 2368 138 | | 129* 289 6 | 128* 128* 3 | 5 4 7 | +----------------+------------------+---------------------+ | 4 18* 9 | 5 368 168* | 7 38 2 | | 6 3 128* | 18 1789 278 | 489 589 458 | | 7 28 5 | 4 39 28 | 39 1 6 | +----------------+------------------+---------------------+ 3x3 Constraint Set (r34,b9): r3c478|r4c479|r789c7|r7c8 => r56c8<>5,r6c7<>5 +------------------+-------------------+-------------------+ | 168 3 128 | 4 57 256 | 9 17 567 | | 5 16 12 | 36 79 269 | 1467 8 34 | | 9 7 4 | 356* 8 1 | 356* 235* 23 | +------------------+-------------------+-------------------+ | 168 2 9 | 1568* 3 7 | 1568* 4 56* | | 3 1456 1568 | 9 145 4568 | 2 17-5 567 | | 7 1456 1568 | 2 145 4568 | 1368-5 13-5 9 | +------------------+-------------------+-------------------+ | 124 159 3 | 15 6 459 | 457* 257* 8 | | 46 8 56 | 7 2 3 | 45* 9 1 | | 124 159 7 | 158 1459 4589 | 345* 6 234 | +------------------+-------------------+-------------------+ 4x4 Constraint Set (r1,c57,b4): r1c69|r3569c5|r459c7|r56c2|r6c3 => r56c9<>7 +------------------+----------------+--------------------+ | 9 26 48 | 24 3 67* | 5 1 278* | | 7 16 5 | 24 8 16 | 49 34 2349 | | 138 123 348 | 5 179* 179 | 6 478 2478 | +------------------+----------------+--------------------+ | 138 4 2 | 137 6 5 | 789* 378 139 | | 5 1379* 139 | 8 147* 2 | 47* 6 13-7 | | 6 137* 1378* | 9 147* 137 | 2 34578 13458-7 | +------------------+----------------+--------------------+ | 4 379 379 | 36 2 38 | 1 578 567 | | 2 8 17 | 167 5 4 | 3 9 67 | | 13 5 6 | 137 179* 389 | 478* 2 47 | +------------------+----------------+--------------------+

by **ronk** » Wed Oct 25, 2006 11:18 am

Mike Barker wrote:Like I said constraint subsets are pretty weird.

Mike, great finds. It's helpful to consider unfinned exemplars first. For your first puzzle:

Code: Select all: . . / | . . . | . . . . . / | . . . | . . . . . / | . . . | . . . ----------+----------+--------- * * X | * * * | . . . * * X | * * * | . . . X X / | X X X | / / / ----------+----------+--------- X X / | / / / | / / / * * X | . . . | . . . * * X | . . . | . . . Fig 1A: rrc\bbb constraint sets

The candidates in set A (r6, r7 and c3) are covered by set B (b4, b5 and b6). Any other candidates in set B may be excluded. (If any of the excluded candidates were true, no candidate would remain for row 7.) Add the fin at r7c6 and exclusions at r45c6 still occur (denoted by "**" below).

Code: Select all: . . / | . . . | . . . . . / | . . . | . . . . . / | . . . | . . . ----------+----------+--------- * * X | * * ** | . . . * * X | * * ** | . . . X X / | X X X | / / / ----------+----------+--------- X X / | / / # | / / / * * X | . . . | . . . * * X | . . . | . . . Fig 1B: rrc\bbb almost constraint sets Key: X = candidate, which may be missing / = no candidate # = extra candidate (fin cell) * = potential exclusion whether fin exists or not ** = potential exclusion if fin exists

For the second puzzle:

Code: Select all: . . . | * . . | * * . . . . | * . . | * * . / / / | X / / | X X / ----------+----------+--------- / / / | X / / | X X / . . . | * . . | * * . . . . | * . . | * * . ----------+----------+--------- . . . | * . . | X X / . . . | * . . | X X / . . . | * . . | X X / Fig 2A: rrb\ccc constraint sets

The candidates in set A (r3, r4 and b9) are covered by set B (c4, c7 and c7). Any other candidates in set B may be excluded. (If any of the excluded candidates were true, no candidate would remain for box 9.) Add the fin at r4c9 and exclusions at r56c78 still occur.

You should recognize this as the inverse of a "finned franken swordfish."

Code: Select all: . . . | * . . | * * . . . . | * . . | * * . / / / | X / / | X X / ----------+----------+--------- / / / | X / / | X X # . . . | * . . | ** ** . . . . | * . . | ** ** . ----------+----------+--------- . . . | * . . | X X / . . . | * . . | X X / . . . | * . . | X X / Fig 2B: rrb\ccc almost constraint sets

For the third puzzle:

Code: Select all: / / / | X / X | / / # . . . | * X * | / . . . . . | * X * | / . . ----------+----------+--------- / / / | . / . | # . . X X X | * X * | X * ** X X X | * X * | X * ** ----------+----------+--------- . . . | . / . | / . . . . . | . / . | / . . * * * | * X * | X * * Fig 3: rccb\rrrb two-finned almost constraint sets

If both fins r1c9 and r4c7 are false, the candidates in set A (r1, c5, c7 and b4) are covered by set B (r5, r6, r9 and b2). Any other candidates in set B could be excluded. (If any of the excluded candidates were true, no candidate would remain for row 1.) Add either fin and exclusions at r56c9 still occur.

I don't think constraint sets are weird at all. Difficult to find? Yes, but not weird.

[edit: In third puzzle, Mike provided correct b4 (was b8).]

by **Mike Barker** » Wed Oct 25, 2006 12:51 pm

My mistake the basis set for the 3rd example should read r1,c57,b4. I'll change the original post.

by **daj95376** » Wed Oct 25, 2006 6:15 pm

Mike Barker, Please forgive me in advance if the following is off-topic or misses your point. I seem to have that problem.

Code: Select all: I've given up on naming fish after: N=2 - X-Wing N=3 - Swordfish N=4 - Jellyfish N=5 - Squirmbag, Starfish N=6 - Whale N=7 - Leviathan (???) N=8 - Kraken

Your first constraint subsets example can be derived with four additional eliminations on <1>.

Code: Select all: *-----------------------------------------------------------------------------* | 19 159 37 | 1368 -1578 4 | 2 356789 1358 | | 8 125 37 | 1236 -1257 9 | 1346 3567 1345 | |-129 6 4 | 1238 -1578 178 | 1389 35789 1358 | |-------------------------+-------------------------+-------------------------| | 3 4 128 | 7 1268 5 | 168 268 9 | | 5 7 128 | 9 4 -16 | 1368 2368 138 | |#129 289 6 |*128 *128 3 | 5 4 7 | |-------------------------+-------------------------+-------------------------| | 4 18 9 | 5 368 168 | 7 38 2 | | 6 3 #128 |*18 *1789 278 | 489 589 458 | | 7 28 5 | 4 39 28 | 39 1 6 | *-----------------------------------------------------------------------------*

Code: Select all: X-Wing [r68c45] => [r3c6]=1 => all eliminations performed fin [r6c1]=1 => fin [r8c3]=1 => [r7c6]=1 => [r4c5]=1 => all eliminations performed fin [r8c3]=1 => fin [r6c1]=1 & [r7c6]=1 => [r4c5]=1 => all eliminations performed

I'll leave it up to someone else to decide if this pattern has a name. I'd call it an exo-finned X-Wing, but what do I know.

by **Mike Barker** » Thu Oct 26, 2006 12:51 pm

As usual there are several ways to make the eliminations. The example above demonstrates a constraint set approach. In your approach either the fins are true or the fish is true. In the first case, r4c5 is "1" and r123c5<>1 and r6c1<>1. If the fish is true then the same holds. This seems to be a Kraken Fish except that it appears to rely on dynamic forcing chains and not nice links. Is this the case?

The elimination r5c6<>1 can also be based on an a Kraken row (I used to call a Kraken House, but this wasn't really correct and less descriptive) which is a technique which can be derived from the Sudoku Unification Model. r7c6 is linked to r6c1 via 2 grouped strong links: r6c1-1-r13c1=1=r12c2-1-r7c2=1=r7c6. Then because row 6 must contain a "1", "1" can be eliminated from any cell which sees r6c45 and r7c6 such as r5c6. Looked at the other way if r5c6=1 then r6 doesn't contain a "1". r123c5 and r3c1 fall with singles. I would probably prefer this, but it doesn't demonstrate a constraint set approach.

by **Myth Jellies** » Thu Oct 26, 2006 3:38 pm

Code: Select all: *-----------------------------------------------------------------------------* | 19 159 37 | 1368 -1578 4 | 2 356789 1358 | | 8 125 37 | 1236 -1257 9 | 1346 3567 1345 | |-129 6 4 | 1238 -1578 (A)178 | 1389 35789 1358 | |-------------------------+-------------------------+-------------------------| | 3 4 A128 | 7 (a)1268 5 | 168 268 9 | | 5 7 A128 | 9 4 -16 | 1368 2368 138 | |a129 289 6 |A128 A128 3 | 5 4 7 | |-------------------------+-------------------------+-------------------------| | 4 A18 9 | 5 368 a168 | 7 38 2 | | 6 3 a128 |A18 A1789 278 | 489 589 458 | | 7 28 5 | 4 39 28 | 39 1 6 | *-----------------------------------------------------------------------------*

A two step simple grouped coloring works as well. The parenthetical colors apply after the 1 in r5c6 is removed. Also not a constraint set approach, though one could use the A-colored box-box interactions in r45 and also in c45 to aid in the deduction.

One could even multi-color the c45 box-box interaction thus...

Code: Select all: *-----------------------------------------------------------------------------* | 19 159 37 |B1368 B1578 4 | 2 356789 1358 | | 8 125 37 |B1236 B1257 9 | 1346 3567 1345 | |-129 6 4 |B1238 B1578 b178 | 1389 35789 1358 | |-------------------------+-------------------------+-------------------------| | 3 4 A128 | 7 1268 5 | 168 268 9 | | 5 7 A128 | 9 4 -16 | 1368 2368 138 | |a129 289 6 |A128 A128 3 | 5 4 7 | |-------------------------+-------------------------+-------------------------| | 4 A18 9 | 5 368 a168 | 7 38 2 | | 6 3 a128 |A18 A1789 278 | 489 589 458 | | 7 28 5 | 4 39 28 | 39 1 6 | *-----------------------------------------------------------------------------*

Colors A and B inhibit each other due to the box-box interaction, therefore either color a or color b or both must be true. Again, lost in life support-Kraken fish section.

by **daj95376** » Thu Oct 26, 2006 5:47 pm

Mike Barker wrote:As usual there are several ways to make the eliminations. The example above demonstrates a constraint set approach. In your approach either the fins are true or the fish is true. In the first case, r4c5 is "1" and r123c5<>1 and r6c1<>1. If the fish is true then the same holds. This seems to be a Kraken Fish except that it appears to rely on dynamic forcing chains and not nice links. Is this the case?

Your analysis and techniques are beyond my skills ... as is your question. However, I don't think forcing chains are involved. My chaining of resultant Singles may not be acceptable. What prompted my reply was your earlier message.

Mike Barker wrote:Here's another 2c worth. I have nothing against using boxes in the basis set if one is talking about constraint subsets. I'm looking forward to finding new eliminations with this approach. My objection is calling these fish.

It set me to wondering if a fish variant existed in any of your constraint subset examples. It was luck/misfortune that I managed to find an X-Wing with fin cells that produced the same eliminations as the Templates output from my solver.

If the X-Wing is true, then this leave a Hidden Single in [r3c6] and I apply its eliminations as well.

The key to the fin cells is: [r6c1]=1 <=> [r45c3]<>1 <=> [r8c3]=1. If either fin cell is true, then the other is true. This means that the X-Wing is completely destroyed if either fin cell is true. What follows are two successive Hidden Singles, [r7c6]=1 and [r4c5]=1.

Thanks Myth Jellies for providing the different Coloring approaches. I'll study them! The only other solution that I could derive was Double Implication (Forcing) Chains using [r7c26]=1.

by **tarek** » Thu Oct 26, 2006 9:32 pm

Mike Barker wrote:My objection is calling these fish. The problem is that suddenly a Franken fish may look nothing like what someone would expect. Consider Ocean's fish - weird.

Mike Barker later wrote:Like I said constraint subsets are pretty weird. Here are three examples:

Havard wrote:I would have to agree with Mike on this one, using more than just columns or rows as basis-sectors should have some other name to indicate just that.

A radical change to a fish ...... that sounds like a "Mutant fish" to me

.

So what does a non mutant fish look like (1 step down) ????

Franken fish: (A rows + B Boxes) * (C columns + D Boxes) or vv. No fins (A+B=C+D=N , A+C>0, B+D>0)
Finned Franken fish: A rows + B Boxes) * (C columns + D Boxes) or vv. with fins (A+B=C+D=N , A+C>0, B+D>0)

This would insure that we can't have mixed (row/column) base sets or mixed (row/column) cover sets ....... making it more like a freindly fish

& then we have the mutant & the finned mutant fish (or some other names)

tarek

by **Mike Barker** » Fri Oct 27, 2006 1:04 pm

I love mutant fish! So we have a class of techniques which are constraint sets or almost constraint sets with subclasses:
1) basic, finned and sashimi fish: n rows or columns covered by n columns or rows plus a possible fin
2) finless and finned Frankenfish: n rows or columns covered by n columns and boxes or n rows and boxes plus possible fin(s?)
3) finless and finned mutant fish: n rows, columns, and/or boxes covered by n rows, columns, and/or boxes plus possible extra cells (not sure what a fin looks like in this case)
4) Kraken fish: any fish on life support (requires extra strong link(s), grouped strong link(s), bivalue cell, and/or ALS to perform the elimination(s))
5) Almost fish (?): a fish which is part of a nice loop

Yes, we could get away with only constraint sets or almost constraint sets, but these divisions make a logical progression from the basic to the complex, that is, from an intermediate player to an expert level player.

by **Ocean** » Fri Oct 27, 2006 2:17 pm

ronk wrote:Nice example of a 4x4 constraint set problem which could be called a "generalized jellyfish", I suppose. All the candidates of set 'A' in b1c478 are covered by set 'B' in r2359. Candidates in set B, but not in set A, may thus be excluded.

Thanks Ron ... didn't see this perspective until you spelled it out.

I tried to translate three other examples, from an old Hidden Pattern thread.

The two first examples have constraint sets of type (bbbb\rrcc) and (bbc\rrc), respectively. Observe the extra elimination when rows and columns in set B intersect - is this a general rule?

Is it also possible to explain the third example (shown in two variations) using the "constraint set" concept?

Code: Select all: Hidden Pattern: I. *-----------------* |/ / .|. / /|. . .| |/ / .|. / /|. . .| |. . *|* . .|* * *| |-----+-----+-----| !. . *|* . .|* * *| |/ / .|. / /|. . .| |/ / .|. / /|. . .| |-----+-----+-----| |. . *|* . .|. . .| |. . *|* . .|. . .| |. . *|* . .|. . .| *-----------------* II. *-----------------* |/ / .|. / .|. . .| |/ / .|. / .|. . .| |. . *|* . *|* * *| |-----+-----+-----| !. . *|* . *|* * *| |/ / .|. / .|. . .| |/ / .|. / .|. . .| |-----+-----+-----| |. . *|. / .|. . .| |. . *|. / .|. . .| |. . *|. / .|. . .| *-----------------* III. *-----------------* *-----------------* |/ / .|. / /|. . .| |. . .|. . .|/ . /| |/ / .|. / /|. . .| |. . .|. . .|/ . /| |. . .|. . .|. . .| |* . .|. . .|. . .| |-----+-----+-----| |-----+-----+-----| !. . .|* . .|. . .| |. . .|. . .|. . .| |/ / .|. . .|. . .| |. . .|. . .|. . .| |/ / .|. . .|. . .| |. . .|. . .|. . .| |-----+-----+-----| |-----+-----+-----| |. . .|. . .|. . .| |. / /|. . .|/ . /| |. . .|. . .|. . .| |. . .|. . .|. . .| |. . .|. . .|. . .| |. / /|. . .|/ . /| *-----------------* *-----------------* Key: . = candidate present or missing / = no candidate * = potential exclusion

Note also the inverse sets:

Code: Select all: I Inverse. *-----------------* |* * .|. * *|. . .| |* * .|. * *|. . .| |. . /|/ . .|/ / /| |-----+-----+-----| |. . /|/ . .|/ / /| |* * .|. * *|. . .| |* * .|. * *|. . .| |-----+-----+-----| |. . /|/ . .|. . .| |. . /|/ . .|. . .| |. . /|/ . .|. . .| *-----------------* II Inverse. *-----------------* |* * .|. * .|. . .| |* * .|. * .|. . .| |. . /|/ . /|/ / /| |-----+-----+-----| !. . /|/ . /|/ / /| |* * .|. * .|. . .| |* * .|. * .|. . .| |-----+-----+-----| |. . /|. * .|. . .| |. . /|. * .|. . .| |. . /|. * .|. . .| *-----------------*

by **tarek** » Fri Oct 27, 2006 2:48 pm

Ocean wrote:Is it also possible to explain the third example (shown in two variations) using the "constraint set" concept?

I couldn't find fewer than 4 cover sets for the eliminations for HIDDEN I.....
base sectors r1256 with cover sectors c34 & b36 making it a franken Jellyfish

Mike Barker wrote:I love mutant fish!
.
.
.
2) finless and finned Frankenfish: n rows or columns covered by n columns and boxes or n rows and boxes plus possible fin(s?)
.
.
.
Yes, we could get away with only constraint sets or almost constraint sets, but these divisions make a logical progression from the basic to the complex, that is, from an intermediate player to an expert level player.

I do agree that we need to make fish that do not exhibit many fish structure in a category of their own (mutant fish) which sounds more hydrophilic than constraint subsets.......

but I think there is a slight difference of opinions of that threshold between FRANKEN & MUTANT fish....... from what I see, these 2 opinions are:

Code: Select all: Opinion 1: Franken fish must have NO boxes in the BASE sectors Opinion 2: you CAN have boxes in the base sectors provided that there is NO row/column MIXING in either the base or cover sectors......

In Havard's Big fish wxample.....The smaller fish would be a finned mutant x-wing according to opinion 1 while it is a finned franken x-wing acording to opinion2

I tend to go with opinion 2 .......Mike seems to go with opinion 1

tarek

by **ronk** » Fri Oct 27, 2006 2:51 pm

Mike Barker wrote:2) finless and finned Frankenfish: n rows or columns covered by n columns and boxes or n rows and boxes plus possible fin(s?)
3) finless and finned mutant fish: n rows, columns, and/or boxes covered by n rows, columns, and/or boxes plus possible extra cells (not sure what a fin looks like in this case)

If you consider what Angus Johnson's Simple Sudoku calls Locked Candidates 1 and 2, you'll note they are inverse techniques. Empty cells in one are exclusions cells in the other. Exclusion cells in one are empty cells in the other. The point being the two types of locked candidate techniques are a logical set, belonged together, and were named similarly.

Code: Select all: . . . | / X / | . . . . . . | * X * | . . . . . . | / X / | . . . . . . | * X * | . . . . . . | / X / | . . . . . . | * X * | . . . -------+-------+------- -------+-------+------- . . . | . * . | . . . . . . | . / . | . . . . . . | . * . | . . . . . . | . / . | . . . . . . | . * . | . . . . . . | . / . | . . . -------+-------+------- -------+-------+------- . . . | . * . | . . . . . . | . / . | . . . . . . | . * . | . . . . . . | . / . | . . . . . . | . * . | . . . . . . | . / . | . . . Locked candidates 1 Locked candidates 2 Inverse of locked candidates 2 Inverse of locked candidates 1 Box-line interaction Line-box interaction

The same should happen for the franken fish and its inverse -- the inverse franken fish.

Code: Select all: . . . | / . . | X X * . . . | * . . | X X / . . . | / . . | X X * . . . | * . . | X X / . . . | / . . | X X * . . . | * . . | X X / -------+-------+------- -------+-------+------- . . . | / . . | / / . . . . | * . . | * * . * * * | X * * | X X * / / / | X / / | X X / . . . | / . . | / / . . . . | * . . | * * . -------+-------+------- -------+-------+------- . . . | / . . | / / . . . . | * . . | * * . . . . | / . . | / / . . . . | * . . | * * . * * * | X * * | X X * / / / | X / / | X X / Unfinned franken swordfish Inverse unfinned franken swordfish

Or maybe "franken fish 1" and "franken fish 2". At the risk of being repetitious, I strongly believe a technique and its inverse belong together.

[edit: Swapped "Box-line interaction" and "Line-box interaction."]

by **ronk** » Fri Oct 27, 2006 3:33 pm

Ocean wrote:Observe the extra elimination when rows and columns in set B intersect - is this a general rule?

Yes. If a placement were to occur in the intersection of two units of set B (the cover), the result would be invalid. There would be N units remaining in set A (the base) and N-1 units remaining in set B.

Ocean wrote:Note also the inverse sets:

Your inverse sets are correct IMO.

P.S. Not showing the Xs is an interesting approach, but I'm having difficulty adjusting because one's attention isn't drawn to the cells that must be covered.

by **ronk** » Fri Oct 27, 2006 5:21 pm

Ocean wrote:Is it also possible to explain the third example (shown in two variations) using the "constraint set" concept?
...
Code: Select all
III. *-----------------* |/ / .|. / /|. . .| |/ / .|. / /|. . .| |. . .|. . .|. . .| |-----+-----+-----| !. . .|* . .|. . .| |/ / .|. . .|. . .| |/ / .|. . .|. . .| |-----+-----+-----| |. . .|. . .|. . .| |. . .|. . .|. . .| |. . .|. . .|. . .| *-----------------* Key: . = candidate present or missing / = no candidate * = potential exclusion

Since the strong inferences of three empty rectangles are sufficient, using constraint sets seems like a stretch ... but it does work.

Note this is identical to your first example except that we know nothing about r45c45. The possible existence of candidates in those locations must be considered "extras" ... as in the fin cells of an N-fish. So we have ...

Code: Select all: *------------------------------* | / / X | X / / | . . . | | / / X | X / / | . . . | | X X *X | *X X X | * * * | |---------+----------+---------| | X X *X |**X X X | * * * | | / / X | X # # | . . . | | / / X | X # # | . . . | |---------+----------+---------| | . . * | * . . | . . . | | . . * | * . . | . . . | | . . * | * . . | . . . | *------------------------------* finned bbbb\rrcc

If all the fin cells are false, all the exclusions of example 1 apply (shown * and **). If any fin cell is true, the only ** exclusion sees all the fin cells.

by **Mike Barker** » Fri Oct 27, 2006 6:34 pm

Two to one - you guys win. I can live with Frankenfish including row/box or column/box basis sets.

The New Sudoku Players' Forum

Looking for a rule: finned x wing