The New Sudoku Players' Forum

[Hajime]

Suppose an X-chain of length 8 and the cell-numbers are 1-2-3-4-5-6-7-8, and the target candidate is '3'.
Odd-numbered cell have '3' OFF, even numbered cells have '3' ON.
Strong link between odd-even and weak link between even-odd cells.
Rule: all cells that 'see' cell 1 AND 8 can eliminate '3'. Start-cell number is 1 and end-cell must be even.

Now an optimization:
A. all cells that 'see' any odd-numbered cell and any even-numbered cell can eliminate '3'.

Further: The X-chain will be extended with cell-number 9 and it collides with the chain itself.

If it collides with an odd numbered cell, say 5, (cell 5 and 9 are the same) we get an continuous nice loop (X-cycle).
B1. All cells that see both an even AND an odd numbered cell between 5 and 9 (same cell) can eliminate '3'.
B2. We cannot say anything about cell number 1.
B3. If statement A is correct, statement B1 is already dealt with.

If it collides with an even numbered cell, say 4, (cell 4 was ON and must be OFF ) we get an discontinuous nice loop (X-cycle).
C1. Cell numbered 4 cannot have '3'.
C2. Cell number 1, that lead to cell 4 has a '3', is also false and must be '3'.

If the X-chain was of odd-length (say 7) and extended with cell 8 then
If it collided with cell 5 (odd number) :
D1. Cell 5 must be '3', other candidates in cell 5 to be eliminated.
D2. Cell number 1, that lead to cell 5 not having a '3', is also false and must be '3'.

If it collided with cell 4 (even number) :
We get a continuous nice loop
E1. All cells that see both an even AND an odd numbered cell between 4 and 9 (same cell) can eliminate '3'.
E2. We cannot say anything about cell number 1.
E3. If statement A is correct, statement E1 is already dealt with.

B=E and C=D depending on odd/even.

Are all statements above correct? Did I miss something?

[mith]

Statement A is not quite true. What is true is the more general statement that applies to any AIC:

A'. If a chain is composed of alternating strong and weak links, beginning and ending with strong links, removing the first two or last two nodes/links in the chain results in another valid chain. As a result, all candidates that 'see' any odd-numbered cell and any even-numbered cell later in the chain can be eliminated.

For your example, you could not eliminate 3 from a cell only on the basis of it seeing cells 2 and 7. The chain could look like: FFTFTF or FTFFTF or FTFTFF; since there are now more weak links than strong links, you can only show that there is a weak link between the ends (2-7), whereas the original chain shows a strong link between the ends (1=8).

B1 fills in this gap, because the loop can be traversed the other direction:

1=2-3=4-5=6-7=8-1 becomes 2=1-8=7

[Hajime]

Thanks mith,
I will change the A statement.
A. all cells that 'see' any odd-numbered cell X and any even-numbered cell Y, where X<Y, can eliminate '3'.
Now statement B3 and E3 can be deleted

[RSW]

I guess it also depends on how you implement your chain constructor.

In my solver, it starts by building a list of strongly linked cell pairs for the digit under consideration. The x-chain is then built starting with the first pair (A=B), and then (if possible) finding another pair (C=D) that has a weak link to one end or the other of the currently existing chain. (If no add-on pairs can be found for the first pair, then the first pair is rejected, and the next pair from the list is chosen as the starting point, etc.)
Thus, after the second pair is added we have:
A=B–C=D
or
A=B–D=C
or
B=A–C=D
or
B=A–D=C

These first two pairs form a Turbot fish of some kind, so that exclusions are immediately possible.

After each new pair is added, the solver checks for any exclusions that can be made. If there's an exclusion, then the routine terminates. If there's no exclusion, another pair is added to the chain (if possible), and the solver again checks for exclusions. This prevents the chain from becoming unnecessarily long. Using this construction method, there is always an even number of cells in the chain.

[Hajime]

I guess it also depends on how you implement your chain constructor.

In my solver, it starts by building a list of strongly linked cell pairs for the digit under consideration. The x-chain is then built starting with the first pair (A=B), and then (if possible) finding another pair (C=D) that has a weak link to one end or the other of the currently existing chain. (If no add-on pairs can be found for the first pair, then the first pair is rejected, and the next pair from the list is chosen as the starting point, etc.)
...
After each new pair is added, the solver checks for any exclusions that can be made. If there's an exclusion, then the routine terminates. If there's no exclusion, another pair is added to the chain (if possible), and the solver again checks for exclusions. This prevents the chain from becoming unnecessarily long. Using this construction method, there is always an even number of cells in the chain.

My subroutine is almost the same and is recursive. At each recursive depth a strong-link-pair is added to the X-chain. So always an even number of cells in the chain.
Up to now I only check for eliminations regarding cell #1 with the last cell, so #1 with #4, #1 with #6, #1 with #8, etc
The pairing and the checking is for all types of houses, so: rows, columns, boxes, diagonals, asterisk, jigsaw etc. Also mixed per chain.

I intent to check (eg. at depth 4) also #3 with #8, #5 with #8, #7 with #8 and also make code to check (and act upon) nice loops.
Only in case of a discontinuous nice loop the process will be stopped after elimination (we have a solution for a cell, and the chain is not valid anymore), otherwise continued.

Because all types of Turbot Fishes (X-chain of length 4) are widely named and recognized, a checkbox can be chosen by the user, to examine these methods. This is done by calling the subroutine "X-chain(2)" with a max of depth 2. Equal to a chain length of 4. Again though for all types of houses, not limited to rows,cols,boxes.

[RSW]

Up to now I only check for eliminations regarding cell #1 with the last cell, so #1 with #4, #1 with #6, #1 with #8, etc

Okay, I see what you mean. My solver does exactly the same thing. I hadn't considered checking intermediate cells with the last cell, as these would be picked up in a later chain iteration that starts with the applicable cell pair. Your suggested method of back-checking from the newly added pair to all of the intermediate pairs would likely be more efficient than waiting for a later chain. There is always a trade off though. Adding more checks will increase processing time for the individual chain, but may save time overall.

[Hajime]

A turbot fish is a X-chain of length 4.
Is every X-chain of length 4 a turbot fish?
A turbot fish can be a skyscraper, 2string kite or an empty rectangle.
Are there more possibilities?
Are a turbot crane and an empty rectangle the same?

[RSW]

Is every X-chain of length 4 a turbot fish?

I'm no expert, but from what I've seen on this site, it appears that just about all length-4 X-chains are some variant of a turbot fish. My solver used to have a separate solving routine for the turbot fish variations, but I retired it when I added the x-chain routine, since it handles them all. In the output it identifies skyscrapers and two string kites as such. It calls all other length 4 x-chains generic turbot fish. Everything longer than length 4 are simply identified as x-chains.

I know that empty rectangles are considered a type of x-chain, but I'm still trying to wrap my head around that.

I've seen turbot cranes mentioned a couple of times, but don't think I've ever seen a formal definition of it.

Personally, I think people get too carried away, trying to come up with names for every possible variation of a general pattern. I'm perfectly happy calling an X-chain an X-chain.

[StrmCkr]

Are a turbot crane and an empty rectangle the same?

yes and no.

Empty rectangle defined as 4 empty rectangle aligned cells in a box that contains a strong weak relationship on the row/col {has no restrictions to active cell count in the box which can be 2-5}

Loader Crane is a empty rectangle of 3-5 cells in a box.Which is a name me and space hashed out when discussing the minimal er pattern instead of just leaving it as an er (min 2 cells) or er (min+1 - max{5}) definition.

Tower Crane{turbot crane} is the minimal version of a ER {2 cells in a box}

http://forum.enjoysudoku.com/name-this-turbot-fish-type-t35499-30.html?hilit=turbot%20crane

The biggest headache for x cycles is grouped nodes especially when they share a sector which is where eliminations hang up the most especially since er tend to use group nodes in a box there is a row/col swap to consider.

also they hang up when trying to explain multiple grouped node for things like 9 cell active sword fish, and it delves into fish terminology instead of figuring out a multi nodule method for. Recognizing pseudo/indirect overlaps Of chain segments, but that's what happen when its built around logic gates instead of set-wise mathematics but digress.

or even easier cases like this some cant find them as x-cycles

Code: Select all

///|xxx|xxx
xxx|...|...
///|xxx|xxx

all the dots <> x
fraken x-wing

Now if you would like an easier method swap to mini row/col by box storage systems and strong link x cycles are fast and easier to spot with out sector issues for eliminations which is what I use for turbots (size 2 fish) for the named shorted chains

for reference the solver simple sudoku has simple coloring {x-cycles } and it too doesn't work on the ER"S he was planning on upgrading it to include them but that was never released {the row/col swap on nodes in a box was his hangup as well}

Code: Select all

+-----------+---------------+---------+
| (1)  .  . | .    -1   .   | .  .  . |
| .    .  . | .    .    .   | .  .  . |
| .    .  . | .    .    .   | .  .  . |
+-----------+---------------+---------+
| .    .  . | .    (1)  .   | .  .  . |
| (1)  .  . | (1)  (1)  (1) | .  .  . |
| .    .  . | .    (1)  .   | .  .  . |
+-----------+---------------+---------+
| .    .  . | .    .    .   | .  .  . |
| .    .  . | .    .    .   | .  .  . |
| .    .  . | .    .    .   | .  .  . |
+-----------+---------------+---------+

Col = Col - Row = Col eliminate cell is visible on Row of R1c1 and Col of R46C5
or simply put elimination cell is peers of cells R46C5 & R1C1

{compared to normal x-cycles that use 1 cell start and end}

Code: Select all

+-----------+-------------+---------+
| (1)  .  . | .    -1   . | .  .  . |
| .    .  . | .    .    . | .  .  . |
| .    .  . | .    .    . | .  .  . |
+-----------+-------------+---------+
| .    .  . | .    (1)  . | .  .  . |
| (1)  .  . | (1)  .    . | .  .  . |
| .    .  . | .    .    . | .  .  . |
+-----------+-------------+---------+
| .    .  . | .    .    . | .  .  . |
| .    .  . | .    .    . | .  .  . |
| .    .  . | .    .    . | .  .  . |
+-----------+-------------+---------+

[Hajime]

Code: Select all

+-----------+---------------+---------+
| (1)  .  . | .    -1   .   | .  .  . |
| .    .  . | .    .    .   | .  .  . |
| .    .  . | .    .    .   | .  .  . |
+-----------+---------------+---------+
| .    .  . | .    (1)  .   | .  .  . |
| (1)  .  . | (1)  (1)  (1) | .  .  . |
| .    .  . | .    (1)  .   | .  .  . |
+-----------+---------------+---------+
| .    .  . | .    .    .   | .  .  . |
| .    .  . | .    .    .   | .  .  . |
| .    .  . | .    .    .   | .  .  . |
+-----------+---------------+---------+

Col = Col - Row = Col eliminate cell is visible on Row of R1c1 and Col of R46C5 or simply put elimination cell is peers of cells R46C5 & R1C1

Thank you StrmCkr
I think I will name a Skyscraper and a 2-string kite separately and the rest of all X-chain of length 4 a Turbotfish.
Busy programming a X-chain method and I do not identify grouped and minimal methods.
Also my algoritm will not detect above a (-1)r1c5, because the end-link is weak, must be strong normally.

[StrmCkr]

because the end-link is weak, must be strong normally.

not sure on that comment as the common end points of a a 2 string kite are weakly related to the chain same as an ER {pretty much all chains with the exception of loops}

this is a grouped 2 string kite {uses strong links on the row & col }

Code: Select all

+-----------+---------------+---------+
| .    .  . | .    .    .   | .  .  . |
| -1   .  . | .    (1)  .   | .  .  . |
| .    .  . | .    .    .   | .  .  . |
+-----------+---------------+---------+
| .    .  . | 1    (1)  1   | .  .  . |
| (1)  .  . | (1)  .    (1) | .  .  . |
| .    .  . | 1    (1)   1  | .  .  . |
+-----------+---------------+---------+
| .    .  . | .    .    .   | .  .  . |
| .    .  . | .    .    .   | .  .  . |
| .    .  . | .    .    .   | .  .  . |
+-----------+---------------+---------+

un grouped 2 string kite
{uses strong links on the row & col }

Code: Select all

+-----------+-------------+---------+
| .    .  . | .    .    . | .  .  . |
| -1   .  . | .    (1)  . | .  .  . |
| .    .  . | .    .    . | .  .  . |
+-----------+-------------+---------+
| .    .  . | 1    (1)  1 | .  .  . |
| (1)  .  . | (1)  .    . | .  .  . |
| .    .  . | 1    .    1 | .  .  . |
+-----------+-------------+---------+
| .    .  . | .    .    . | .  .  . |
| .    .  . | .    .    . | .  .  . |
| .    .  . | .    .    . | .  .  . |
+-----------+-------------+---------+

skyscraper

Code: Select all

+-----------+-------------+---------+
| .  .    . | .   .    .  | .  .  . |
|.  (1) . | -1  .    -1 | .  .  . |
| -1 .  - 1| .   (1)  .  | .  .  . |
+-----------+-------------+---------+
| .  .    . | .   .    .  | .  .  . |
| .  (1)  . | .   (1)  .  | .  .  . |
| .  .    . | .   .    .  | .  .  . |
+-----------+-------------+---------+
| .  .    . | .   .    .  | .  .  . |
| .  .    . | .   .    .  | .  .  . |
| .  .    . | .   .    .  | .  .  . |
+-----------+-------------+---------+

finned x-wing

Code: Select all

+-----------+-------------+---------+
| .  .    . | .   (1)  .  | .  .  . |
| .  (1)  . | -1  (1)  -1 | .  .  . |
| .  .    . | .   (1)  .  | .  .  . |
+-----------+-------------+---------+
| .  .    . | .   .    .  | .  .  . |
| .  (1)  . | .   (1)  .  | .  .  . |
| .  .    . | .   .    .  | .  .  . |
+-----------+-------------+---------+
| .  .    . | .   .    .  | .  .  . |
| .  .    . | .   .    .  | .  .  . |
| .  .    . | .   .    .  | .  .  . |
+-----------+-------------+---------+

sashimi x-wing

Code: Select all

+-------------+-----------+---------+
| -1  .    -1 | .  (1)  . | .  .  . |
| .   (1)  .  | 1  .    1 | .  .  . |
| .   (1)  .  | .  .    . | .  .  . |
+-------------+-----------+---------+
| .   .    .  | .  .    . | .  .  . |
| .   (1)  .  | .  (1)  . | .  .  . |
| .   .    .  | .  .    . | .  .  . |
+-------------+-----------+---------+
| .   .    .  | .  .    . | .  .  . |
| .   .    .  | .  .    . | .  .  . |
| .   .    .  | .  .    . | .  .  . |
+-------------+-----------+---------+

x-wing

Code: Select all

+-------------+-------------+------------+
| .   .    .  | .   .    .  | .   .   .  |
| -1  (1)  -1 | -1  (1)  -1 | -1  -1  -1 |
| .   .    .  | .   .    .  | .   .   .  |
+-------------+-------------+------------+
| .   .    .  | .   .    .  | .   .   .  |
| -1  (1)  -1 | -1  (1)  -1 | -1  -1  -1 |
| .   .    .  | .   .    .  | .   .   .  |
+-------------+-------------+------------+
| .   .    .  | .   .    .  | .   .   .  |
| .   .    .  | .   .    .  | .   .   .  |
| .   .    .  | .   .    .  | .   .   .  |
+-------------+-------------+------------+

Edit fixed skyscraper for elims

[Hajime]

A=B-C=D and A=B=C=D will be found.
A=B-C-D and A=B=C-D will not be found

[SpAce]

Hi Hajime,

I think I will name a Skyscraper and a 2-string kite separately and the rest of all X-chain of length 4 a Turbotfish.

I wish you didn't. There are no "rest of all X-chain of length 4" except one: Turbot Crane. Turbot Fish is the family name for the three subtypes: Skyscraper, 2-String Kite, and Turbot Crane (aka Loader Crane, Minimal ER). It should only be used to refer to the whole family, not also to a specific subtype. It was a mistake in the original spec, but it's now fixed.

There are no other subtypes of Turbot Fishes, so every non-grouped X-Chain of length 4 that is not a Skyscraper or a Kite is a Crane. It's that simple. Using those exact subtypes allows precise communication. Using the family name for one of the subtypes is ambiguous and unnecessary now that we have a specific name for it.

Similarly, there are three subtypes of Grouped Turbot Fishes: Grouped Skyscraper (aka Finned X-Wing), Grouped 2-String Kite, Grouped Turbot Crane (aka Tower Crane, ER). Of course almost everyone still calls the third type ER, and that's fine. Logically ER is the grouped version of a Turbot Crane.

[Hajime]

There are no "rest of all X-chain of length 4" except one: Turbot Crane. Turbot Fish is the family name for the three subtypes: Skyscraper, 2-String Kite, and Turbot Crane (aka Loader Crane, Minimal ER).

Thank you SpAce, that is the confirmation a was looking for.
I will call the methods: Skyscraper, 2-String Kite and Turbot Crane.
Now I have the challenge to implement also the "grouped" versions, because the examples of StrmCkr explained that a lot is to be gained.

[SpAce]

Thank you SpAce, that is the confirmation a was looking for.
I will call the methods: Skyscraper, 2-String Kite and Turbot Crane.

Excellent!