The New Sudoku Players' Forum

[ronk]

Please explain how to use the ALS xz-rule on

Almost Locked Set: xz-rule with A=2 cells: r3c17, r12c8|r3c9 => r2c7<>8

to obtain r12c9<>9.

I can't. Sorry, I redefined the sets without saying so.

I can do it if I set up the sets as

A={r3c17, r2c8}, B = {r1c8, r3c9} with the restricted common as x = 6 and the other common as z = 9.

That works, but I recommend always keeping all cells of one unit in one set, i.e., A = {r3c1} = {56} and B = {r12c8,r3c79} = {45689}.

A = {r3c179} = {45689} and B = {r12c8} = {489} works too as a triply-weakly-linked AALS and ALS, but that's another discussion I think.

[re'born]

Please explain how to use the ALS xz-rule on

Almost Locked Set: xz-rule with A=2 cells: r3c17, r12c8|r3c9 => r2c7<>8

to obtain r12c9<>9.

I can't. Sorry, I redefined the sets without saying so.

I think this helps to show the value of using the subset principle. Before your comment, I had not considered redefining the sets to make the additional exclusions. With the subset principle, you don't even have to differentiate between the two almost locked sets, just make them one big locked set and then all of the deductions will follow with little additional work.

I have a question for Mike and the other programmers. I understand the theory of ALS and if given the sets, I can make the deductions. But left to my own devices, I doubt I would have the patience to look for them, since I can't figure out how to do it intelligently. Do your algorithms use a brute force approach, say compiling a list of all ALS's and then checking the rules against them, or do they use shortcuts that are human implementable (is "implementable" a real word?)

I'm sorry that I have pulled the conversation so far off topic. I have some other questions, and if I can't resolve them myself I will create a new topic in the appropriate forum.

[ronk]

I think this helps to show the value of using the subset principle. Before your comment, I had not considered redefining the sets to make the additional exclusions. With the subset principle, you don't even have to differentiate between the two almost locked sets, just make them one big locked set and then all of the deductions will follow with little additional work.

I have two problems with the "subset principle". First, it's a principle in search of a technique. IOW the principle lacks a practical algorithm for finding "one big locked set." A chain of almost-locked-sets is the best we have right now AFAIK. That being the case, we might as well make the deductions based on the ALSs too.

Second, the term "subset principle" isn't very descriptive.

[re'born]

...the (subset) principle lacks a practical algorithm for finding "one big locked set." A chain of almost-locked-sets is the best we have right now AFAIK.

I get what you are saying, though I don't have a practical algorithm yet for finding almost-locked-sets either. My point is that once you find the almost-locked-sets, instead of applying the xz-rule and then readjusting the sets and applying the xz-rule again and then possible readjusting the sets and using a VWXYZ-wing, etc., that one applies the subset principle immediately and get all of the deductions at once.

we might as well make the deductions based on the ALSs too.

Mike Barker's solver used the same cells in 4 different ways to make deductions. If the goal is to aid human solving, why not use those cells in just 1 way to make those same deductions?

Second, the term "subset principle" isn't very descriptive.

It is probably fair to point out that aeb has used the phrases subset principle, extended subset principle and subset counting (note that the second is actually a generalization of the first). Of these, I think the last is the most descriptive. I certainly don't feel comfortable changing the name of someone else's work, but I suppose you were being mostly facetious anyway.

[ronk]

My point is that once you find the almost-locked-sets, instead of applying the xz-rule and then readjusting the sets and applying the xz-rule again and then possible readjusting the sets and using a VWXYZ-wing, etc., that one applies the subset principle immediately and get all of the deductions at once.
.....................
Mike Barker's solver used the same cells in 4 different ways to make deductions. If the goal is to aid human solving, why not use those cells in just 1 way to make those same deductions?

I believe -- for the ALS xz-rule and as stated in my previous post -- that if either set A or set B includes all of the elements in one unit (of the union of sets A and B), there will be no need to "readjust the sets". However, I'm prepared to readjust (pun intended) my belief when, and if, someone illustrates an exception.

Second, the term "subset principle" isn't very descriptive.

... but I suppose you were being mostly facetious anyway.

I was ... and I should have added that the prefix "sub" is quite useless too.

[Mike Barker]

First, thanks to both of you for the comments. In trying to think of how to implement both subset counting with a locked set and the mutual exclusion rule they seem to be very similar. The puzzle at the point of discussion is

Code: Select all

+------------------+-----------------------+-----------------+
|   126    8  1269 |    4679    679      5 |   3  #49  -14679|
|  1356  139     4 |    6789  36789      2 |-578  #89  -1679 |
|   *56   39     7 |     489      1    349 | #58    2   #469 |
+------------------+-----------------------+-----------------+
|   247    5     3 |    1279    279    179 |  49    6      8 |
|   124    6    12 |       5    239      8 |  49    7     23 |
|     9   27     8 |      67      4    367 |   1    5     23 |
+------------------+-----------------------+-----------------+
|    28    4   129 |   12789      5    179 |   6    3     79 |
|   167  179   169 |       3    689  14679 |   2  489      5 |
|  2368  237     5 |  246789  26789   4679 |  78    1    479 |
+------------------+-----------------------+-----------------+

With subset counting with a locked set, any candidate in a cell not in the set which can eliminate all occurances of the digit within the set can be eliminated, in this case the 4, 8 and 9's in box 3. To be a locked set, all occurances of a candidate within the set must be visible to all other occurances of the candidate within the set. This implies that it has at least two restricted commons. The mutual exclusion rule can then apply with the added exclusions it might provide (in this case none). I'm not sure in general how the performance of the two compare.

As far as how I implemented the ALS, yes it is by brute force, however like Ron suggested, the idea is to find a bivalue cell first which is human implementable. I'll have to investigate why it didn't find it in the above case. The idea for the solver is to show eliminations not only for what I can do, but also to show what can be done with the idea that I could improve. I agree that I've taken it to the limit. I will probably never find a 6 cell ALS locked with a 6 cell ALS, but at least I know thats what I need to do. The key is the order in which the solver finds solutions going from the simple to the more complex. At one point to check out the algorithm I had the solver solve everything as nice loops - not something I plan to do too often by hand!

[ronk]

The puzzle at the point of discussion is

Code: Select all

+------------------+-----------------------+-----------------+
|   126    8  1269 |    4679    679      5 |   3  #49  -14679|
|  1356  139     4 |    6789  36789      2 |-578  #89  -1679 |
|   *56   39     7 |   -4689      1 -34569 | #58    2   #469 |
+------------------+-----------------------+-----------------+
|   247    5     3 |    1279    279    179 |  49    6      8 |
|   124    6    12 |       5    239      8 |  49    7     23 |
|     9   27     8 |      67      4    367 |   1    5     23 |
+------------------+-----------------------+-----------------+
|    28    4   129 |   12789      5    179 |   6    3     79 |
|   167  179   169 |       3    689  14679 |   2  489      5 |
|  2368  237     5 |  246789  26789   4679 |  78    1    479 |
+------------------+-----------------------+-----------------+

I think it's a bit earlier than that, with candidates 5 and 6 still in r3c4 and r3c6 ... as I added above.

The mutual exclusion rule can then apply with the added exclusions it might provide (in this case none).

I count 7 exclusions. How do come up with none?

I'm not sure in general how the performance of the two compare.

When multiply-linked sets are recognized for the ALS xz-rule, the two approaches are equivalent IMO.

Ron

P.S. I went through all 50 solution steps you posted and I'm quite impressed ... even a bit envious. That's an extremely difficult puzzle IMO, and your solver used logical steps all the way. I do have a few suggestions for your "solver log", however. If you don't mind hearing them, let me know.

[Mike Barker]

I think the reason I missed the eliminations is that I only have xz and xy rules implemented. I need to implement the mutual exclusion rule as well (something I hope to correct soon). As far as suggestions - always. As you've probably surmised from other posts - I'm here to learn.