Fish Groups & Constraint Groups in AICs

Advanced methods and approaches for solving Sudoku puzzles

Fish Groups & Constraint Groups in AICs

Postby Myth Jellies » Thu Dec 21, 2006 10:24 am

Expanding the basic AIC building blocks - NxN Fish Groups

You can extend the concept of bilocated candidates into two dimensions by considering an NxN fish group.

Definitions for an NxN Fish Group

An NxN fish group consists of any intersection of N column houses with N row houses. A fish group pertains to only one particular digit. The particular digit does not need to be present as a candidate in any of the cells that form the NxN fish group.

An NxN fish group is considered true for a particular digit only if it contains exactly N true candidates for that digit. A fish group being true doesn't necessarily tell you where in the fish group that digit's candidates are true, but it does tell you that any like candidates that are outside of the fish group that share a row or column with the fish group must be false. Likewise, if the fish group is false, then at least one of the outside candidates that shares a row, and at least one of the outside candidates that shares a column with the fish group must be true.

NxN Fish Group - Identifying Weak Links

Any group of like candidates, not part of the fish group, that all share either a row or a column with the fish group is weakly linked to the fish group. You cannot have both the fish group and a candidate from the outside group be true.

NxN Fish Group - Identifying & Using Strong Links

If a group of like candidates encompasses either all of the outside candidates sharing rows with the fish group, or all of the outside candidates sharing columns with the fish group; then that group is strongly linked to the fish group. Either the outside group or the fish group (or possibly both if they share candidates) must be true. If there is no intersection between the two groups, they are conjugate, and they can even be colored. If there are no candidates for the outside group in one dimension (rows or columns), then the fish group must be true and outside candidates sharing the other dimension may be removed.

Note that when a fish group is false, it may still contain a significant number of true candidates. Because of this, it is practically impossible to come up with cases where two large fish patterns are directly strongly linked.

AIC Notation for Fish Groups

To denote a fish group using AIC notation, use a slash in between the rows/columns in the location field. Changing the order of rows and columns so that the correct set of houses faces the candidates interacting with them is allowed. While this is not so important in the case of fish groups, it will help make things clearer in the case of the more generic Constraint Groups.

Examples of Fish Groups in AICs

Finned fish and finned sashimi fish are simple AICs of the form...

{Fish Group} = {Fin Group}

...which eliminates candidates weakly linked to both the fish and the fin. For example...

(1)c248/r159 = (1)r1c13 => is a finned swordfish with r23c2 <> 1

Kraken Fish are identical to longer AIC chains or nets with a fish group.

Here is the original finned fish example
Code: Select all
+----------+-----------+-----------+
| .  .  .  |  .  .  .  |  .  1  .  |
| . *1  .  | *1  .  .  |  .  .  .  |
| .  1  1  |  1  1  1  |  .  .  .  |
+----------+-----------+-----------+
| . *1  .  | *1 #1 #1  |  .  .  .  |
| .  1  1  | -1  1  1  |  .  .  .  |
| .  .  .  | -.  .  .  |  .  .  1  |
+----------+-----------+-----------+
| .  .  .  |  1  1  1  |  .  .  .  |
| .  .  .  |  .  .  .  |  1  .  .  |
| 1  .  .  |  .  .  .  |  .  .  .  |
+----------+-----------+-----------+
(1)c24/r24 = (1)r4c56 => r56c4 <> 1 (finned x-wing)

Code: Select all
 +-----------+-----------+-----------+
 |*7   .   . | .   .   . | .  *7  *7 |
 | .   .   . | .   7   . | .   .   . |
 | 7   .   7 | .   .   . | 7   .   . |
 +-----------+-----------+-----------+
 | .   .   . | .   .  A7 | 7  -7   . |
 |*7   .   . | .   .   . |#7  *.  *7 |
 | .   .   7 |a7   .   . | 7   7   . |
 +-----------+-----------+-----------+
 | .   .   . | 7   .  a7 | 7   7   7 |
 | .   7   . | .   .   . | .   .   . |
 |*.   .   . |#7   .   . | .  *7  *7 |
 +-----------+-----------+-----------+
               = (7)r5c7
              /
(7)c189/r159 =
              \
               = (7)r9c4 - (7)r6c4 = (7)r4c6
At least one of the three endpoints is true implying r4c89 <> 7


Code: Select all
 +-----------+-----------+------------+
 | .   .   1B| 1b  .   . | .   .   .  |
 | 1c  .   1 | 1   .   1A| 1   1   1  |
 | 1c  .   1 | 1   .   1A| 1   1   1  |
 +-----------+-----------+------------+
 | .   1X  . | .   1X  . | 1x" 1x" 1x"|
 | .   .   1d| .   .   . | 1D  1D  1D |
 | 1C  .   1 | 1   .   . | 1   1   1  |
 +-----------+-----------+------------+
 | .   .   1 | 1   .   . | 1   1   1  |
 | .   1X  . | .   1X  . | .   .   .  |
 | .   1x' . | 1   1x' 1a| 1   1   1  |
 +-----------+-----------+------------+

(1)r48/c25 = (1)r9c25 - (1)r9c6 = (1)r23c6 - (1)r1c4 = (1)r1c3 - (1)r23c1 = (1)r6c1 - (1)r5c3 = (1)r5c789 - (1)r4c789 = (1)r48/c25 => the X-Wing is true, therefore r9c25 & r4c789 <> 1

Here is a wild one...let '/' indicate cells containing neither candidates for 1 nor 2. Let X, Y, and Z be any number of non-12 digits. Dot cells here can contain any candidates.
Code: Select all
 +-----------+-----------+------------+
 | 12X /   / | 12Y /   / | /   12Z /  |
 | .   .   . | .   .   . | .   .   .  |
 | .   .   . | .   .   . | .   .   .  |
 +-----------+-----------+------------+
 | .   .   . | .   .   . | .   .   .  |
 | 12  /   / | 12  /   / | /   /   /  |
 | .   .   . | .   .   . | .   .   .  |
 +-----------+-----------+------------+
 | 123 .   . | 123 .   . | .   .   .  |
 | .   .   . | .   .   . | .   .   .  |
 | .   .   . | .   .   . | .   .   .  |
 +-----------+-----------+------------+

(3&2=1)r7c14 - (1)c14/r15 = (1-2)r1c8 = (2)r15/c14 - (2=1&3)r7c14... AIC loop => r7c2356789 <> 3 and r1c8 <> Z

Expanding the Basic AIC Building Blocks - NxN Constraint Groups

Other NxN constraint groups are possible besides fish (N rows vs N columns). As long as the set of houses on either side do not have any internal intersections, the constraint group is just the cells forming the intersection of the two sets of houses, and all of the other rules apply just as they do for fish groups.

The particular problem of internal intersections

If a set of constraint houses has internal intersections, then you cannot form strong links against that set unless those internal intersections are removed from the constraint group (do this by removing them from the other set of houses!)

For example, consider r28c28/b1379

Code: Select all
 +-----------+-----------+------------+
 | .   X   . | .   .   . | .   X   .  |
 | X  (X)  X | .   .   . | X  (X)  X  |
 | .   X   . | .   .   . | .   X   .  |
 +-----------+-----------+------------+
 | .   .   . | .   .   . | .   .   .  |
 | .   .   . | .   .   . | .   .   .  |
 | .   .   . | .   .   . | .   .   .  |
 +-----------+-----------+------------+
 | .   X   . | .   .   . | .   X   .  |
 | X  (X)  X | .   .   . | X  (X)  X  |
 | .   X   . | .   .   . | .   X   .  |
 +-----------+-----------+------------+

The X's denote the constraint group. Let / indicate cells which cannot contain the digit, and let '*' indicate cells where the digit could be removed. The (X)s indicate cells that are part of the internal intersection for r28 & c28. The cells should be removed from the b1379 set and thus removed from the constraint group. If 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   /  |
 +-----------+-----------+------------+

...then we have our always false cells (/) strongly linked to the b1379 set of houses in our constraint group, and since that set has no internal intersections we can safely eliminate all the candidates that weakly link with the r28c28 part of the constraint group (marked with an *).

Our modified constraint group works even better though...
Code: Select all
 +-----------+-----------+------------+
 | /   X   / | .   .   . | /   X   /  |
 | X   *   X | *   *   * | X   *   X  |
 | /   X   / | .   .   . | /   X   /  |
 +-----------+-----------+------------+
 | .   *   . | .   .   . | .   *   .  |
 | .   *   . | .   .   . | .   *   .  |
 | .   *   . | .   .   . | .   *   .  |
 +-----------+-----------+------------+
 | /   X   / | .   .   . | /   X   /  |
 | X   *   X | *   *   * | X   *   X  |
 | /   X   / | .   .   . | /   X   /  |
 +-----------+-----------+------------+

Here you see that r28c28 are no longer considered part of b1379/ or the constraint group, but they are still considered part of the r28 & c28 set, therefore they are automatically removed along with the rest of that set when the slash cells are empty.

The complementary situation does not work out at all without the internal intersection mod. Taking this example we would have...
Code: Select all
 +-----------+-----------+------------+
 | *   X   * | .   .   . | *   X   *  |
 | X   X   X | /   /   / | X   X   X  |
 | *   X   * | .   .   . | *   X   *  |
 +-----------+-----------+------------+
 | .   /   . | .   .   . | .   /   .  |
 | .   /   . | .   .   . | .   /   .  |
 | .   /   . | .   .   . | .   /   .  |
 +-----------+-----------+------------+
 | *   X   * | .   .   . | *   X   *  |
 | X   X   X | /   /   / | X   X   X  |
 | *   X   * | .   .   . | *   X   *  |
 +-----------+-----------+------------+

The slash cells here do not form a strong link with the constraint group. You can see that if you put a true candidate in one of the internal intersection cells (r28c28) then you could not fill in the grid without placing a true candidate in one of the starred cells. That means that the Constraint Group will have less than 4 true candidate, thus both the group of slash cells and the constraint group will be false.

If you remove the internal intersection cells from the b1379 constraint set and the constraint group, then you have...
Code: Select all
 +-----------+-----------+------------+
 | *   X   * | .   .   . | *   X   *  |
 | X   /   X | /   /   / | X   /   X  |
 | *   X   * | .   .   . | *   X   *  |
 +-----------+-----------+------------+
 | .   /   . | .   .   . | .   /   .  |
 | .   /   . | .   .   . | .   /   .  |
 | .   /   . | .   .   . | .   /   .  |
 +-----------+-----------+------------+
 | *   X   * | .   .   . | *   X   *  |
 | X   /   X | /   /   / | X   /   X  |
 | *   X   * | .   .   . | *   X   *  |
 +-----------+-----------+------------+

And now the strong link between the constraint group and the /-cells holds up and we can safely make all the deletions from the starred cells when the slash cells are empty.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Thu Jan 11, 2007 7:01 am

Myth Jellies wrote:If you remove the internal intersection cells from the b1379 constraint set and the constraint group, then you have...
Code: Select all
 +-----------+-----------+------------+
 | *   X   * | .   .   . | *   X   *  |
 | X   /   X | /   /   / | X   /   X  |
 | *   X   * | .   .   . | *   X   *  |
 +-----------+-----------+------------+
 | .   /   . | .   .   . | .   /   .  |
 | .   /   . | .   .   . | .   /   .  |
 | .   /   . | .   .   . | .   /   .  |
 +-----------+-----------+------------+
 | *   X   * | .   .   . | *   X   *  |
 | X   /   X | /   /   / | X   /   X  |
 | *   X   * | .   .   . | *   X   *  |
 +-----------+-----------+------------+

And now the strong link between the constraint group and the /-cells holds up and we can safely make all the deletions from the starred cells when the slash cells are empty.

How would you write an AIC for the following?
Code: Select all
 +-----------+-----------+------------+
 | *   X   * | .   .   . | .   X   .  |
 | X   #   X | /   /   / | X   /   X  |
 | *   X   * | .   .   . | .   X   .  |
 +-----------+-----------+------------+
 | .   /   . | .   .   . | .   /   .  |
 | .   /   . | .   .   . | .   /   .  |
 | .   /   . | .   .   . | .   /   .  |
 +-----------+-----------+------------+
 | .   X   . | .   .   . | .   X   .  |
 | X   /   X | /   /   / | X   /   X  |
 | .   X   . | .   .   . | .   X   .  |
 +-----------+-----------+------------+
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Thu Jan 11, 2007 5:49 pm

ronk wrote:How would you write an AIC for the following?
Code: Select all
 +-----------+-----------+------------+
 | *   X   * | .   .   . | .   X   .  |
 | X   #   X | /   /   / | X   /   X  |
 | *   X   * | .   .   . | .   X   .  |
 +-----------+-----------+------------+
 | .   /   . | .   .   . | .   /   .  |
 | .   /   . | .   .   . | .   /   .  |
 | .   /   . | .   .   . | .   /   .  |
 +-----------+-----------+------------+
 | .   X   . | .   .   . | .   X   .  |
 | X   /   X | /   /   / | X   /   X  |
 | .   X   . | .   .   . | .   X   .  |
 +-----------+-----------+------------+

(X)b1379/r28c28 = (X)r2c2 => r13c13 <> X.

Because the b1379 set is matched up with a set containing internal intersections, the intersection cells, r28c28, are not considered part of the b1379 set or the constraint group in this case. r2c2 is still part of the set r28c28 though, which is why I ordered my constraint group the way I did.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Thu Jan 11, 2007 6:41 pm

Myth Jellies wrote:the b1379 set ... the r28c28 set ...

To be clear, when you say "b1379 set" -- ignoring the internal intersections -- are the empty cells ('/') inside or outside the units b1379?

(X)b1379/r28c28 = (X)r2c2 => r13c13 <> X.

Because the b1379 set is matched up with a set containing internal intersections, the intersection cells, r28c28, are not considered part of the b1379 set or the constraint group in this case. r2c2 is still part of the set r28c28 though, which is why I ordered my constraint group the way I did.

The constraint group? Aren't there two constraint groups?

Also, if by "ordered my constraint group" means ...

b1379/r28c28 = (X)r2c2 => r13c13 <> X

versus

(X)r2c2 = b1379/r28c28 => r13c13 <> X

... I see no difference. If anything -- for reading left-to-right -- I have a slight preference for the latter, because "if the fin is false, then the fish is true" is easier to understand than "if the fish is false, then the fin is true."
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Fri Jan 12, 2007 2:01 am

My nomenclature might not match everyone elses, which could be a problem. I use constraint group as a special case of grouped candidates.

The constraint group is formed from the intersection of two constraint sets. The constraint group is represented by the two constraint sets separated by a slash (r28c28/b1379).

In this case:
One constraint set is r2, r8, c2, & c8; and the other is b1, b3, b7, & b9 minus the cells r28c28 (internal intersection cells in the other set). The constraint group is the intersection of the two sets, which is all of the cells marked with an 'X'. The cells marked with '/' are the empty cells that are part of the r28c28 set, but are outside of the r28c28/b1379 constraint group.

Ordering question: I would write this as either

(X)b1379/r28c28 = (X)r2c2 => r13c13 <> X,

or

(X)r2c2 = (X)r28c28/b1379 => r13c13 <> X.

Either one is fine, but note that I kept the r28c28 set facing the '=' to help signify that fin (X)r2c2 belonged to that set. Might be better if I did it the other way actually. Probably doesn't matter either way.

Of course I prefer "either the fin or the fish/constraint group must be true.":)
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Fri Jan 12, 2007 5:15 pm

By the way, am I consistent with the following definitions?

Fish Group - intersection of a constraint set of rows with a constraint set of columns

Frankenfish Group - intersection of two constraint sets, neither one of which has any internal intersections, and at least one box is included in at least one of the constraint sets.

Mutant Fish Group - intersection of two constraint sets, at least one of which has an internal intersection.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Fri Jan 12, 2007 5:57 pm

Myth Jellies wrote:By the way, am I consistent with the following definitions?

Fish Group - intersection of a constraint set of rows with a constraint set of columns

Frankenfish Group - intersection of two constraint sets, neither one of which has any internal intersections, and at least one box is included in at least one of the constraint sets.

Mutant Fish Group - intersection of two constraint sets, at least one of which has an internal intersection.

Yes, except that box\line and line\box "internal intersections" may also occur in franken fish. A line\line internal intersection makes it a mutant fish.

BTW I use the backslash ('\') because that's a generally accepted mathematical symbol for the substraction of sets -- r2\b2 means the cells of b2 are subtracted from the cells of r2 leaving r2c456 as the remainder.

For the earlier example and ignoring internal intersections -- the remainder of r28c28\b1379 specifies the empty cells -- which define the fish. The remainder of b1379\r28c28 defines the exclusions.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Jean-Christophe » Sat May 12, 2007 8:28 am

Myth Jellies wrote:Expanding the Basic AIC Building Blocks - NxN Constraint Groups
...
The particular problem of internal intersections


Thanks for your clear explanation.

Indeed I was confused about strong and weak links because most sources indicate that a strong link is also a weak link. But this does not have to be the case. Your examples shows grouped strong links which are not valid grouped weak links.

If the cell at the intersection may hold the candidate, this does not form a grouped weak link. But still forms a grouped strong link.

Here is an example for which we cannot eliminate any candidate because there is no weak link in box 8.
Code: Select all
+-------+-------+-------+
| . . . | . / . | . . . |
| . ? . | . X . | . . . |
| . . . | . / . | . . . |
+-------+-------+-------+
| . . . | . / . | . . . |
| . . . | . / . | . . . |
| . . . | . / . | . . . |
+-------+-------+-------+
| . . . | . X . | . . . |
| / X / | X X X | / / / |
| . . . | . X . | . . . |
+-------+-------+-------+

(X)r2c5 = (X)r789c5 -no valid weak link in b8- (X)r8c456 = (X)r8c2 => cannot deduce anything here

In order to have a valid weak link in b8, the internal intersection cannot hold the candidate (this example could be called grouped 2 string kite)
Code: Select all
+-------+-------+-------+
| . . . | . / . | . . . |
| . * . | . X . | . . . |
| . . . | . / . | . . . |
+-------+-------+-------+
| . . . | . / . | . . . |
| . . . | . / . | . . . |
| . . . | . / . | . . . |
+-------+-------+-------+
| . . . | . X . | . . . |
| / X / | X / X | / / / |
| . . . | . X . | . . . |
+-------+-------+-------+

(X)r2c5 = (X)r79c5 - (X)r8c46 = (X)r8c2 => r2c2 <> X

However if the internal intersection may hold the candidate, this still forms a strong link as in this example (the Empty Rectangle pattern)
Code: Select all
+-------+-------+-------+
| . . . | . . . | . . . |
| / X / | / X / | / / / |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | / X / | . . . |
| . * . | X X X | . . . |
| . . . | / X / | . . . |
+-------+-------+-------+

(X)r2c2 = (X)r2c5 - (X)r789c5 = (X)r8c456 => r8c2 <> X

And if the AIC forms a continuous loop, all strong links forming the continuous loop must "become" weak: the two cases cannot be both true. And all weak links must "become" strong: one of the case must be true. As in this grouped swordfish example
Code: Select all
+-------+-------+-------+
| * / * | . * . | . . . |
| / / X | / X / | / / / |
| * X * | . * . | . . . |
+-------+-------+-------+
| . / . | . * . | . . . |
| . / . | . * . | . . . |
| . / . | . * . | . . . |
+-------+-------+-------+
| . / . | / X / | . . . |
| * X * | X * X | * * * |
| . / . | / X / | . . . |
+-------+-------+-------+

- (X)r2c3 = (X)r2c5 - (X)r789c5 = (X)r8c456 - (X)r8c2 = (X)r3c2 - => the swordfish is true & r8c5 <> X

This could also be applied to any AIC forming a continuous loop, incl XY-loops and probably CoALS continuous loops.

Please correct me if I'm wrong.

Edit I knew it has been discussed already. Have a look at the AIC thread
Jean-Christophe
 
Posts: 149
Joined: 22 January 2006

Postby Myth Jellies » Sun May 13, 2007 9:36 am

You are quite correct. Nice examples, too.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005


Return to Advanced solving techniques

cron