The New Sudoku Players' Forum

[re'born]

After reading Bennys post on almost locked sets, http://forum.enjoysudoku.com/viewtopic.php?t=2510&highlight=locked+sets, it occured to me that the key point is that two disjoint locked sets cannot have a restricted common candidate. Should we not then be able to state a corresponding set of rules for almost hidden sets. Let me define some terms and state for almost hidden sets a rule which would correspond to the xz-rule of almost locked sets.

Let A be a subset of a group (a row, block or column). The complement of A in its group are the cells in the group not in A. It will be denoted by c(A). There is already some ambiguity here as it is possible for A to be a subset of multiple groups. In this case one should be more explicit and write, for instance, c(A,r7) or c(A,b4). When the group we are talking about is unique or clear from the situation, we can suppress the extra information.

A candidate in A is called a hidden candidate if it does not occur in c(A). A hidden set is then precisely a set A which contains n cells and n hidden candidates. An almost hidden set will be a set A which contains n cells and n-1 hidden candidates.

Let A and B be two disjoint almost hidden sets and let x be a common candidate. Then x is a hidden common candidate if it is a hidden candidate for both A and B. A restricted hidden common candidate is a restricted common candidate which is also a hidden common candidate.

xz-rule: Let A and B be two disjoint almost hidden sets and let x be a restriced hidden common candidate. Let z be a common candidate of A and B which is not a hidden candidate for either A or B. Then any cell which can see all of the z candidates in c(A) and c(B) cannot be z.

Proof: Such a z would eliminate all z's in c(A) and c(B). Hence z would be a hidden candidate for both A and B. They would now form hidden sets (and hence locked sets) with a restricted common candidate, a contradiction.

My questions are whether any deductions made from this theorem could be seen (more easily, perhaps) by another rule and whether anyone can come up with a useful example. As a mathematician, I am trained to work out theory and let the engineers come up with applications, so I am not much use in finding examples.

Thanks in advance for your expertise and time.

[aeb]

After reading Bennys post on almost locked sets, it occured to me that the key point is that two disjoint locked sets cannot have a restricted common candidate.

In my view the key point is that a set of size n has n digits. In reality no two disjoint sets are used in Bennys post but just their union as a single set. (But if the set is not contained in a single row/column/box then digits must be counted with multiplicity.) See also http://forum.enjoysudoku.com/viewtopic.php?p=20633 and http://homepages.cwi.nl/~aeb/games/sudoku/solving11.html.
(Your almost hidden sets are also a special case.)

[re'born]

aeb,

Thanks for the response. I've tried to digest your extended subset principle and I understand how it works for almost locked sets. I'm sure that it must explain almost hidden sets as well, but I am having trouble applying it nonetheless. My issue seems to be in putting bounds on sum of the n_d (using your notation). Without this I can't find the \delta (again, your notation) and so I'm not left with much.

Could you elaborate a little for me?

Also, to make sure that I understand, is your extended subset principle the same idea that Bennys is alluding to in http://forum.enjoysudoku.com/viewtopic.php?t=2725&highlight=multiplicity?

Thanks again.

[aeb]

Also, to make sure that I understand, is your extended subset principle the same idea that Bennys is alluding to in http://forum.enjoysudoku.com/viewtopic.php?t=2725&highlight=multiplicity?

Let me answer this part first. Yes, this is somewhat related, considers only a single set, and the word multiplicity occurs in the title, that is the good part. On the other hand, the reasoning seems more like: for a naked subset we really need that each digit can occur only once, but in this particular case if a digit occurs more than once there is a separate reason why the conclusion still holds. I do not quite see the extended subset principle formulated there yet. (And it is not a special case since this additional argument is required.)
On the other hand, what Carcul does in http://forum.enjoysudoku.com/viewtopic.php?t=2846 is really a special case.

[re'born]

aeb,

Let me see if I am getting this straight now. In Bennys' example, (as usual using your notation), |S| = 6, n_1 = 1, n_2 = 2, n_3 = 1, n_4 = 1, n_5 = 2, n_6 = 1. Thus, \sum n_d = 8 and hence \delta = 2. Then (4,1)5 would imply that the number of 5's in S is 0. Since 0 is not less than 0 = n_5 - \delta, we can not apply the extended subset principle.

Is this correct? I had misread the principle the first time to read less than or equal rather than the strict inequality. Naturally, the strictness is required. Thanks for the help in understanding your very elegant approach. I'm still not certain how to see almost hidden sets as a special case. I'll keep looking at it, but any help would be appreciated.

[aeb]

aeb,

Let me see if I am getting this straight now. In Bennys' example, (as usual using your notation), |S| = 6, n_1 = 1, n_2 = 2, n_3 = 1, n_4 = 1, n_5 = 2, n_6 = 1. Thus, \sum n_d = 8 and hence \delta = 2. Then (4,1)5 would imply that the number of 5's in S is 0. Since 0 is not less than 0 = n_5 - \delta, we can not apply the extended subset principle.

Is this correct? I had misread the principle the first time to read less than or equal rather than the strict inequality. Naturally, the strictness is required. Thanks for the help in understanding your very elegant approach. I'm still not certain how to see almost hidden sets as a special case. I'll keep looking at it, but any help would be appreciated.

Yes, entirely correct.

Concerning the almost hidden sets, these are just almost locked sets in disguise.
A hidden set is by definition the complement of a naked set, so one can translate your description into one for A'=c(A) and B'=c(B). You write

Let A and B be two disjoint almost hidden sets and let x be a restriced hidden common candidate. Let z be a common candidate of A and B which is not a hidden candidate for either A or B. Then any cell which can see all of the z candidates in c(A) and c(B) cannot be z.

Here you need not assume that z is a common candidate of A and B.
Taking complements this becomes (after forgetting the word "disjoint", and using that "candidate for A'" is equivalent to "not hidden for A"):
Let A' and B' be two almost locked sets such that their union has |A'|+|B'|+1 candidates, and let z be a candidate of multiplicity 2 in this union. Then a cell outside this union that can see all z-candidates inside cannot be z itself. (Here "outside" is not important, since a cell cannot see itself.)
You see that your almost hidden sets are nearly equivalent to almost locked sets, but there is a small detail, namely that complements of disjoint sets need not be disjoint. Therefore one should forget the "disjoint" and work with multiplicities. Now both almost locked sets and almost hidden sets are a special case.

[re'born]

Ahh, I see now that which I wasn't seeing. A is an almost hidden set if and only if c(A) = A' is an almost locked set. This is nice because if you can find one, you have the other automatically. This answers both of the questions posed in the title:

Redundant: Yes. The xz-rule for almost hidden sets is a special case of the extended subset principle and equivalent (after possibly a little tweaking to the definitions) to the xz-rule of almost locked sets.

Useful: Yes, insofar as almost locked sets are useful.

At least I get another entry into the journal of irrelevant techniques.

Thanks for the help, aeb.

Adam

P.S. I really enjoyed working through your website. However, there were, on rare occasions, portions where the explanation is unclear. For instance, in the statement of the extended subset principle it would have made more sense to me if you had introduced notation for the actual number of d's in S, say m_d, helping to emphasize that n_d is not just found by counting up the cells in S which have d as a possibility. In this case, one would have the equations:

|S| = \sum_d m_d

|S| + \delta = \sum_d n_d

Then \sum_d (n_d - m_d) = \delta and it now becomes straightforward to check that if m_e < n_e - \delta for some e, then we get a contradiction. Naturally, one does not know the actual values of the m_d in general (at least until that portion of the puzzle is solved) but it makes the background work (i.e., proving that the principle is sound) so much more tractable.

Of course, if I were you, I'd be saying either, "hey you figured it out didn't you," or "this should be clear without the extra burdensome notation, dunderhead."

[aeb]

P.S. I really enjoyed working through your website. However, ...
"this should be clear without the extra burdensome notation"

Thanks! Yes, I tend to err on the concise side.