The New Sudoku Players' Forum

by **PIsaacson** » Sun Apr 05, 2009 1:03 pm

Aran,

Thanks for the high level overview. Now, how about opening a new thread and introducing your concepts in detail? I'm always on the look-out for newer/better/faster algorithms, especially if I can apply them manually to help solve tough puzzles.

Bernhard,

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

Cheers,
Paul

by **PIsaacson** » Mon Apr 06, 2009 3:57 am

Bernhard,

Example 1 is a really sweet ALS chain!!! Very tasty!!!

This is the closest I have come to duplicating example 1, but it demonstrates something that I've been working on recently: Any ALS chain > length 2 can be decomposed into sub-chains. This is especially effective in example 1 because 2 of the sub-chains are dual-linked ALS sets.

Picture 1 describes a modified view of the start of example 1 in where the dual-linked subset chain A+(some of C)-B is now:
r13c4 {278} -27- r2c2569 {23789} => r4c5<>78, r2c3<>389, r3c6<>28, r58c4<>8, r2c56<>8 (cannibalistic) -- ignoring the Xsudo assignment of r2c9=8 (which it does) + 6 eliminations

Picture 2 describes the addition of r8c4 to the overall logic and dual-linked subset chain B-C is now:
r2c2569 {23789} -27- r138c4 {2678} => r5c4<>6, r8c6<>6 -- many of the potential eliminations are already covered by sub-chain 1

Picture 3 describes the addition of r8c6 to the overall logic and a non dual-linked subset chain C-D-(some of D) is now:
r138c4 {2678} -6- r8c6 {68} => r456c6<>8 -- but these are because of the assignments r8c4=6, r8c6=8

Picture 4 describes the entire set of cells as defined by example 1, but notice that the addition of r9c56 doesn't contribute to the logic, so I guess they are superfluous?

Anyway, the point is that the combination of the cells described in example 1 contains many potential eliminations beyond what can be discovered by just examining the end-point ALSs. Decomposition into sub-chains really squeezes the most mileage possible out of ALS chains. But this also means you have to "remember" the dual-link RCDs between any 2 adjacent ALSs as you develop the chain.

Cheers,
Paul

by **aran** » Mon Apr 06, 2009 2:59 pm

Paul, Hobiwan
First of all, at the risk of repitition, what fine structures those dual-linked ALSs are.
One observation :
If the D-L As are initially seen as in picture 2 ie
A=r2c2569
B=r138c4
giving {38927}{6827} (dual-links in bold)
then the original eliminations in picture 1 (which has a smaller base, with r8c4 excluded) do not occur "spontaneously" since the 8s in box 2 no longer see all of the 8s in set B. So they aren't eliminated immediately. Of course one gets there quickly since the placement of 6 in r8c4 (which does happen spontaneously) limits the 8s in B to r13c4.
Howver given a certain tendency not to "count" as "true" D-L A eliminations anything which arises from a placement, we have the somewhat counter-intuitive situation, that a larger base produces less "spontaneous" eliminations.

by **Allan Barker** » Wed Apr 08, 2009 6:23 pm

Paul,

PIsaacson wrote:the point is that the combination of the cells described in example 1 contains many potential eliminations beyond what can be discovered by just examining the end-point ALSs. Decomposition into sub-chains really squeezes the most mileage possible out of ALS chains.

Looking at the above logic diagram, I thought it might be useful to say something about the eliminations and assignments that show up, and maybe some that do not. One question might be, why do some diagrams not show the assignment of a candidate in a bi-value cell that has an elimination. The answer is based on the idea of logic scope.

Scope of Base / Cover Set Logic and Eliminations

For any base cover set logic:

The scope of the logic includes only the base and cover sets that are a part of logic, i.e., what you see.

The scope of constrained candidates is the group of all candidates in all strong (base) sets in the logic. This group of candidates is constrained by both the base and cover sets, which in turn determines eliminations and assignments.

The scope of possible eliminations and assignments caused by the constrained candidates includes all candidates in both the cover sets and base sets.

For example, if the logic causes the elimination of a candidate, and that candidate is a bi-value cell not in the scope of logic , then the elimination does not result in the assignment of the other candidate in the bi-value set.

The scope rules can also lead to the following subtle situation. Candidates that are in cover sets but not in bases can sometimes see each other. When they do, they could affect the logic of the constrained candidates in a way that causes an elimination somewhere else. This elimination is not a consequence of the primary constrained candidates, and is not counted.

When scope is defined this way, the logic will apply to any puzzle that has the same logic. Without the scope definition, this may not be true.

This definition of scope does allow the elimination or assignment of candidates in the base sets, but such eliminations or assignments are not necessarily cannibalistic.

..

by **ronk** » Wed Apr 08, 2009 6:48 pm

Allan Barker wrote:Scope of Base / Cover Set Logic and Eliminations

For any base cover set logic:

...

The scope of possible eliminations and assignments caused by the constrained candidates includes all candidates in both the cover sets and base sets.

For example, if the logic causes the elimination of a candidate, and that candidate is a bi-value cell not in the scope of logic , then the elimination does not result in the assignment of the other candidate in the bi-value set.

Nice definition Allan.

I think the "scope of eliminations" for true rank 0 logic should be limited as well. In brief, there should be no "extraneous" cover sets and the cover sets should be the "natural" cover sets.

Dang, I reckon I need to find an example for that to be clear.

by **PIsaacson** » Wed Apr 08, 2009 9:00 pm

Allan Barker wrote:The scope of possible eliminations and assignments caused by the constrained candidates includes all candidates in both the cover sets and base sets.

Dang! For a second I thought I understood scope, but then I had to go back and look at my first diagram again. To my dismay, the r8c4<>8 leaves a possible assignment and it's in the scope of the cover set logic and what I thought was the scope of possible eliminations and assignments.

Why isn't the assignment r8c4=6 present in diagram 1? Did I click or not click some special option?

by **ronk** » Wed Apr 08, 2009 9:58 pm

PIsaacson wrote:Why isn't the assignment r8c4=6 present in diagram 1?

Because the candidates of r8c4 weren't defined as a strong set, i.e. a member of the base set.

But IMO r2c9 shouldn't have been part of the base set either. Without r2c9, the logic set is minimal and is the essence of the move. Everything after that is just a cascade of singles and locked candidates. Allan Barker illustrated this minimal logic set here.

[edit: remove rogue parenthesis]

by **hobiwan** » Thu Apr 09, 2009 4:59 pm

Thanks to all of you for your continued interest. I am currently away from a decent internet line (plus my family has banned sudoku for the holidays...). I will try and catch up with you all as soon as I can.

Happy Easter to you all!

by **PIsaacson** » Sun Apr 12, 2009 10:37 am

Code: Select all: Hodoku ver 1.2 .6...52..4..1..65.....6..3....3...65.5........7.5.....681457.......2.517.2.9..846 .--------------------------.-------------------------.-----------------------. | B13789 6 B3789 | A78 34-7-8-9 5 | 2 A789 14-8-9 | | 4 B39 2-378-9 | 1 3789 2389 | 6 5 8-9 | | -12578-9 B19 2578-9 | 278 6 2489 | 147-9 3 148-9 | :--------------------------+-------------------------+-----------------------: | 1289 149 2489 | 3 14789 12489 | 1479 6 5 | | 12389 5 234689 | 2678 14789 124689 | 13479 278-9 123489 | | 12389 7 234689 | 5 1489 124689 | 1349 28-9 123489 | :--------------------------+-------------------------+-----------------------: | 6 8 1 | 4 5 7 | 39 2-9 239 | | 39 349 349 | 68 2 68 | 5 1 7 | | 57 2 57 | 9 13 13 | 8 4 6 | '--------------------------'-------------------------'-----------------------' Almost Locked Set XZ-Rule: A=r1c48 {789}, B=r1c13,r23c2 {13789}, X=7,8, Z=7,8 => r1c59<>8, r1c5<>7, r1c59,r2c39,r3c1379,r567c8<>9, r3c1<>1, r2c3<>3

Code: Select all: ALS engine + base/cover set analysis .6...52..4..1..65.....6..3....3...65.5........7.5.....681457.......2.517.2.9..846 puzzle 1 hobiwan1.pm 13789 6 3789 |78 34789 5 |2 789 1489 4 39 23789 |1 3789 2389 |6 5 89 125789 19 25789 |278 6 2489 |1479 3 1489 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 1289 149 2489 |3 14789 12489 |1479 6 5 12389 5 234689 |2678 14789 124689 |13479 2789 123489 12389 7 234689 |5 1489 124689 |1349 289 123489 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 6 8 1 |4 5 7 |39 29 239 39 349 349 |68 2 68 |5 1 7 57 2 57 |9 13 13 |8 4 6 do_alschains - graph contains 182 vertices and 702 edges 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 -- cannibalistic but legal do_alschains - reducing r1c3.<3789> by <9> dual -- cannibalistic but legal 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 r4c2.<149> by <9> base/cover -- additional elimination beyond ALS dual-link rules do_alschains - reducing r8c2.<349> by <9> base/cover -- additional elimination beyond ALS dual-link rules do_alschains - cover rn(17, 18, 19) cn(29) bn(11, 13) -- cover set for the above 2 eliminations + base set of all the ALS cells do_alschains - alsc[2x5/5] r1c48.<n789> -78- b1x1358.<n13789>

Code: Select all: Xsudo ver 0.80 060005200400100650000060030000300065050000000070500000681457000000020517020900846 +-------------------------+----------------------+------------------------+ | (1378-9) 6 (378-9) | (78) 34-789 5 | 2 (+9-78) 14-89 | | 4 (39) 278-39 | 1 3789 2389 | 6 5 8-9 | | 2578-19 (19) 2578-9 | 278 6 2489 | 147-9 3 148-9 | +-------------------------+----------------------+------------------------+ | 1289 14-9 2489 | 3 14789 12489 | 1479 6 5 | | 12389 5 234689 | 2678 14789 124689 | 13479 278-9 123489 | | 12389 7 234689 | 5 1489 124689 | 1349 28-9 123489 | +-------------------------+----------------------+------------------------+ | 6 8 1 | 4 5 7 | 39 2-9 239 | | 39 34-9 349 | 68 2 68 | 5 1 7 | | 57 2 57 | 9 13 13 | 8 4 6 | +-------------------------+----------------------+------------------------+ 1 r1 18 Nodes, Raw Rank = 3 (linksets - sets) 6 Sets = {1N1348 2N2 3N2} 9 Links = {789r1 9c28 139b1 9b3} 22 Eliminations, 1 Assignments --> r1c1359<>9, r3c1379<>9, r1c589<>8, r567c8<>9, r1c58<>7, r2c39<>9, r48c2<>9, r2c3<>3, r3c1<>1, r1c8=9

I modified my ALS engine to use your new RCD algorithm and checked against example 1 - royle17 #2231 from the new 48010 collection. Interestingly, both HoDoKu and my ALS engine found the exact same dual-link ALS which then led to carnage with the massive amount of eliminations it produced. By the time my ALS engine got around to locating the ALS chain indicated in example 1, all of the potential eliminations had already been covered by prior found ALS chains. I have subsequently tested against various large collections with no case of invalid chains or invalid eliminations.

Regarding the differences in eliminations: 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. The 9s in ALS B that are peers of the 9s in ALS A are candidates for elimination. I checked using Xsudo and it agrees with the 2 cannibalistic eliminations. 2 additional eliminations that my ALS engine found (tagged as base/cover) are due to new code that attempts to emulate Allan Barker's set/link-set logic. I missed the assignment of r1c8=9 => r1c8<>78, but I'm working on that...

Cheers,
Paul

by **ronk** » Sun Apr 12, 2009 1:17 pm

Paul, as before you are not using the minimal logic set, which doesn't require r1c8 in the base set. Without r1c8, there is no assignment in xsudo.

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

by **aran** » Sun Apr 12, 2009 4:38 pm

Paul
Three of the linksets don't provide any additional cover : 9b1 9b3 9c8
ie 9r1 and 9c2 have already done all the work.
So there is no guarantee of an additional "truth" in any of them.
I don't therefore think it could be construed as a rank 3 structure in any case.
The given structure certainly has rank 0 with 6 set/6 linkset.
This provides 14 eliminations ie all except those in box 3 (other than 89 r1c9, which are part of the 14 elims).
Including the cannibalized 9s at r1c13.
All of that leaves only one position for 9 in r1 : r1c8 which then generates the remaining elims to make 22.
I'm interested to know what your logic was.

by **Allan Barker** » Sun Apr 12, 2009 6:43 pm

PIsaacson wrote:Regarding the differences in eliminations: 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. The 9s in ALS B that are peers of the 9s in ALS A are candidates for elimination. I checked using Xsudo and it agrees with the 2 cannibalistic eliminations. 2 additional eliminations that my ALS engine found (tagged as base/cover) are due to new code that attempts to emulate Allan Barker's set/link-set logic. I missed the assignment of r1c8=9 => r1c8<>78, but I'm working on that...

...but, you got the eliminations in c2! In simplest terms, the logic proceeds in three steps:

A. als:(13789){r1c13,r23c2}-(78)r1c4 => 10 Elim: r1c589<>8, r1c58<>7, r3c13<>9, r2c3<>39, r3c1<>1

B. r1c8=9 => 10 Elim: r1c1359<>9, r567c8<>9, r3c79<>9, r2c9<>9

C. als:(1378)r1c134-78- als(139)r23c2 => 2 Elim: rr48c2<>9

The eliminations in r1c1359<>9 are all from the assignment in B. The eliminations in C, r48c2<>9, come after eliminating 9r1c13 in step B, which allows column set 9c2 to become a cover set.

In this case, Xsudo is summing the logical steps brought about by of the addition of r1c8. Try adding r2c9, r7c8, r6c8, and r5c8 in that order, each new cell makes a new assignment and more eliminations.

by **PIsaacson** » Sun Apr 12, 2009 9:41 pm

Let's see if I can cover all the bases here without hi-jacking this thread too much:

Ron,

I had to "tune" my options to match HoDoKu's primary ALS. I deliberately skipped bi-values with the "-M3 -A9" option to only consider ALSs with 3 or more candidate values (ie 2 - 8 cells). Without the "-M3" the ALS engine found:

Code: Select all: 150> sudoku -bvwe -Xprsa -A9 -M2 -B2 -P -T-1 -S hobiwan1.pm hobiwan1.sud Puzzle: .6...52..4..1..65.....6..3....3...65.5........7.5.....681457.......2.517.2.9..846 puzzle 1 hobiwan1.sud 13789 6 3789 |78 34789 5 |2 789 1489 4 39 23789 |1 3789 2389 |6 5 89 125789 19 25789 |278 6 2489 |1479 3 1489 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 1289 149 2489 |3 14789 12489 |1479 6 5 12389 5 234689 |2678 14789 124689 |13479 2789 123489 12389 7 234689 |5 1489 124689 |1349 289 123489 --------- --------- ---------+--------- --------- ---------+--------- --------- --------- 6 8 1 |4 5 7 |39 29 239 39 349 349 |68 2 68 |5 1 7 57 2 57 |9 13 13 |8 4 6 do_alschains - graph contains 195 vertices and 864 edges 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 r1c8.<789> by <7> dual do_alschains - reducing r1c5.<3489> by <8> dual do_alschains - reducing r1c8.<89> by <8> dual do_alschains - reducing r1c9.<1489> by <8> dual do_alschains - reducing r2c3.<2789> by <9> dual do_alschains - reducing r3c1.<25789> by <9> dual do_alschains - reducing r3c3.<25789> by <9> dual do_alschains - als[2x5/5] r1c4.<n78> -78- b1x1358.<n13789>

That is your "minimalist" ALS, and it generates a nice set of 10 eliminations using just dual-link rules. My base/cover logic didn't find any additional missed eliminations and Xsudo finds the exact same 10 with:

Code: Select all: Almo 15 Nodes, Raw Rank = 0 (linksets - sets) 5 Sets = {1N134 2N2 3N2} 5 Links = {78r1 139b1} 10 Eliminations, 0 Assignments --> r1c589<>8, r1c58<>7, r3c13<>9, r2c3<>39, r3c1<>1

Aran,

Let's see if I can explain what I'm doing as simply as possible:

1) I use my ALS engine to find an interesting target set of cells - in this case a dual-linked ALS pair.
2) My ALS engine listed the 1st 18 eliminations based on standard dual-linked eliminations rules plus allowing for cannibalism.
3) Using those 6 cells as the base set, I then used DLX to generate all possible exact cover solutions to find cover sets. During this phase, the base/cover logic found two additional eliminations based on the cover set (789r1, 9c2, 13b1) using Xsudo notation. This equates to the line "do_alschains - cover rn(17, 18, 19) cn(29) bn(11, 13)".
4) I then enter the same set of cells as the base set in Xsudo and click the "Xsudo -> Draw Logic as Sets, Auto" option. This produced the 22 eliminations plus 1 assignment.

Allan,

Thanks for explaining how Xsudo sums the logical steps. I haven't tried decomposing the group of base candidates into various combinations to see which are contributing to the logic/solution. Looks like more coding...

FYI: I've uploaded the *.sud positions generated from the ALS engine using the 1st three example PMs and the following command:
sudoku -bvw -Xprsa -A9 -B2 -S -T-1 -P hobiwan.pm hobiwan.sud
download and rename to hobiwan.sud: http://pisaacson.fileave.com/Bernhard/hobiwan.sud.bin

by **Allan Barker** » Mon Apr 13, 2009 7:56 am

Aran,

Looking over our almost simultaneous analyses:

Aran: Three of the linksets don't provide any additional cover : 9b1 9b3 9c8 ie 9r1 and 9c2 have already done all the work.

From my post, I might have said,

Allan:Three of the linksets don't provide any additional cover : 9c2 9b3 9c8 ie 9r1 and 9b1 have already done all the work.

So there are two (six cell) rank 0 cover sets with slightly different results. Combined, the 7 cover sets produce more eliminations.

Thus here 6 + 6 = 7, straight from my wife's accounting principles.

.

by **PIsaacson** » Mon Apr 13, 2009 11:06 am

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

I just realized that perhaps I didn't make this clear before. My ALS engine is not a solver. It is just a tool to be used to examine various ALS structures including ALS chains and Death Blossoms. As such, it exhaustively finds ALL possible ALS structures within the parameters specified with the command line option flags. It normally only reports those that produce eliminations, but with the "-V" flag you can examine the entire set.

The 1st example with the options "sudoku -bvwV -Xprsa -M2 -A9 -B4 -P hobiwan1.pm > log" followed by "grep '\- als.*\[' log | wc" shows that 74957 ALS chains were generated and examined for eliminations. The fact that the testbed actually solves some puzzles should not be taken to mean that this is a solver. Solutions are possible from leaving in elementary methods for bring puzzles to a known quasi-SSTS position, but solutions are not the goal of the ALS engine. The goal is to find "interesting" examples, generate the corresponding sud file, and then use Xsudo for analysis and those lovely 3d graphs!

As a manual solver... Unfortunately, I'm (arguably) a better sudoku programmer than a player. If I could find just a tiny fraction of the ALS structures that my engine generates, I would consider myself fortunate. As DonM said quoting Marlon Brando (and I love this line) "I coulda been a contender. I coulda been somebody. Instead of a bum, which is what I am. Let's face it..."

Cheers,
Paul

The New Sudoku Players' Forum

Restricted Common Adjacency Rules