Mino21 wrote:... and please don't tell me that it works also like a weak link ... the whole question of "strong links working as weak links" is totally absent in my logical setting.
StrmCkr wrote:Your code shouldn't even be able to build it
StrmCkr wrote:(you said you found invalid loops)
Mino21 wrote:Maybe I was unclear, maybe also because of my bad english, but the algorithm I implemented does not find either of the two aforementioned loops, as more than two consecutive weak links are not allowed; in fact once arrived at one of these points:
r1c123 = r1c8-r8c8-r8c2 ...
r123c2 = r8c2-r8c8-r1c8 ...
the search for the next node necessarily requires a strong link (in the description of my algorithm it is clearly explained).
StrmCkr wrote:Now your asking to counter prove your software that skips elimination sequences that don't match a preset condition?
eleven wrote:Mino21 wrote:... and please don't tell me that it works also like a weak link ... the whole question of "strong links working as weak links" is totally absent in my logical setting.
Mino, please stop bothering people here, but start to read and understand.
You implemented x-cycles following SudoWiki:
X-Cycles (Part 1): A "Cycle", as the name implies, is a loop or joined-up chain of single digits with alternating strong and weak links.
X-Cycles (Part 2): A discontinuity occurs when we find two strong links next to each other (that is, with no weak link between them) or two weak links next to each other (with no strong link dividing them). These rules work only if there is exactly one discontinuity, and such a loop will always have an odd number of nodes.
Your chain only works, because the strong link IS a weak link.
| x x x |
|/ x / |
|/ x / |
------------------------------
| X X X | . . . |-X -X / |
| / X / | . . . | . . / |
| / -X / | . . . | . . x |
------------------------------
| . . . | . . . | . . / |
| . . . | . . . | . . / |
| . . . | . . . | . . / |
------------------------------
| / x / | . . . | . . / |
| / X / | . . . | . . / |
| x x x | . . . | . . x |
------------------------------
------------------------------
| X X X | . . . |-X -X / |
| / X / | . . . | . . / |
| / -X / | . . . | . . x |
------------------------------
| . / . | . . . | . . / |
| . / . | . . . | . . / |
| . / . | . . . | . . / |
------------------------------
| / x / | . . . | . . / |
| / X / | . . . | . . / |
| x x x | . . . | . . x |
------------------------------
------------------------------
| X X X | . . . | . -x . |
| / X / | . . . | . . . |
| / X / | . . . | . . . |
------------------------------
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
------------------------------
| / x / | . . . | / x / |
| X X X | . . . | x x x |
| / x / | . . . | / x / |
------------------------------
+----------------+------------+----------------+
| (1) (-1) (1) | -1 -1 -1 | (1) (-1) (1) |
| . (1) . | . . . | . (1) . |
| . (1) . | . . . | . (1) . |
+----------------+------------+----------------+
| . -1 . | . . . | . -1 . |
| . -1 . | . . . | . -1 . |
| . -1 . | . . . | . -1 . |
+----------------+------------+----------------+
| . (1) . | . . . | . (1) . |
| (1) (-1) (1) | -1 -1 -1 | (1) (-1) (1) |
| . (1) . | . . . | . (1) . |
+----------------+------------+----------------+
+---------------+---------+---------------+
| -1 (1) -1 | . . . | -1 (1) -1 |
| (1) . (1) | . . . | (1) . (1) |
| -1 (1) -1 | . . . | -1 (1) -1 |
+---------------+---------+---------------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
+---------------+---------+---------------+
| -1 (1) -1 | . . . | -1 (1) -1 |
| (1) . (1) | . . . | (1) . (1) |
| -1 (1) -1 | . . . | -1 (1) -1 |
+---------------+---------+---------------+
------------------------------
| X X X | . . . |-X -X / |
| / X / | . . . | . . / |
| / -X / | . . . | . . x |
------------------------------
| . . . | . . . | . . / |
| . . . | . . . | . . / |
| . . . | . . . | . . / |
------------------------------
| / x / | . . . | . . / |
| / X / | . . . | . . / |
| x x x | . . . | . . x |
------------------------------
This is not a cycle because box 3 does not connect to box 1.
------------------------------
| X X X | . . . |-X -X / |
| / X / | . . . | . . / |
| / -X / | . . . | . . x |
------------------------------
| . . . | . . . | . . / |
| . . . | . . . | . . / |
| . . . | . . . | . . / |
------------------------------
| / x / | . . . | . . / |
| / X / | . . . | . . / |
| x x x | . . . | . . x |
------------------------------
care to elaborate?How did you (StrmCkr) solve the problem of those early contradictions which prevents forming nice loops?
Mino21 wrote:a) only two candidates in an unit imply a strong link and hence the following two logical implications:
- Code: Select all
A => !B
!A => B
more than two candidates in a unit imply a weak link and hence the only following logical implication:
- Code: Select all
A => !B
b) a valid loop must have the following characteristics:
- at least 4 nodes;
- at least a weak link;
- at most an even subsequence of consecutive strong links or a subsequence of two consecutive weak links;
- (any number of odd subsequences of consecutive strong links).
c) loop rules (green=true and red=false; arrows indicate the starting point and the direction of the logical inferences):
d) implemented recursive algorithm about x-cycles (not grouped):
- I always start from a strong link, of which a candidate will be the arrival node that closes the loop, while I pass the other to the recursive function that, node by node, tries to build a loop;
- at each recursive call, I first use the information on the part of the loop constructed so far to deduce (using positions contained in point b)) if the next link can be weak or must necessarily be strong;
- then I derive the type of connection (weak or strong) that I would have in the other units to which the previous node belongs, and check that it is compatible with the result illustrated in the previous point;
- if it is compatible I consider the various candidates in that unit one at a time, and if the candidate considered is not already a node I add it to the cycle;
- at this point if the loop isn't closed I go on with other recursive calls.
with the specification that with grouped-x-cycles in the case of mini rows and mini columns that share a cell, it is necessary to consider the two cases obtained by assigning the common cell once to the horizontal group and once to the vertical one, as shown in the following image:
loop rule 1 is characterized by:
1) at least one weak link;
2) no subsequence of two consecutive weak links;
3) no even subsequence of consecutive strong links;
4) any number of odd subsequences of consecutive strong links;
5) even number of nodes (but this is a consequence of the previous points)
Proof: starting from a node belonging to a weak link, assuming once it is true and once it is false, and using the logical inferences contained in point a), we will obtain two perfectly mirror chains, which will allow us to eliminate the candidates in the unit to which the weak links belong (of course I am referring to the cells that are not nodes).
loop rule 2 is characterized by:
1) at least one weak link;
2) no subsequence of two consecutive weak links;
3) one even subsequence of consecutive strong links;
4) any number of odd subsequences of consecutive strong links;
5) odd number of nodes (but this is a consequence of the previous points)
Proof: starting from the node that starts the even subsequence of consecutive strong links, and assuming it is true, we will obtain a contradiction, which will allow us to eliminate the candidates in the nodes marked as true and that belong to the even subsequence of consecutive strong links.
loop rule 3 is characterized by:
1) at least one weak link;
2) one subsequence of two consecutive weak links;
3) no even subsequence of consecutive strong links;
4) any number of odd subsequences of consecutive strong links;
5) odd number of nodes (but this is a consequence of the previous points)
Proof: starting from the node that starts the subsequence of two consecutive weak links, and assuming once it is true and once it is false, we will obtain that the node that sees two weak links is false in both cases, which will allow us to eliminate the candidate in it;
---------
| x x x |
| / x / |
| / x / |
---------
StrmCkr wrote:
- Code: Select all
-------------------------
| X X X | . . . |-X-X / |
| / X / | . . . | . . / |
| /-X / | . . . | . . x |
-------------------------
| . . . | . . . | . . / |
| . . . | . . . | . . / |
| . . . | . . . | . . / |
-------------------------
| / x / | . . . | . . / |
| / X / | . . . | . . / |
| x x x | . . . | . . x |
-------------------------
I try to explain how my algorithm works in this case:
- as mentioned in point d), I always start from a strong link, for example the one in c9, and let r9c9 be the arrival node and r3c9 the starting node;
- from the data on the part of the cycle constructed so far, I deduce that the next link can also be weak (ALSO WEAK) and not necessarily strong (ONLY STRONG);
- considering all the possible connections from r3c9, at a certain point I add the node r1c78 with a weak link (-r1c78);
...going on with the notation introduced in the previous two lines...
- ALSO WEAK;
- -r1c123;
- ONLY STRONG;
- =r23c2;
- ALSO WEAK;
- -r78c2;
- ONLY STRONG;
- =r9c123;
- ALSO WEAK;
- -r9c9;
- the chain is closed, I check loop is valid and I deduce that it is a loop rule 3 that delete candidates in r1c78.
To sum up:
r9c9=r3c9-r1c78-r1c123=r23c2-r78c2=r9c123-r9c9
L.R.3 (loop rule 3): r1c78 (elimination)
The aforementioned cycle does not allow me to delete candidate in r3c2, but this other cycle yes:
r9c9=r3c9-r3c2-r789c2=r9c13-r9c9
L.R.3: r3c2
StrmCkr wrote:
- Code: Select all
-------------------------
| X X X | . . . |-X-X / |
| / X / | . . . | . . / |
| /-X / | . . . | . . x |
-------------------------
| . / . | . . . | . . / |
| . / . | . . . | . . / |
| . / . | . . . | . . / |
-------------------------
| / x / | . . . | . . / |
| / X / | . . . | . . / |
| x x x | . . . | . . x |
-------------------------
r9c9=r3c9-r1c78-r1c123=r23c2-r78c2=r9c123-r9c9
L.R.3: r1c78
r9c9=r3c9-r3c2-r789c2=r9c13-r9c9
L.R.3: r3c2
StrmCkr wrote:
- Code: Select all
-------------------------
| X X X | . . . | .-x . |
| / X / | . . . | . . . |
| / X / | . . . | . . . |
-------------------------
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
-------------------------
| / x / | . . . | / x / |
| X X X | . . . | x x x |
| / x / | . . . | / x / |
-------------------------
r8c123-r8c789=r79c8-r1c8-r1c123=r23c2-r79c2=r8c123
L.R.3: r1c8
P.O. wrote:hi Mino21, my reading of the diagram:
if r123c2 is not x then r2c8 is x then r9c13 is not x then one of r9c79 is x: it is not known which one
if r123c2 is not x then one of r1c13 is x then r1c7 is not x then one of r2c7 r3c9 is x it is not known which one
in either case the loop can't be built
creint wrote:Is your solver public somewhere (Mino21)?
Mino21 wrote:eleven wrote:Mino21 wrote: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 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.
"(r8c8 r9c8)--(r8c8 r8c9)"
This is not a weak link.
Weak link would mean, that if a digit is on one side, it cannot be on the other side.
But r8c8 is on both sides.
Okay
and I assume that the same reasoning would have applied even if the link had been strong
Mino21 wrote:Isn't this:Mino21 wrote:two consecutive group-nodes
cannot have a cell in common
a consequence of this:eleven wrote:"(r8c8 r9c8)--(r8c8 r8c9)"
This is not a weak link, which would mean, that if a digit is on one side, it cannot be on the other side. But r8c8 is on both sides.
?
-------------------------
| X X X | . . . | .-x . |
| / X / | . . . | . . . |
| / X / | . . . | . . . |
-------------------------
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | . . . | . . . |
-------------------------
| / x / | . . . | / x / |
| X X X | . . . | x x x |
| / x / | . . . | / x / |
-------------------------
r8c123-(r8c789=r79c8)-r1c8-(r1c123=r23c2)-(r79c2=r8c123)
L.R.3: r1c8
To sum up:
r9c9=r3c9-r1c78-r1c123=r23c2-r78c2=r9c123-r9c9
L.R.3 (loop rule 3): r1c78 (elimination)
Mino21 wrote:It may seem strange to you, but I used the SudokuWiki site only to understand the basic idea of the various solving techniques, but then, both for x-cycles and some other techniques, I built my own logic settings and algorithms.
Return to Help with puzzles and solving techniques
Users browsing this forum: No registered users and 0 guests