Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Fish Groups & Constraint Groups in AICs

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Myth Jellies

Joined: 20 Sep 2005
Posts: 14
:

Items
PostPosted: Mon Jan 08, 2007 7:00 am    Post subject: Fish Groups & Constraint Groups in AICs Reply with quote

Thought I would cross-post this here, because it contains another take on fish and constraint groups which might be of interest to coders.

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.

If a fish group has no weak links in one of its dimensions (rows or columns) then the fish group must 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:
+----------+-----------+-----------+
| .  .  .  |  .  .  .  |  .  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:
 +-----------+-----------+-----------+
 |*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:
 +-----------+-----------+------------+
 | .   .   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:
 +-----------+-----------+------------+
 | 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


Here's one from real life. MM's Extreme 15
Code:
 *-----------*
 |2..|48.|..5|
 |...|...|7..|
 |..7|2.9|4..|
 |---+---+---|
 |.3.|.9.|.6.|
 |4..|8.5|..3|
 |.2.|.3.|.5.|
 |---+---+---|
 |..5|9.3|1..|
 |..4|...|...|
 |3..|.78|..9|
 *-----------*

reduces to
Code:
 *--------------------------------------------------------------------*
 | 2     *19     3      |*4      8      7      | 6     *19     5      |
 | 1689   4      1689   | 3      5      16     | 7      1289   128    |
 | 168    5      7      | 2      16     9      | 4      3      18     |
 |----------------------+----------------------+----------------------|
 | 5      3      18     | 17     9      124    | 28     6      147    |
 | 4     *1679  #169    |*8     #126    5      | 29    *17     3      |
 | 16789  2      1689   | 167    3      146    | 89     5      147    |
 |----------------------+----------------------+----------------------|
 | 67     678    5      | 9      4      3      | 1      278    2678   |
 | 1679   16789  4      | 5      126    126    | 3      78     678    |
 | 3     *16     2      |*16     7      8      | 5     *4      9      |
 *--------------------------------------------------------------------*

Thus we have the AIC
(7)r4c4 = (7)r4c9 - (7=1)r5c8 - (1)r5c35 = (1)r159/c248 => r4c4 <> 1

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:
 +-----------+-----------+------------+
 | .   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:
 +-----------+-----------+------------+
 | /   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:
 +-----------+-----------+------------+
 | /   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:
 +-----------+-----------+------------+
 | *   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:
 +-----------+-----------+------------+
 | *   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
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Tue Jan 09, 2007 10:16 pm    Post subject: Reply with quote

Thanks for your contribution, Myth Jellies. It is such a shame that posts like these receive so little response. To be honest, I had to read your post 3 or 4 times before it sank in.

Incorporating "almost fish" or ARCS (almost row-column subsets) in chains is something that I had in mind when I wrote my ARCS post in the Players forum.

It takes some time to understand the concept of "fish group" vs. "outside group". Most of the time, the outside group is(are) the fin(s), which many consider part of the fish and not something that lies outside the fish.

A simple way to incorporate Almost Fish into chains is this:

Consider N rows with candidates limited to N+1 columns. You can now create a group for each of these columns, containing the candidates that belong to this pattern.
Code:
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 /  /  A | /  B  / | C  /  /
 --------+---------+--------
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 --------+---------+--------
 /  /  A | /  B  / | C  /  /
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .

Each group has strong inference with any of the other groups, because any group which is eliminated enforces the fish in the remaining groups.

Any 2 groups can be used as 2 successive (grouped) nodes in an AIC with strong inference between them.

It is possible to expand this pattern to N rows and N+2 columns, but then it has limitations on the candidates to which strong links can be formed. One of the nodes must include 2 columns. Take the following pattern:
Code:
 .  .  . | .  .  . | #  .  .
 .  .  . | .  .  . | #  .  .
 /  /  A | /  B  / | C  C  /
 --------+---------+--------
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 --------+---------+--------
 /  /  A | /  B  / | C  /  /
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .

The extra candidate in column 7 can be added to the C group, but only r1c7 or r2c7 can be used as the next node. Also, there is no longer strong inference between the A and B groups. It is still possible to expand a second group, but then the applications are severely limited. the B group cannot be used as a node any more and there are only 2 cells which can be linked to each end.
Code:
 .  .  . | .  .  . | #  .  .
 .  .  . | .  .  . | #  .  .
 /  /  A | /  B  / | C  C  /
 --------+---------+--------
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 .  .  . | .  .  . | .  .  .
 --------+---------+--------
 /  A  A | /  B  / | C  /  /
 .  .  # | .  .  . | .  .  .
 .  .  # | .  .  . | .  .  .

Maybe this POV will help people to understand how this technique can be used (and coded).

Ruud
Back to top
View user's profile Send private message Visit poster's website
Jean-Christophe

Joined: 19 Mar 2006
Posts: 126
:
Location: Belgium

Items
PostPosted: Sat May 12, 2007 8:41 am    Post subject: Reply with quote

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:

+-------+-------+-------+
| . . . | . / . | . . . |
| . ? . | . 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:

+-------+-------+-------+
| . . . | . / . | . . . |
| . * . | . 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:

+-------+-------+-------+
| . . . | . . . | . . . |
| / 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:

+-------+-------+-------+
| * / * | . * . | . . . |
| / / 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
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.
Back to top
View user's profile Send private message Visit poster's website
kyriako

Joined: 12 Jun 2008
Posts: 16
:
Location: Germany

Items
PostPosted: Sun Jul 26, 2009 9:34 am    Post subject: Kraken Fish in Nice Loops Reply with quote

Hello,

I have been programming a solver with Nice Loops which work with grouped strong links and
ALSes.
Code and exe:http://home.arcor.de/guentermeinel/download.html

Now I would like to add the "Kraken X-Wing" as a linking element.
As Myth Jellies pointed out, one can treat it as a strong link in the form of:
{Fish Group} = {Fin Group}
In the following example, this would mean that I can connect the Kraken via weak links
from/to the "<"-cells and from/to the ">"-cells:
Code:

+---------+---------+---------+
| .  /  . | .  /  . | .  .  . |
| <  X  < | <  X  < | <  <  < |
| .  /  . | .  /  . | .  .  . |
+---------+---------+---------+
| .  /  . | .  /  . | .  .  . |
| <  X  < | <  X  < | <  <  < |
| .  /  . | .  /  . | .  .  . |
+---------+---------+---------+
| >  #  > | .  /  . | .  .  . |
| >  #  > | .  /  . | .  .  . |
| >  #  > | .  /  . | .  .  . |
+---------+---------+---------+

If the fin is located in the same box as part of the X-Wing, can I use the cell
"?" which "sees" both the two branches of X-Wing and the fin?
Code:

+---------+---------+---------+
| .  /  . | .  /  . | .  .  . |
| <  X  < | <  X  < | <  <  < |
| .  /  . | .  /  . | .  .  . |
+---------+---------+---------+
| ?  X  ? | <  X  < | <  <  < |
| >  #  > | .  /  . | .  .  . |
| >  #  > | .  /  . | .  .  . |
+---------+---------+---------+
| .  /  . | .  /  . | .  .  . |
| .  /  . | .  /  . | .  .  . |
| .  /  . | .  /  . | .  .  . |
+---------+---------+---------+


Even more doubtful is this situation:
Code:

+---------+---------+---------+
| .  /  / | .  .  . | .  .  . |
| <  X  X | <  <  < | <  <  < |
| .  /  / | .  .  . | .  .  . |
+---------+---------+---------+
| ?  X  X | <  <  < | <  <  < |
| ?  #  / | .  .  . | .  .  . |
| ?  #  / | .  .  . | .  .  . |
+---------+---------+---------+
| .  /  / | .  .  . | .  .  . |
| .  /  / | .  .  . | .  .  . |
| .  /  / | .  .  . | .  .  . |
+---------+---------+---------+


Thank's in advance for your comments.

Kyriako.
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Tue Jul 28, 2009 4:55 pm    Post subject: Reply with quote

First things first: I have only skimmed over the preceeding posts, so the following is only an educated guess...

When constructing a chain or loop you often find candidates that are linked to more than one other candidate. You have to pick one of the possibilities to continue in the chain. Your '?' candidates are exactly that: They can be a '<' or a '>', you are free to choose what you like.

Let's take your second grid (?(<) means '?' taken as '<'):
Code:
+---------+---------+---------+
| .  /  . | .  /  . | .  .  . |
| <  X  < | <  X  < | <  <  < |
| .  /  . | .  /  . | .  .  . |
+---------+---------+---------+
| ?  X  ? | <  X  < | <  <  < |
| >  #  > | .  /  . | .  .  . |
| >  #  > | .  /  . | .  .  . |
+---------+---------+---------+
| .  /  . | .  /  . | .  .  . |
| .  /  . | .  /  . | .  .  . |
| .  /  . | .  /  . | .  .  . |
+---------+---------+---------+

If you link to the {Fish Group} first, you can only link back to the originating '?' (that gives you Nice Loops for the fish eliminations) or to any other '>' which doesnt make sense, because in that case '?' and '>' are directly weakly linked.
Example: ?(<) - {Fish Group} = {Fin Group} - ?(>) ... eliminates ?

If you link to the {Fin Group} you can continue with any of the '<':
?(>) - {FinGroup} = {Fish Group} - <
This gives some nice new possibilities for the '<' in row two.

Your third grid is wrong IMHO (your '?' candidates are the possible eliminations of the Finned Fish). It should be:
Code:
+---------+---------+---------+
| .  /  / | .  .  . | .  .  . |
| <  X  X | <  <  < | <  <  < |
| .  /  / | .  .  . | .  .  . |
+---------+---------+---------+
| ?  X  X | <  <  < | <  <  < |
| >  #  / | .  .  . | .  .  . |
| >  #  / | .  .  . | .  .  . |
+---------+---------+---------+
| .  /  / | .  .  . | .  .  . |
| .  /  / | .  .  . | .  .  . |
| .  /  / | .  .  . | .  .  . |
+---------+---------+---------+


PS: I dont think 'Kraken X-Wing' is correct in your case. A Kraken fish is a combination of a fish with one or more chains. You use a Finned Fish as link in a chain, which is not the same.
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Tue Jul 28, 2009 9:24 pm    Post subject: Reply with quote

Nothing competes with a real example -- even if it's a larger fish.

Code:
 +--------------------------------------------------------------------------------+
 |  1238    5       1378    |  13789   3789    1379    |  478     6       12479   |
 |  168     1678    4       |  156789  2       15679   |  3       189     1789    |
 |  9       2678    1378    |  13678   4       1367    |  78      128     5       |
 |--------------------------+--------------------------+--------------------------|
 |  248     9       6       |  1237    37      1237    |  5       248     2478    |
 |  123     127     137     |  4       5       8       |  67      29      2679    |
 |  248     2478    5       |  2679    79      2679    |  1       3       2478    |
 |--------------------------+--------------------------+--------------------------|
 |  7       148     189     |  589     6       459     |  2       1458    3       |
 |  4568    468     2       |  37      1       37      |  9       458     468     |
 |  456     3       189     |  2589    89      2459    |  468     7       1468    |
 +--------------------------------------------------------------------------------+

Code:
 +-----------------------------------+
 |  8  . *8  |  8 *8  .  | *8  .  .  |
 |  8  8  .  |  8  .  .  |  .  8  8  |
 |  .  8 *8  |  8  .  .  | *8 -8  .  |
 |-----------+-----------+-----------|
 |  8  .  .  |  .  .  .  |  .  8  8  |
 |  .  .  .  |  .  .  8  |  .  .  .  |
 |  8  8  .  |  .  .  .  |  .  .  8  |
 |-----------+-----------+-----------|
 |  .  8 @8  |  8  .  .  |  .  8  .  |
 |  8  8  .  |  .  .  .  |  .  8  8  |
 |  .  . *8  |  8 *8  .  | *8  . -8  |
 +-----------------------------------+

Code:
Kraken Swordfish (*) c357\r139 => [r3c8],[r9c9]<>8

w/remote cell (@): (8) r7c3 - r7c4 = r9c45 - r9c7 = r13c7 - r3c8
                                           - r9c9

FWIW: The chain from the remote cell does not have to be based on a single digit. However, I only use a single digit for my remote cell chains.
Back to top
View user's profile Send private message
kyriako

Joined: 12 Jun 2008
Posts: 16
:
Location: Germany

Items
PostPosted: Wed Jul 29, 2009 7:06 pm    Post subject: Finned X-Wing Reply with quote

Hello hobiwan,

thank you for your comment.
I had'nt seen that the "?" cells are elimination cells of the finned X-Wing.
Therefore, I think that theses cells should not(or even must not?)be used for linking the fish.
Regarding example 3:
in my oppinion it is a special case of the finned X-Wing. The condition for elimination is that a cell "sees" both strings of the X-Wing as well as the fin.
This means that all remaining cells in the box are elimination cells and the fin cannot be linked at all.
However, if this pattern has only one fin cell, linking is again possible:
Code:

+---------+---------+---------+
| .  /  / | .  .  . | .  .  . |
| <  X  X | <  <  < | <  <  < |
| .  /  / | .  .  . | .  .  . |
+---------+---------+---------+
| ?  X  X | <  <  < | <  <  < |
| ?  #  / | >  >  > | >  >  > |
| ?  /  / | .  .  . | .  .  . |
+---------+---------+---------+
| .  /  / | .  .  . | .  .  . |
| .  /  / | .  .  . | .  .  . |
| .  /  / | .  .  . | .  .  . |
+---------+---------+---------+


What is your oppinion?

Finally: of course "Kraken X-Wing" is not correct.
The reason for my mistake is that I had just finished coding this strategy, and the name sticked to my mind.

Kyriako.
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Thu Jul 30, 2009 2:36 pm    Post subject: Re: Finned X-Wing Reply with quote

kyriako wrote:
Regarding example 3:
in my oppinion it is a special case of the finned X-Wing. The condition for elimination is that a cell "sees" both strings of the X-Wing as well as the fin.

In fishing terms: All cover candidates that are not base candidates are potential eliminations (in case 3: all candidates in r24 except r24c23). All potential eliminations that see the fin (r5c2) become Fish eliminations. In your example thats only r4c1. r56c1 are cells that see the fin, but they cannot be eliminated by the fish.

I still see no reason why an elimination cell should not serve as link into the Fish group or the Fin group (except the obvious: you have already found an elimination so perhaps it should be done before continuing to search for a chain).
Back to top
View user's profile Send private message
kyriako

Joined: 12 Jun 2008
Posts: 16
:
Location: Germany

Items
PostPosted: Thu Jul 30, 2009 6:33 pm    Post subject: Reply with quote

Thank you hobiwan,
I see the example 3 from a practical point of view:
one method of checking the effect of a finned fish is to look at two possibilities:
1. one of the fin cells receives the candidate
2. one of base cells receives the candidate

If in both cases the candidate in a cell can be eliminated, then it is an elimination cell.

By the way, if there was no fin, the elimination cells would be:
Code:

+---------+---------+---------+
| *  /  / | .  .  . | .  .  . |
| *  X  X | *  *  * | *  *  * |
| *  /  / | .  .  . | .  .  . |
+---------+---------+---------+
| *  X  X | *  *  * | *  *  * |
| *  /  / | .  .  . | .  .  . |
| *  /  / | .  .  . | .  .  . |
+---------+---------+---------+
| .  /  / | .  .  . | .  .  . |
| .  /  / | .  .  . | .  .  . |
| .  /  / | .  .  . | .  .  . |
+---------+---------+---------+


Kyriako.
Back to top
View user's profile Send private message
hobiwan

Joined: 11 Feb 2008
Posts: 83
:

Items
PostPosted: Fri Jul 31, 2009 6:23 am    Post subject: Reply with quote

kyriako wrote:
By the way, if there was no fin, the elimination cells would be:
Code:

+---------+---------+---------+
| *  /  / | .  .  . | .  .  . |
| *  X  X | *  *  * | *  *  * |
| *  /  / | .  .  . | .  .  . |
+---------+---------+---------+
| *  X  X | *  *  * | *  *  * |
| *  /  / | .  .  . | .  .  . |
| *  /  / | .  .  . | .  .  . |
+---------+---------+---------+
| .  /  / | .  .  . | .  .  . |
| .  /  / | .  .  . | .  .  . |
| .  /  / | .  .  . | .  .  . |
+---------+---------+---------+

But these are two overlapping fishes, not just one:
X-Wing c23r24
Franken X-Wing c23b14

I didnt realize you were doing other fish types than basic fish.
Back to top
View user's profile Send private message
kyriako

Joined: 12 Jun 2008
Posts: 16
:
Location: Germany

Items
PostPosted: Sat Aug 01, 2009 6:14 pm    Post subject: Reply with quote

Hello hobiwan,
interesting hint.
Thank you.

Kyriako.
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Sat Aug 01, 2009 10:57 pm    Post subject: Reply with quote

kyriako wrote:
By the way, if there was no fin, the elimination cells would be:
Code:

+---------+---------+---------+
| *  /  / | .  .  . | .  .  . |
| *  X  X | *  *  * | *  *  * |
| *  /  / | .  .  . | .  .  . |
+---------+---------+---------+
| *  X  X | *  *  * | *  *  * |
| *  /  / | .  .  . | .  .  . |
| *  /  / | .  .  . | .  .  . |
+---------+---------+---------+
| .  /  / | .  .  . | .  .  . |
| .  /  / | .  .  . | .  .  . |
| .  /  / | .  .  . | .  .  . |
+---------+---------+---------+


Whether you have a fin cell or not in this scenario, you have a Locked Candidate 1 in [c1b7] that eliminates the candidate in [r123456c1]. After that, you have an X-Wing elimination in [r24c456789] if the fin is missing.
Back to top
View user's profile Send private message
kyriako

Joined: 12 Jun 2008
Posts: 16
:
Location: Germany

Items
PostPosted: Sun Aug 02, 2009 6:13 pm    Post subject: Reply with quote

Hello daj95376,
shame on me, not having seen this simple thing.

Kyriako
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron