Say you’ve gotten to the point in your Sudoku where the obvious numbers have been placed. The next step would be to look for patterns that allow you to narrow down your possibilities. For example, say that you have the following possibilities matrix:

`poss_in = { [], [2 5 6], [2 5], [], [7 8 9], [], [7 8], [2 5], [7 8] }`

```% Subset Update
%
%   This function searches for subsets of repeated numbers within the
%   possibility matrix. If two sets of the same nummbers are found, then
%   those two numbers can be removed from the possibility matrix.
function poss_out = subsetUpdate(puzz_in, poss_in)
poss = reshape(poss_in, 9, 1);
[num_rows num_cols] = size(puzz_in);

unique_poss = cell(1);
unique_cntr = ones(1);
n = 1;

% Count the number of unique sets
for ii = 1:9
if isempty(poss_in{ii});
continue
end

if n == 1
unique_poss{n} = poss_in{ii};
n = n + 1;
continue
end

found = 0;
for nn = 1:numel(unique_poss)
if numel(intersect(unique_poss{nn}, poss_in{ii})) == ...
numel(unique_poss{nn})

unique_cntr(nn) = unique_cntr(nn) + 1;
found = 1;
end
end

if ~found
temp_poss = {unique_poss{:} poss_in{ii}};
unique_poss = temp_poss;
temp_cntr = [unique_cntr 1];
unique_cntr = temp_cntr;
end

n = n + 1;
end

% For the unique sets with more than 2 hits, if the number of hits is
% equal to the size of the unique set, then remove values from the
% other possibilities
if any(unique_cntr > 2)
ind_uniques = unique_cntr > 2;

unique_sets = {unique_poss{ind_uniques}};
for ii = 1:numel(unique_sets)
if numel(unique_sets{ii}) == unique_cntr(ii)
for jj = 1:9
if numel(intersect(poss{jj}, unique_sets{ii})) ...
== numel(unique_sets{ii})
poss{jj} = intersect(poss{jj}, unique_sets{ii});
end
end
end
end
end

poss_out = reshape(poss, num_rows, num_cols);
end```

The first part of `subsetUpdate`, starting from the comment “Count the number of unique sets”, looks for unique sets (`unique_sets`) and counts them (`unique_cntr`). If we apply the first part of the code, we end up with:

`unique_sets = { [2 5 6], [2 5], [7 8 9], [7 8]}`
`unique_cntr = [ 1 2 1 2 ]`

That is, there is only 1 instance of the set `[2 5 6]`, 2 instances of `[2 5]`, etc.

The next part of `subsetUpdate`, starting from the second comment, narrows down the possibilities based upon the unique sets and the number of times they occur. To do this, we simply look for a unique set whose size is equal to the number of occurrences. For example, the set `[2 5]` has 2 elements, and occurs twice in our possibilities. This means that 2 and 5 can only exist in those two locations and can be removed from all other locations. Using this logic, we can remove `[2 5]` from `[2 5 6]` and `[7 8]` from `[7 8 9]`. The output of this function is then:

`poss_out = { [], [6], [2 5], [], [9], [], [7 8], [2 5], [7 8] }`

Advertisements