X-Cycles questions

Post the puzzle or solving technique that's causing you trouble and someone will help

X-Cycles questions

Postby Mino21 » Fri Jul 08, 2022 3:14 pm

Hi all and sorry for my bad english! :)

I state to not be a great sudoku expert, but I am having fun by implementing a sudoku solver using the SudokuWiki site as reference for strategy list.
Obviously, to implement a good algorithm I need to understand the problem very well, so I would like to ask some questions:

1) on the site, loop rule 2 speaks about "two adjacent strong links", but I think that it can be extendend to a generic even sequence of consecutive strong links, right?
From a theoretical point of view it should be right, but from a practical point of view is it possible to have a rule 2 with an even sequence of >2 consecutive strong links (for example 4, 6, etc...)?

2) the site say that a strong link, if necessary, can be converted into a weak one. Can we generalize that a loop can contain any number of odd sequences of consecutive strong links? From a practical point of view, can it happen to have a sequence of >3 (5, 7, etc...) consecutive strong links?

3) can a loop contain 3 consecutive nodes (or, equivalently, 2 consecutive link) that belong to the same unit (row, column or box)? I think it shouldn't, because these two consecutive links, that must be weak (they cannot be strong by definition), imply a loop rule 3 that hides a loop_rule_1 that virtually allow more simultaneous candidate eliminations. Right?

4) about Grouped X-Cycles, can a loop contain only groups as node (from here on I will call them group-nodes)?

5) from a practical point of view, can we have a loop rule 2 or 3 that insists on a group-node?

6) from the point of view of optimization, during the loop search, should I give priority to group-nodes or normal (single) nodes?


Thnx!
“Without education, we are in a horrible and deadly danger of taking educated people seriously.”
User avatar
Mino21
 
Posts: 35
Joined: 08 July 2022
Location: Draghistan

Re: X-Cycles questions

Postby eleven » Tue Jul 12, 2022 4:06 pm

Still no answer ?? I almost lost the interest in this forum (the nicest news was that blue is still living), but a confirmed habit makes me trying to answer this one more time.
1) Yes and yes.
2) Yes, a strong link also works as a weak link in an alternating chain. Yes, there can be more than 4 strong links in a row.
3) ? One of 2 consecutive links must be strong.
4) Yes. [Edit: removed nonsense]
5) Don't understand the question.
6) Not sure. I would start with single nodes, because they are more common.
Last edited by eleven on Wed Jul 13, 2022 1:35 pm, edited 1 time in total.
eleven
 
Posts: 3152
Joined: 10 February 2008

Re: X-Cycles questions

Postby Mino21 » Tue Jul 12, 2022 10:41 pm

Thanks for the reply (and long live the old habits :mrgreen:)!

eleven wrote:2) Yes, a strong link also works as a weak link in an alternating chain. Yes, there can be more than 4 strong links in a row.

"row"? Or do you mean "cycle"?

eleven wrote:3) ? One of 2 consecutive links must be strong.

I will try to be clearer.
If in a generic row for example we have 5 candidates, and we connect 3 of them with two weak links (let's say rXc2==rXc4==rXc9), we will have a loop_rule_3 that allow us to eliminate the candidate in rXc4. But if we consider the same cycle with one less node, the one in rXc4, we will have a loop_rule_1 that allow us more eliminations at the same time.
in this sense I said that a cycle shouldn't contain 3 consecutive nodes (or, equivalently, 2 consecutive link) that belong to the same unit (row, column or box).
Is there something wrong with my reasoning?

eleven wrote:4) Yes (as strong links).

Sorry, but I don't understand what exactly you mean by "as strong links" in this case. Can you give an example?

eleven wrote:5) Don't understand the question.

As mentioned in the first post, about grouped_x_cycle, by group-node I mean a node consisting of a group of more (2 or 3) candidates.
So, pointing a generic node as N and a group-node as GN, we could have:

- loop_rule_3 on a group-node: ...--N==GN==N--...

- loop_rule_2 on a group-node: ...==N--GN--N==...

I was simply wondering if from a practical point of view it was possible to have situations of this type.
“Without education, we are in a horrible and deadly danger of taking educated people seriously.”
User avatar
Mino21
 
Posts: 35
Joined: 08 July 2022
Location: Draghistan

Postby Pat » Tue Jul 12, 2022 11:02 pm


    "in a row"
    = consecutive
User avatar
Pat
 
Posts: 4056
Joined: 18 July 2005

Re:

Postby Mino21 » Wed Jul 13, 2022 12:13 am

:oops:
“Without education, we are in a horrible and deadly danger of taking educated people seriously.”
User avatar
Mino21
 
Posts: 35
Joined: 08 July 2022
Location: Draghistan

Re: X-Cycles questions

Postby eleven » Wed Jul 13, 2022 1:49 pm

3) Yes (if a Rule 3 would eliminate the double weakly linked digit in a unit, there must be a Rule 1 loop with possibly more eliminations.)

4) please forget the nonsense "(as strong links)" (deleted it above). If i understood you right, the last grouped x-cycle sample in sudowiki is an example having only group nodes.

5) still don't get you, for building a chain there is no difference, if links are grouped or not. They either are weak links or strong links (which serve as weak links too).



I should state, that this sudowiki page is very old (about 2006). Nice loops are completely out of fashion, and usually were replaced by AIC's.
(A popular reference for solving strategies now is Bernhard Hobiger's hodoku site. But to my surprise it has not described and used grouped x-chains, it just shows them as grouped AIC's.)

Using AIC's, (grouped) x-cycles were replaced by (grouped) x-loops and (grouped) x-chains.
AIC's are "alternating inference chains" of strong and weak (possibly grouped) links, starting and ending with a strong one.
They are loops, if the last node would eliminate the first one ("sees" it, is linked to it), because in that case you could continue the chain with the first one and repeat forever.
All digits, which see the first and last node (have a link to both) then can be eliminated.

If you have a loop, it is said, that "weak links become strong links", i.e. (in the 1-digit case) you can eliminate the other digits in that units.
E.g. the AIC for the first 'Rule 1' example would be as follows ('=' is a strong, '-' a weak link). Here it does not matter, where you start the loop.
8C2 = G2 - H3 = H9 - J7 = 8C7, loop => -8G3,G9,C39
(without using the loop, you would eliminate 8C39, because they see both 8C2 and 8C9, and starting with other nodes you would get the other eliminations too)
These AIC loops are equivalent to the 'Rule 1' x-cycles, the AIC's without loop can make all eliminations of the other types. Instead of closing an alternating chain with 2 links, stop the chain and look if there are digits which see both ends.

In the sample for Rule 2 you have
1E3 = E7 - J7 = 1J1 => -1G3,F1 (forcing J1 with the strong link) (thats a "skyscraper")
Alternatively you could start the AIC in J1 and extend it to a cycle
1J1 = J8 - E8 = 1E3 - G3 = 1J1 => 1J1
But stopping at 1E3 already would give you the eliminations -1G3,F1.

Rule 3:
1C7 = G7 - G2 = 1H3 => -1C3 (thats a "kite")
8B1 = C3 - E3 = 8E7 => -8B7 (kite)

The last sample to grouped x-cycles is a loop with additional eliminations:
4AB7 = C89 - C12 = AB3 - HJ3 = G12 - G89 = 4HJ7, loop => -4C5,DE3,G56,EF7

There are many ways to find and describe single digit eliminations, and many names for them.
Grouped x-loops and x-chains will catch all the eliminations of x-cycles, as well as named patterns like (grouped) skyscrapers/kites/empty rectangles, finned and sashimi x-wings, turbot fish, 222 swordfish.
Also some simpler exotic fish eliminations can be done, e.g. in this sample solvers make the elimination of 7 in r9c4 with a "finned franken swordfish" or a "grouped swordfish", but a grouped x-chain also does the job.
Code: Select all
.---------------.-----------------.---------------.
| 6    379  79  | 137   137   5   | 8    4     2  |
| 5    8    1   |f37    4     2   |e37   9     6  |
|c37   24   24  | 8     6     9   |d357 d1357  13 |
:---------------+-----------------+---------------:
| 13   237  27  | 4     18    68  | 9    167   5  |
| 149  79   5   | 126   19    3   | 247  1267  8  |
| 149  6    8   | 1259  159   7   | 234  123   13 |
:---------------+-----------------+---------------:
|b79   5    3   |a79    2     1   | 6    8     4  |
| 8    1    469 | 3569  359   46  | 235  235   7  |
| 2    47   467 | 356-7 3578  468 | 1    35    9  |
'---------------'-----------------'---------------'
eleven
 
Posts: 3152
Joined: 10 February 2008

Re: X-Cycles questions

Postby Mino21 » Wed Jul 13, 2022 3:31 pm

Thanks, you cleared up all my doubts!

About AIC's I should study them better, but from your explanation I have already got a general idea of how they work.
Also, if I undestood, grouped_x_cycles are a subset of AIC's (and obviously x_cycles are a subset of grouped_x_cycles), in the sense that all grouped_x_cycles inferences are also AIC's inferences, but not viceversa. But i already implemented x_cycles and I don't have much to finish with grouped_x_cycles, so i want to finish it before moving on to other strategies, in the hope that it wasn't a complete waste of time, in the sense that the algorithms that I designed for grouped_x_cycles will work for AIC's too (or at least in part)! :mrgreen:

Finally, I still have some questions:

7) can two consecutive group-nodes that belong to the same box have a candidate in common?
That is, does it make sense to differentiate this

Image

from this

Image

or nothing changes for the purposes of the strategy?

8) by reasoning, I came to the conclusion that a grouped-loop (I mean a cycle with at least one group-node) allows us inferences that a normal-loop doesn't, only if at least one of the two link of every group-node is strong. Right?

9) which strategies are subset of grouped_x_cycles? i don't have a great culture about strategies, but i definitely think x-wings and all its variants. Is there anything else too?
“Without education, we are in a horrible and deadly danger of taking educated people seriously.”
User avatar
Mino21
 
Posts: 35
Joined: 08 July 2022
Location: Draghistan

Re: X-Cycles questions

Postby eleven » Thu Jul 14, 2022 7:58 am

In a box there are only three non-equivalent cases for group nodes in a mini-column, which could be part of an x-cycle. The small 'x' may be there or not:
Code: Select all
---------   ---------   ---------
| X . . |   | X . . |   | X . . |
| X . . |   | X . . |   | X . . |
| x . . |   | . X x |   | X X x |
---------   ---------   ---------
The first two just work like normal nodes:
In the first there must be two weak links to other cells in the column. So, as noted above, without them there must be a Role 1 x-cycle.
In the second there is both a strong and weak link between the minirow and minicolumn cells, just like between single cells. If e.g. - from the x-cycle - the group must be true (Role 3), then one of the 2 cells must be true.

The 3rd one is tricky.
There is a strong link between the minicolumn and the other 2 row cells (if all minicolumn cells are false, one of the other row cells must be true, and the rest of the row false then). But (unlike all the other strong links) there is NOT a weak link too, which would mean, that if one cell in the minicolumn is true, ALL cells in the minirow have to be false, so that an outside cell (not in the group) in the row had to be true. This is not the case, if the crossing cell is true.
So if it is part of an x-cycle, it has to work as a strong link only, with weak links on both ends.

Hopefully this answers 7) and 8)

9) the same as the equivalent grouped x-loops and x-chains. I have listed some above.
eleven
 
Posts: 3152
Joined: 10 February 2008

Re: X-Cycles questions

Postby Mino21 » Thu Jul 14, 2022 10:33 am

eleven wrote:Hopefully this answers 7) and 8)

Most likely yes, but it's not entirely clear to me, perhaps due to my unfamiliarity with these things, coupled with the fact that the algorithm I designed works differently.
Anyway I seem to understand that the answer should be yes to both 7) and 8).

Thanks for the replies, I should now be able to update my x_cycles algorithm to grouped_x_cycles. :D
“Without education, we are in a horrible and deadly danger of taking educated people seriously.”
User avatar
Mino21
 
Posts: 35
Joined: 08 July 2022
Location: Draghistan

Re: X-Cycles questions

Postby Mino21 » Mon Aug 15, 2022 11:23 am

Mino21 wrote:Thanks for the replies, I should now be able to update my x_cycles algorithm to grouped_x_cycles.

I guess I was too optimistic! :D

I have implemented much of the algorithm, but at this point:

Code: Select all
+------------------+-------------------+--------------------+
| 1      8   5     | 49    2    6      | 3    7     49      |
| 234    6   234   | 34579 134  13457  | 2458 28    24589   |
| 234    9   7     | 345   34   8      | 1    26    2456    |
+------------------+-------------------+--------------------+
| 4678   1   48    | 348   5    2      | 68   9     37      |
| 245789 27  2489  | 348   6    34     | 258  13    137     |
| 2568   3   28    | 1     7    9      | 2568 4     2568    |
+------------------+-------------------+--------------------+
| 2378   4   1     | 6     38   37     | 9    5     238     |
| 23789  27  2389  | 3457  1348 13457  | 2468 12368 123468  |
| 38     5   6     | 2     9    134    | 7    138   1348    |
+------------------+-------------------+--------------------+

the program returns me the following invalid cycle ("=' strong link, '-' weak link):

Code: Select all
START: r5c9==r5c8==(r8c8 r9c8)--(r8c8 r8c9)==(r8c5 r8c6)==r9c6==(r9c8 r9c9)--(r8c9 r9c9)==r5c9

more or less I think I understand why it is not a valid loop_rule_1, but I don't know what condition exactly I should add to my algorithm to have only valid loops.
I think the problem is related to the group-nodes that share a same candidate, but I honestly don't know what to do. I hope someone can help me!
“Without education, we are in a horrible and deadly danger of taking educated people seriously.”
User avatar
Mino21
 
Posts: 35
Joined: 08 July 2022
Location: Draghistan

Re: X-Cycles questions

Postby yzfwsf » Mon Aug 15, 2022 1:49 pm

X-Cycle:4r1c9 = r1c4 - r23c5 = r8c5 - r8c79 = r9c9 - 4r1c9 => r2c4<>4,r2c6<>4,r2c9<>4,r3c4<>4,r3c9<>4,r8c4<>4,r8c6<>4,r8c9<>4
There is overlapping cell(r8c9) here, but the overlapping cell is only included in the previous node.
or
4r1c9 = r1c4 - r23c5 = r8c5 - r8c7 = r89c9 - 4r1c9 => r2c4<>4,r2c6<>4,r2c9<>4,r3c4<>4,r3c9<>4,r8c4<>4,r8c6<>4,r8c9<>4
The overlapping cell is only included in the next node.
yzfwsf
 
Posts: 905
Joined: 16 April 2019

Re: X-Cycles questions

Postby Mino21 » Mon Aug 15, 2022 3:55 pm

yzfwsf wrote:X-Cycle:4r1c9 = r1c4 - r23c5 = r8c5 - r8c79 = r9c9 - 4r1c9 => r2c4<>4,r2c6<>4,r2c9<>4,r3c4<>4,r3c9<>4,r8c4<>4,r8c6<>4,r8c9<>4
There is overlapping cell(r8c9) here, but the overlapping cell is only included in the previous node.
or
4r1c9 = r1c4 - r23c5 = r8c5 - r8c7 = r89c9 - 4r1c9 => r2c4<>4,r2c6<>4,r2c9<>4,r3c4<>4,r3c9<>4,r8c4<>4,r8c6<>4,r8c9<>4
The overlapping cell is only included in the next node.

What i need is a general rule that tell me what constraints must be respected for a loop to be valid, with those examples are you telling me that in a valid loop, group-nodes can never share a same cell?

and if we have a similar case:

Code: Select all
---------
| x x x |
|   x   |
|   x   |
---------

how should it be interpreted?
- Is it possible to have a strong link in the box between the entire mini-row and the entire mini-column that share a cell (with the possibility of having a strong link both on the row and on the column)?
- Is it possible to have as group-node only a part of a mini-row or of a mini-column? In other words is it possible to assign the cell in common either to the mini-row or to the mini-column (but so we will have at least a weak link on the column or on the row)?

I hope I have been clear enough!
“Without education, we are in a horrible and deadly danger of taking educated people seriously.”
User avatar
Mino21
 
Posts: 35
Joined: 08 July 2022
Location: Draghistan

Re: X-Cycles questions

Postby yzfwsf » Tue Aug 16, 2022 12:09 am

X-Cycle has a similar structure:
(llc1 == rlc1) -- (llc2 == rlc2) -- (llc3 == rlc3) ... (llcn == rlc1), all llc can not include overlapping cells.
yzfwsf
 
Posts: 905
Joined: 16 April 2019

Re: X-Cycles questions

Postby Mino21 » Tue Aug 16, 2022 10:06 am

Sorry, but I don't know how to interpret what you wrote:
- what do "llc" and "rlc" exactly mean? left/right something?
- assuming that "-" and "=" have the usual meaning, what do the brackets represent in this case?
“Without education, we are in a horrible and deadly danger of taking educated people seriously.”
User avatar
Mino21
 
Posts: 35
Joined: 08 July 2022
Location: Draghistan

Re: X-Cycles questions

Postby yzfwsf » Tue Aug 16, 2022 10:55 am

llc is off candidates, rlc is on candidates, llc==rlc is strong link, rlc--llc is weak link,brackets for distinguish strong and weak links.
Or to be clear, when you are dealing with overlapping cells, treating it as a weak link has bugs and cannot guarantee the correctness of subsequent strong links.
yzfwsf
 
Posts: 905
Joined: 16 April 2019

Next

Return to Help with puzzles and solving techniques