The New Sudoku Players' Forum

[aran]

Allan
As you say, not quite six of one and half a dozen of the other

[hobiwan]

Back again!

Any benchmarks/comparisons on your new RCD rules vs. your former RCD ALS chaining?

Benchmarks: Not representative (too many non RCD related changes).
Comparisons: I got a problem there. My old code took a very simple approach: I ignored doubly linked ALS completly as a special case. Double links were treated as two seperate possible links and I took the first RCD that was not equal to the last. That approach should get me all ALS chains I get now, so the only difference would be the newly introduced overlapping.

The old code should however fail on some cases. I am still wondering why I couldn't find a fail case till now. Take the following situation (forbidden under the rules presented in the first post, but valid for my old code):

a- ALS1 -b(c)- ALS2 -c- ALS3

Of the two possible RCDs b and c between ALS1 and ALS2 b is taken. That eliminates c as possible RCD between ALS2 and ALS3 and breaks the chain. The reverse direction however would still work which would be enough for a non looping chain to work correctly.

For a chain to fail we had to find a case that fails in both directions, e.g.:

a- ALS1 -b(c)- ALS2 -c- ALS3 -(c)d- ALS4 -a

The link -c- should fail in both directions resulting in an invalid chain (but how are the odds for finding such a chain?). On the whole I think DonM is right to not allow simply alternating RCDs in his tutorial. As long as double links are not handled correctly, chains could be invalid.

[hobiwan]

HoDoKu seems to avoid eliminations in any of the cells of participating ALSs. The two eliminations listed above as "cannibalistic but legal" are just that.

Thanks for the tip, thats clearly a bug. ALS-XZ and ALS-XY are handled differently from ALS Chains in HoDoKu (unfortunately) and I missed cannibalism in those two extra cases. I will correct that for the next release.

[hobiwan]

As a manual solver, you see what you see, but a programmed solver should IMO first find the smaller of two ALS-xz patterns.

That would probably require a thread of its own

HoDoKu finds the step with the most eliminations first (and not the smallest step), thats why Paul ended up with the step he posted. The original idea was, that such a logic would lead to shorter solutions, which didnt work as planned.

[ronk]

HoDoKu finds the step with the most eliminations first (and not the smallest step), thats why Paul ended up with the step he posted. The original idea was, that such a logic would lead to shorter solutions, which didnt work as planned.

"Finding the smallest step", the most elegant step, has been the hallmark of this "Advanced solving techniques" forum. Witness that posters are forever trying to outdo each other in this aspect.

If anything should have a separate thread, IMO it's the topic of "finding the shortest solution".

[PIsaacson]

Along the lines of finding the smallest step, and also regarding decomposing ALS sets into smallest logical unit:

I was looking for examples of dual-linked ALSs that could be "broken down" into a possibly smaller dual-linked ALS and hit this one in the royle17 (36628) collection #2730:


Without decomposing into the smaller dual-linked ALS r1c4 -78- b1x1358 on the right, r18<>78 is not permitted since they are the RCDs in dual-linked ALS r1c48 -78- b1x1358. I'm guessing that Allan's permutation solver finds all productive combinations of base/cover sets and displays the combined results. I've started doing something similar in my base/cover logic to take all the possible combinations of a given set of cells to see if there are eliminations from some smaller subset. For the r1c48 -78- b1x1358 my ALS engine showed:

Code: Select all

do_alschains - reducing r3c1.<125789> by <1> dual
do_alschains - reducing r2c3.<23789> by <3> dual
do_alschains - reducing r1c5.<34789> by <7> dual
do_alschains - reducing r1c5.<3489> by <8> dual
do_alschains - reducing r1c9.<1489> by <8> dual
do_alschains - reducing r1c1.<13789> by <9> dual
do_alschains - reducing r1c3.<3789> by <9> dual
do_alschains - reducing r1c5.<349> by <9> dual
do_alschains - reducing r1c9.<149> by <9> dual
do_alschains - reducing r2c3.<2789> by <9> dual
do_alschains - reducing r2c9.<89> by <9> dual
do_alschains - reducing r3c1.<25789> by <9> dual
do_alschains - reducing r3c3.<25789> by <9> dual
do_alschains - reducing r3c7.<1479> by <9> dual
do_alschains - reducing r3c9.<1489> by <9> dual
do_alschains - reducing r5c8.<2789> by <9> dual
do_alschains - reducing r6c8.<289> by <9> dual
do_alschains - reducing r7c8.<29> by <9> dual

do_alschains - reducing r1c8.<789> by <7> base/cover
do_alschains - reducing r1c8.<89> by <8> base/cover
do_alschains - reducing r4c2.<149> by <9> base/cover
do_alschains - reducing r8c2.<349> by <9> base/cover

do_alschains - base/cover {1n134 2n2 3n2} {78r1 9c2 13b1}

do_alschains - als[2x5/5] r1c48.<n789> -78- b1x1358.<n13789>

18 eliminations from standard dual-linked rules and 4 "outside" eliminations from consideration of the smaller base set consisting of 5 cells. Without trying the 5 cell subsets, my base/cover logic only found the 2 r48c2<>9 eliminations from the 6 cell base/cover set {1n1348 2n2 3n2} {789r1 9c2 13b1}.

Once again, less is more...

[Allan Barker]

Once again, less is more...

I'm guessing that Allan's permutation solver finds all productive combinations of base/cover sets and displays the combined results. I

More or less.....

In the manual Draw Logic as Sets mode it will find all eliminations and assignments as defined by the "scope" presented on the previous page. It's up to the user to provide links of interest.

In the Draw Logic as Sets, Auto mode, it fills in links as you edit. When it finds eliminations or assignments, it will show only the links (cover sets, seeing, RCDs, etc) that contribute to the eliminations or assignments. In this case, the scope includes all possible links.

In the Draw Logic as Candidates mode, one selects candidates, as if building a chain, and the program assigns both strong sets and links, and then displays the results. This mode was meant to bridge the gap between set/constraint reasoning and implication type reasoning. Someone not familiar with Sudoku methods could try out their own reasoning by hiding the logic with the trasparancy slider.

Answer, within the scope, the program finds all eliminations possible for a set of truths for a given method, which may be more but not less.

What happens to r1c8<>78 may be implimentation dependent, as you suggest. The smaller DL-ALS r1c4 -78- b1x1358 and the larger DL-ALS r1c48 -78- b1x1358 use the same RCDs so 78r1c8 must be goners in either case.

[ronk]

Answer, within the scope, the program finds all eliminations possible for a set of truths for a given method, which may be more but not less.

If one defined a sufficiently large set of truths (base sets, strong sets, ...), could xsudo -- in the absence of memory and time constraints -- make an assignment in every unsolved cell

[Allan Barker]

If one defined a sufficiently large set of truths (base sets, strong sets, ...), could xsudo -- in the absence of memory and time constraints -- make an assignment in every unsolved cell

Yes, the following is a solution to Easter Monster (21 clues) that uses 60 sets. All cells are assigned. This puzzle is a symetrical morph.

Code: Select all

001000002090400050600000700050903000000070000000850040007000600030009080200000001

+----------------------------------+---------------------------------+----------------------------------+
| (+4-3578)  (+7-48)    1          | (+3-567)   (+8-369)   (+5-678)  | (+9-348)    (+6-39)    2         |
| (+3-78)    9          (+2-38)    | 4          (+6-1238)  (+7-1268) | (+1-38)     5          (+8-36)   |
| 6          (+8-24)    (+5-2348)  | (+1-235)   (+9-1238)  (+2-158)  | 7           (+3-19)    (+4-389)  |
+----------------------------------+---------------------------------+----------------------------------+
| (+1-478)   5          (+4-268)   | 9          (+2-146)   3         | (+8-12)     (+7-126)   (+6-78)   |
| (+8-1349)  (+2-1468)  (+9-23468) | (+6-12)    7          (+4-126)  | (+3-12589)  (+1-2369)  (+5-3689) |
| (+7-139)   (+6-127)   (+3-269)   | 8          5          (+1-26)   | (+2-139)    4          (+9-367)  |
+----------------------------------+---------------------------------+----------------------------------+
| (+9-1458)  (+1-48)    7          | (+5-123)   (+4-1238)  (+8-1245) | 6           (+2-39)    (+3-459)  |
| (+5-14)    3          (+6-45)    | (+2-1567)  (+1-246)   9         | (+4-25)     8          (+7-45)   |
| 2          (+4-68)    (+8-4569)  | (+7-356)   (+3-468)   (+6-4578) | (+5-349)    (+9-37)    1         |
+----------------------------------+---------------------------------+----------------------------------+

EM2  239 Candidates\
     60 Sets   = {1C1245678 2C2345678 3C1345789 4C1235679 5C134679 6C2345689 7C124689 8C1235679 9C135789}
     179 Eliminations, 60 Assignments -->

[Draco]

If anything should have a separate thread, IMO it's the topic of "finding the shortest solution".

One would need to agree on several things to help guide such a discussion. For instance one might want to agree on:

- Which tecniques are acceptable?
- Within this accepted set, is there a ranking of which should be applied (e.g. always clear singles, then...)?
- Is it preferrable to make more eliminations in a single, complex step or to make shorter, easier to understand eliminations that occur in a sequence yielding the same result?

... and so on. In short, an agreed-upon way of scoring puzzles so that each move could be evaluated, not unlike the decisions made by chess programs (an apt analogy I first ran across in the Solver Programs forum).

I believe that once you have an agreed set of rules, you can develop a scoring method that follows those rules, and use that to brute-force your way through a puzzle to find the shortest path according to those rules. One could do that manually or with software. In either case, it is only algorithms, time and memory . It reminds me of high school geometry, where our teacher would encourage us to find the "most elegant" proof (usually defined as the one with the fewest steps).

Given the brute-force nature of this sort of search, perhaps this thread -- if started -- would find an interesting home in the Solver Programs forum.

Cheers...

- drac

[aran]

If one defined a sufficiently large set of truths (base sets, strong sets, ...), could xsudo -- in the absence of memory and time constraints -- make an assignment in every unsolved cell

Yes, the following is a solution to Easter Monster (21 clues) that uses 60 sets. All cells are assigned. This puzzle is a symetrical morph.

Code: Select all

001000002090400050600000700050903000000070000000850040007000600030009080200000001

+----------------------------------+---------------------------------+----------------------------------+
| (+4-3578)  (+7-48)    1          | (+3-567)   (+8-369)   (+5-678)  | (+9-348)    (+6-39)    2         |
| (+3-78)    9          (+2-38)    | 4          (+6-1238)  (+7-1268) | (+1-38)     5          (+8-36)   |
| 6          (+8-24)    (+5-2348)  | (+1-235)   (+9-1238)  (+2-158)  | 7           (+3-19)    (+4-389)  |
+----------------------------------+---------------------------------+----------------------------------+
| (+1-478)   5          (+4-268)   | 9          (+2-146)   3         | (+8-12)     (+7-126)   (+6-78)   |
| (+8-1349)  (+2-1468)  (+9-23468) | (+6-12)    7          (+4-126)  | (+3-12589)  (+1-2369)  (+5-3689) |
| (+7-139)   (+6-127)   (+3-269)   | 8          5          (+1-26)   | (+2-139)    4          (+9-367)  |
+----------------------------------+---------------------------------+----------------------------------+
| (+9-1458)  (+1-48)    7          | (+5-123)   (+4-1238)  (+8-1245) | 6           (+2-39)    (+3-459)  |
| (+5-14)    3          (+6-45)    | (+2-1567)  (+1-246)   9         | (+4-25)     8          (+7-45)   |
| 2          (+4-68)    (+8-4569)  | (+7-356)   (+3-468)   (+6-4578) | (+5-349)    (+9-37)    1         |
+----------------------------------+---------------------------------+----------------------------------+

EM2  239 Candidates\
     60 Sets   = {1C1245678 2C2345678 3C1345789 4C1235679 5C134679 6C2345689 7C124689 8C1235679 9C135789}
     179 Eliminations, 60 Assignments -->

Just seen this.
Extraordinary.

[ronk]

If one defined a sufficiently large set of truths (base sets, strong sets, ...), could xsudo -- in the absence of memory and time constraints -- make an assignment in every unsolved cell

Yes, the following is a solution to Easter Monster (21 clues) that uses 60 sets. All cells are assigned.

Code: Select all

EM2  239 Candidates\
     60 Sets   = {1C1245678 2C2345678 3C1345789 4C1235679 5C134679 6C2345689 7C124689 8C1235679 9C135789}
     179 Eliminations, 60 Assignments -->

Very impressive I note that all the strongs sets are column sets. Does that work for all row sets too? All box sets?

Here's somewhat of a head start.

Code: Select all

Row 239 Candidates
     60 Sets = {3456789R1 123678R2 1234589R3 124678R4 12345689R5 123679R6 1234589R7 124567R8 3456789R9}


Box 239 Candidates
     60 Sets = {234578B1 12356789B2 134689B3 12346789B4 1246B5 12356789B6 145689B7 12345678B8 234579B9}

I tried, but my xsudo version says 'Diagram too big'.

[Allan Barker]

Here's somewhat of a head start.

Code: Select all

Row 239 Candidates
     60 Sets = {3456789R1 123678R2 1234589R3 124678R4 12345689R5 123679R6 1234589R7 124567R8 3456789R9}

Box 239 Candidates
     60 Sets = {234578B1 12356789B2 134689B3 12346789B4 1246B5 12356789B6 145689B7 12345678B8 234579B9}

I tried, but my xsudo version says 'Diagram too big'.

Mine, too. That's the 2D "ttt" type diagram, which has become too big for the screen. The logic image should pop up in about 250 ms. on a normal computer. There are a few ways to place such logic**.

**Perhaps I should start a thread for xsudo questions/discussion. If anyone thinks they might be interested in trying the program and participating, they could send me a PM.
.

[PIsaacson]

Bernhard,

This is probably obvious to everyone else, and although I had coded it correctly, I recently re-discovered this: The cells containing the RCC candidates cannot be (reliably) shared between the ALSs linked by these RCCs. I modified my ALS engine recently and allowed overlap in RCC cells while investigating certain doubly-linked Death Blossoms, but with disastrous results. Sometimes it works, but more often it doesn't. Otherwise, non-RCC-linked cells can overlap with apparent impunity. Needless to say, I retracted the changes...

Cheers,
Paul

[hobiwan]

The cells containing the RCC candidates cannot be (reliably) shared between the ALSs linked by these RCCs.

A RCC only works, if it can only be true in one of the two connected ALS. If it can be true in both (as in overlapping ALS where the overlapping area includes at least one RCC), setting an RCC in the overlap area fails to turn the second ALS into a Locked Set, which entirely breaks the chain logic.