Susets for Subsets

As we went through the phases of Sysudoku Basic, we noted how the placement rules of Sudoku imply that subsets of n cells in a unit can be reserved for n numbers, restricting placement of other numbers. Two naked triples and a naked pair brought down the Wayne Gould puzzle used to demonstrate line marking. Subsets are a math problem lurking in several closets along the innocent looking Sudoku main hall, the restriction that every line and box have one true candidate of each number 1 – 9.

A subset is a locked set, a set of n numbers confined to n cells. Candidates of these numbers are locked into these sets, and candidates of all other numbers are locked out. Clues are locked sets. The unlocked cells of properly line marked units, box or line, are also locked sets. A subset is an answer to a riddle posed by unlocked cells: Is there a locked set that is a subset of the unlocked set? That is to say, n numbers confined to n cells, where n is less than the number of unlocked cells.

A remarkable thing is that this problem occurs in other locked set situations in Sudoku, including almost locked sets(ALS) and regular, finned and kraken fish.  In fact, Sudoku solving computer programs use a simple method of set manipulation to find locked sets in these contexts.  This page explains a humanly practical version of this method. Here it is called the Suset method.

First, let’s agree, that in most cases, a systematic search for locked sets isn’t necessary.  We notice that the same candidates in several cells, and then realize that we have a naked pair, or triple, or even a quad. Then removals bring out what was a hidden counterpart.  Or we notice one or two candidates having only the one or two places to go, a hidden single or pair.

When a complex case leaves you feeling you might have missed one, it’s time to focus your thoughts with Susets.

Let’s play mathematician and take the subset detection problem of column c4 in Fiendish 25 out of its Sudoku context. Here are the free cells of the column, as a set of number strings:

26, 236, 3469, 267, 27, 2349.

In the Suset method we do a little construction on scratch paper:

First we number the unlocked cells, and list the candidatesin each cell by number, this way:

1/26, 2/236, 3/3469, 4/267, 5/27, 6/2349.

This now is a list of susets, each one being a combination of original sets on the left, and the members of each combination on the right. The combinations on both left and right are set unions.  For example, we can merge the first two susets on the list into another suset, 12/236. This suset describes 3 numbers contained in 2 sets. To find n sets containing n numbers, with n less than 6, a computer program could just combine all susets to cover all combinations, doing all combinations of the original susets.

Humans, however, can better handle a plan to increase sets while keeping numbers as few as possible. So we would start with sets 1, and 5, and the suset 15/267, then realize we can add set 4 “for free”, increasing the number of sets, without increasing numbers, to have 145/267, the suset of the naked triple.

A similar suset strategy applies to the harder problem of detecting hidden subsets. Hiddens are harder, because we have to look at all the sets, not just the ones with fewest candidates. What’s fewest with hiddens? Locations. Hidden subsets are identified by the fewest locations.

To start, write out susets with the cell locations of each number, among the original cells:

2/12456, 3/236, 4/36, 6/1234, 7/45, 9/36

The numbers with the fewest locations are 4, 7, and 9, but now we see that 4 and 9 can join 3 for a hidden triple 349.

Yes, there’s not much demand for hidden subset algorithms if they can be found with naked subsets, but this does hint at the flexibility of susets. In my October 2011 post on susets for subsets, I had some real sticklers. The original grid cells are displayed there, in my late but unlamented Brush Script font, but here I’ll transpose them into numbers. See what you can do with these, and go to the post for answers. Get both the naked and the hidden subset in each case.

A box from Sheldon’s Master Class 40 reads

1/235, 2/256, 3/25, 4/38, 5/478, 6/28, 7/2469, 8/24879.

Which is scarcer, cells or locations?

A column from another Fiendish reads

1/378, 2/78, 3/14, 4/38, 5/14378.

If you actually like to do this, the Suset post has two horrifying examples from a revered but frozen website, the sudocue guide. These are unraveled with a more systematic version of the suset method. This full nelson, labeled suset enumeration, is deployed in several places in the blog.

Whenever you want to tackle harder Sudoku’s, or just want to decipher the reviews on the toughest collections, begin the Sysudoku Advanced series, in the Guide as they become available, and in the posts if not.

Advertisements