Hidden triples rule question

Phil1 · Posted: Sun Dec 31, 2006 5:08 am Post subject: Hidden triples rule question

Thank you for reading this.

I’m trying to programme the hidden triple rule based on the code that I have developed for the hidden pairs rule. The hidden pairs rule was fairly easily solved by looking for a pair of numbers that only occur twice and only occur in the same two cells. My routine works but it’s probably not very efficient and may not lead to solving the hidden triples rule.

Say I know that the hidden triple is 3, 6 and 7. This means that I could be looking for cells that contain (3,6) (3,7) (6,7) or (3, 6, 7). It could be that one cell contains (3,6) a second cell could contain (3,7) and the third cell could contains (6,7). What I’m getting at is that three cells don’t necessarily need to contain all three numbers.

Counting the number of occurrences of numbers (which works for hidden pairs) didn’t lead me anywhere and looking for all possible sets and subsets looked promising but I think that there must be an easier method of discovering the hidden triples.

I’ve spent a lot of time on trying to solve this problem and searching the Internet for a suitable algorithm without success. Can anyone put me on the right track?

Regards,
Phil.

Ruud · Site Admin

Hi Phil,

check these topics on generic naked/hidden subset searching:

http://www.setbb.com/sudoku/viewtopic.php?t=231
http://www.setbb.com/sudoku/viewtopic.php?t=273

Ruud.
_________________
Meet me at sudocue.net

MCondron · Posted: Tue Jan 09, 2007 3:57 am Post subject:

What I do to find all hidden subsets is examine the house in question (a certain row/col/box) for cells that do *not* contain a certain pair, triplet, etc. If, for example, there are 6 cells that do not have a certain set of 3 digits in a line, then I know those 3 digits must be in the remaining 3 cells, ergo a hidden triplet. I don't know if this is faster than any other way, but I think it's fairly compact and easy to understand.

In detail:

First of all, I represent the grid as a 9x9 array of bit fields with each bit representing a possible value for the cell. I also have another 9x9 array which is 0 if the cell is empty and holds the cell's value if the cells' value is known.

1. Scan the house (row/col/box) under examination and make a list of all empty cells. If this list shorter than the size you're looking for, then stop (i.e. you aren't going to find a hidden quad if there are only 3 empty cells).

2. Iterate steps 2 - 4 over all permutations of numbers indexing the list from (1). How to do that is a whole task in itself, but the idea is to make an array of numbers and a little loop to count like this: If you find, say, 5 empty cells and you're looking for triplets -- 012, 013, 014, 123, 124, 234. You want to cover all possible triplets from that list of 5.

3. Scan over the house in question, looking at all the bitfields of the cells which are not known and are not in that permutation of the list of empty cells. This essentially picks a certain triplet in the house and scans its negative or complement in that house.

3a. Specifically: initialize a bit field (call it f) to all 1's. For each cell in the house that is not in the permutation from (2), perform a logical AND of f with the logical NOT of that cell's bitfield. The end result will be that f has bits set for all values that are not possible outside the n-tuple from (2).

4. If f is zero, move on to the next permutation (2)

5. If the number of bits set in f is less than the size of the set you're looking for, move on to the next permutation (2). [You could write a loop to count the bits in f; I made an array that has the answer for all 512 9-bit combinations that will occur in 9x9 sudoku so I can look it up quickly.]

6. If you've found a hidden single (exactly one bit set in f), you can set the value of that cell to its now-known value and stop.

7. If you find more than a single, you have to search the rest of the house under examination to see if your discovery results in any possible candidates being eliminated and clear them if so.