X-chain optimalisation

Programs which generate, solve, and analyze Sudoku puzzles

X-chain optimalisation

Postby Hajime » Tue Oct 13, 2020 11:12 am

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?
User avatar
Hajime
 
Posts: 200
Joined: 20 April 2018
Location: Netherlands

Re: X-chain optimalisation

Postby mith » Tue Oct 13, 2020 4:59 pm

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
mith
 
Posts: 281
Joined: 14 July 2020

Re: X-chain optimalisation

Postby Hajime » Wed Oct 14, 2020 9:08 am

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
User avatar
Hajime
 
Posts: 200
Joined: 20 April 2018
Location: Netherlands

Re: X-chain optimalisation

Postby RSW » Thu Oct 15, 2020 6:08 am

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.
RSW
 
Posts: 68
Joined: 01 December 2018
Location: Western Canada

Re: X-chain optimalisation

Postby Hajime » Thu Oct 15, 2020 2:09 pm

RSW wrote: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.
User avatar
Hajime
 
Posts: 200
Joined: 20 April 2018
Location: Netherlands

Re: X-chain optimalisation

Postby RSW » Thu Oct 15, 2020 11:50 pm

Hajime wrote: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.
RSW
 
Posts: 68
Joined: 01 December 2018
Location: Western Canada

X-chain 4 naming

Postby Hajime » Sat Oct 17, 2020 8:42 am

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?
User avatar
Hajime
 
Posts: 200
Joined: 20 April 2018
Location: Netherlands

Re: X-chain 4 naming

Postby RSW » Sat Oct 17, 2020 9:40 am

Hajime wrote: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.
RSW
 
Posts: 68
Joined: 01 December 2018
Location: Western Canada

Re: X-chain optimalisation

Postby StrmCkr » Sun Oct 18, 2020 10:42 am

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)  .    . | .  .  . |
| .    .  . | .    .    . | .  .  . |
+-----------+-------------+---------+
| .    .  . | .    .    . | .  .  . |
| .    .  . | .    .    . | .  .  . |
| .    .  . | .    .    . | .  .  . |
+-----------+-------------+---------+
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 1165
Joined: 05 September 2006

Re: X-chain optimalisation

Postby Hajime » Tue Oct 20, 2020 11:42 am

StrmCkr wrote:
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.
User avatar
Hajime
 
Posts: 200
Joined: 20 April 2018
Location: Netherlands


Return to Software