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