Naked Subsets

Naked Subsets is the next most difficult strategy. Naked subsets come in a few varieties: Naked Pairs, Naked Triples, and Naked Quads. All three use the same logic, but Pairs is typically easier to use and spot than Triples and Quads.

fig7The idea behind a naked subset is that because in a row, block, or column x cells share a combined candidate set of size x, all candidates in that subset may not occur elsewhere in the row, block, or column. For instance, in Figure 7, the candidates 5 and 7 occur in the top-left and bottom-center cells. This means no other cells in the block may contain a 5 or a 7 in their candidate set, as between these two cells, 5 and 7 will be used. 7 can be removed as a candidate from the top-center cell and the middle-left cell. This example also depicts a naked triple, though it may be difficult to see. To have a hidden triple, one must have three cells that share three candidates. It is not necessary for all three cells to have all three candidates. All that is needed is a candidate set of size 3 when combining the candidate sets of three cells and removing duplicates. Adding the candidate sets of the top-right, middle-right, and bottom left cells one gets {1,2,3} + {1,2} + {1,3) = {1,2,2,3,3}, and removing duplicates, simply {1,2,3}. So between three cells, there are exactly three candidates, so it follows that those candidates must be used between those three cells and thus cannot be in any other cells in the block. 1 can be removed as a candidate from the middle-left cell.

Each size of naked subset should be represented as its own separate strategy, but these strategies will all share the same common framework. First, the programmed algorithm should loop through all columns, rows, and blocks individually. While looking at each row, column, or block, first all possible subsets of a given size sharing that same number of candidates must be found. To accomplish this, one can find all possible combinations of x empty cells, and then check to see which of these combinations have a combined candidate set with x unique candidates. With all of these combinations found, the program may then proceed to check if these naked subsets of size x allow for any candidate exclusion to take place. If no candidate exclusion ever takes place, then it is onward and upward to the next strategy.

Posted in Sudoku Solving Strategies and Techniques at April 26th, 2009. Trackback URI: trackback

No Responses to “Naked Subsets”

Comments are closed.