Okay, one more iteration for this thing. Traveling back home for Thanksgiving, I typed in some more sudoku puzzles from the back of the in-flight magazine. Leave it to Southwest to once again break my code…

Edit: Click here for revision 3.1

So here we are with revision 3.0 of my Sudoku Solver. This time, I’ve added a recursive guessing mechanism. If we go through revision 2.0 and still end up with unsolved cells, then we take a random cell with the smallest amount of possibilities and randomly choose one possibility. This possibility gets written into the cell and then the code is recursively called. If we make it through the code again and end up with unsolved cells, then we have guessed wrong. At that point, we reset the possibility and puzzle matrices and then take a different guess at that cell.

Index

main.m

clear
clc

% Puzzles from 24 November 2010 flight
% ========================================================================

hard2 = ...
    [0 0 0  4 0 7  0 0 0; ...
     8 0 7  0 6 0  2 0 9; ...
     0 4 0  0 0 0  0 7 0; ...
     ...
     0 0 4  0 0 0  3 0 0; ...
     0 0 0  9 0 6  0 0 0; ...
     0 0 5  0 0 0  1 0 0; ...
     ...
     0 9 0  0 0 0  0 8 0; ...
     3 0 1  0 5 0  4 0 2; ...
     0 0 0  7 0 3  0 0 0];
sudokuSolver(hard2)

% hard1 = ...
%     [0 0 0  0 0 6  0 0 0; ...
%      0 7 0  0 4 5  0 0 2; ...
%      5 0 0  2 0 0  9 0 0; ...
%      ...
%      2 0 0  0 0 0  0 8 0; ...
%      0 9 0  1 0 7  0 4 0; ...
%      0 8 0  0 0 0  0 0 6; ...
%      ...
%      0 0 4  0 0 8  0 0 7; ...
%      6 0 0  4 7 0  0 3 0; ...
%      0 0 0  9 0 0  0 0 0];
% sudokuSolver(hard1)

% easy = ...
%     [5 4 7  0 0 3  0 0 0; ...
%      0 3 6  0 0 0  0 4 2; ...
%      0 0 0  9 7 4  0 0 0; ...
%      ...
%      0 0 3  1 0 8  0 6 9; ...
%      0 0 9  0 3 0  2 0 0; ...
%      6 5 0  4 0 2  3 0 0; ...
%      ...
%      0 0 0  8 1 9  0 0 0; ...
%      2 6 0  0 0 0  9 7 0; ...
%      0 0 0  6 0 0  1 3 4];
% sudokuSolver(easy)

% warm_up = ...
%     [9 0 0  5 0 0  6 0 0; ...
%      0 0 0  0 6 9  0 1 3; ...
%      5 0 3  0 0 8  0 4 0; ...
%      ...
%      6 2 0  0 7 1  0 9 0; ...
%      3 1 0  0 0 0  0 5 7; ...
%      0 7 0  8 2 0  0 3 6; ...
%      ...
%      0 5 0  2 9 7  3 0 1; ...
%      7 9 0  1 8 0  0 0 0; ...
%      0 0 2  0 0 4  0 0 9];
% sudokuSolver(warm_up)

Return to index

sudokuSolver.m

function varargout = sudokuSolver(A)

% Input: 9x9 matrix, unknowns should be populated with 0.

puzzle = num(A);

puzzle = solve(puzzle);

if nargout == 0
    disp(puzzle)
elseif nargout == 1
    varargout{1} = puzzle.puzz;
elseif nargout == 2
    varargout{1} = puzzle.puzz;
    varargout{2} = puzzle.poss;
end

end

Return to index

num.m

classdef num
    properties
        puzz_orig   % The original puzzle input
        puzz        % The puzzle output, 9x9 matrix of values 0 to 9
        poss        % The possibilities matrix, 9x9 cell matrix
                    %   corresponding to each cell in the puzzle matrix
        
        guess       % The current guess
        guess_row   % Current guess's row
        guess_col   % Current guess's column
        guess_orig  % num object of puzzle before the guess
        guessed     % Vector holding the guesses we have tried
    end
    
    methods
        
        % Constructor
        % 
        %   Creates a num object which holds the puzzle matrix and the
        %   possibilies cell array. The puzzle matrix is simply a 9x9
        %   matrix with 0s for the unknown locations. The possibilies
        %   matrix is a 9x9 cell array which a subset of the integers 1
        %   through 9.
        function obj = num(puzz)
            % Assign the given puzzle matrix
            obj.puzz = puzz;
            obj.puzz_orig = puzz;
            
            % Assign all possibilies
            all_poss = [1 2 3 4 5 6 7 8 9];
            obj.poss = cell(9, 9);
            for ii = 1:9
                for jj = 1:9
                    obj.poss{ii, jj} = all_poss;
                end
            end
            
            % Update the possibilies cell array
            for ii = 1:9
                obj = updatePoss(obj, @solvedUpdate, ii);
            end
        end
        
        % Solve
        %
        %   After the object has been initialized, this function is called
        %   once to solve the puzzle. There are three main processes to
        %   solve the puzzle. The first process is a loop that seeks unique
        %   possibilities first and does subset operations after. If this
        %   fails then the second process seeks subset possibilities first
        %   and unique possibilities after. If these two processes fail,
        %   then the final process starts the guessing algorithm.
        function obj = solve(obj)
            
            n = 0;
            done = 0;
            while ~done
                [obj single_changed] = solveSingle(obj);
                
                if ~single_changed
                    [obj unique_changed] = solveUnique(obj);
                    
                    if ~unique_changed
                        [obj subset_changed] = solveSubset(obj);
                        
                        if ~subset_changed
                            done = 1;
                        end
                    end
                end
                n = n + 1;
            end
            
            % If we end up with unsolved cells, then we removed too many
            % sets in the wrong order. Start over by removing subsets first
            % and then unique sets after.
            if any(any(obj.puzz == 0))
                old_obj = obj;
                obj = num(obj.puzz_orig);
                n = 0;
                done = 0;
                while ~done
                    [obj single_changed] = solveSingle(obj);
                    
                    if ~single_changed
                        [obj subset_changed] = solveSubset(obj);
                        
                        if ~subset_changed
                            [obj unique_changed] = solveUnique(obj);
                            
                            if ~unique_changed
                                done = 1;
                            end
                        end
                    end
                    n = n + 1;
                end
            end
            
            % At this point, should have solved the puzzle. Start guessing.
            if any(any(obj.puzz == 0))
                obj = solveGuess(old_obj);
                obj = solve(obj);
            end
        end
        
        % Loops through every cell to check if only one possibility exists.
        function [obj varargout] = solveSingle(obj)
            
            changed = 0;
            for ii = 1:9
                for jj = 1:9
                    if isempty(obj.poss{ii, jj})
                        continue
                    end
                    
                    obj.poss{ii, jj} = checkOnlyPoss(obj, ii, jj);
                    
                    if numel(obj.poss{ii, jj}) == 1
                        obj.puzz(ii, jj) = obj.poss{ii, jj};
                        [obj solved_changed] = updatePoss(...
                            obj, ...
                            @solvedUpdate, ...
                            ii, ...
                            jj);
                        if solved_changed
                            changed = 1;
                        end
                    end
                end
            end
            
            if nargout == 2
                varargout{1} = changed;
            end
        end
        
        % Loops over all rows/columns/squares to check for subsets
        function [obj varargout] = solveSubset(obj, varargin)
            
            if nargin == 2
                switch varargin{1}
                    case 'reverse'
                        iters = 9:-1:1;
                    case 'random'
                        iters = randperm(9);
                    otherwise
                        iters = 1:9;
                end
            else
                iters = 1:9;
            end
            
            changed = 0;
            for ii = iters
                [obj subset_changed] = updatePoss(...
                    obj, ...
                    @subsetUpdate, ...
                    ii);
                
                if subset_changed
                    changed = 1;
                end
            end
            
            if nargout == 2
                varargout{1} = changed;
            end
        end
        
        % Loops over all rows/columns/squares to check for unique sets
        function [obj varargout] = solveUnique(obj, varargin)
            
            if nargin == 2
                switch varargin{1}
                    case 'reverse'
                        iters = 9:-1:1;
                    case 'random'
                        iters = randperm(9);
                    otherwise
                        iters = 1:9;
                end
            else
                iters = 1:9;
            end
            
            changed = 0;
            for ii = iters
                [obj unique_changed] = updatePoss(...
                    obj, ...
                    @uniqueUpdate, ...
                    ii);
                
                if unique_changed
                    changed = 1;
                end
            end
            
            if nargout == 2
                varargout{1} = changed;
            end
        end
        
        function obj = solveGuess(obj)
            if isempty(obj.guess_orig)
                % Make a first guess on a cell with a minimum number of
                % possibilities
                
                % Count the number of possibilities in each cell
                poss_num = zeros(9);
                for ii = 1:9
                    for jj = 1:9
                        poss_num(ii, jj) = numel(obj.poss{ii, jj});
                    end
                end
                
                % Find the minimum number of possibilities overall
                min_poss = min(min(poss_num(poss_num ~= 0)));
                
                % Create some variables to help separate the minim number
                % of possibilities
                ind_min = poss_num == min_poss;
                [col_mesh row_mesh] = meshgrid(1:9, 1:9);
                guess_rows = row_mesh(ind_min);
                guess_cols = col_mesh(ind_min);
                
                % Take a random cell with the minimum number of guesses
                guess_num = randi(length(guess_rows));
                obj.guess_row = guess_rows(guess_num);
                obj.guess_col = guess_cols(guess_num);
                
                % Take a random possibility within the cell
                guess_poss = obj.poss{obj.guess_row, obj.guess_col};
                obj.guess = guess_poss(randi(length(guess_poss)));
                obj.guessed = obj.guess;
                obj.guess_orig = obj;
                
            else
                % Guessed wrong
                
                % Find all the other possibilities within the guess matrix
                guess_poss = ...
                    obj.guess_orig.poss{...
                        obj.guess_row, ...
                        obj.guess_col};
                guess_poss = setxor(guess_poss, obj.guessed);
                
                % Take a random possibility, other than the one just tried
                obj.guess = guess_poss(randi(length(guess_poss)));
                obj.guessed = [obj.guessed obj.guess];
                
                % Reset the possibility and puzzle matricies to that before
                % our initial guess
                obj.poss = obj.guess_orig.poss;
                obj.puzz = obj.guess_orig.puzz;
            end
            
            % Set the only possibility for that cell as our guess, then
            % update the possibilities matrix
            obj.poss{obj.guess_row, obj.guess_col} = obj.guess;
            obj = solveSingle(obj);
        end
        
        % Check Only Possible
        %
        %   This function checks the possibility cell array for the only
        %   possible values. Meaning, if the number 5 can only be placed in
        %   one specific place in a row, then it will flag that row. Once
        %   flagged, the current possibilities cell is replaced by the only
        %   possible value. Immediately after this function returns,
        %   isolated possibilities are written into the puzzle matrix
        function poss_out = checkOnlyPoss(obj, ii, jj)
            poss_out = obj.poss{ii, jj};
            
            if isempty(obj.poss{ii, jj})
                return
            end
            
            row_poss = {obj.poss{ii, :}};
            col_poss = {obj.poss{:, jj}};
            
            [sqr, sqr_num, ind_rows, ind_cols] = getSqr(obj, ii, jj);
            sqr_poss = {obj.poss{ind_rows, ind_cols}};
            
            vals = obj.poss{ii, jj};
            for mm = 1:numel(vals)
                val = vals(mm);
                
                found_row = 0;
                found_col = 0;
                found_sqr = 0;
                
                for nn = 1:9
                    % Check rows
                    if nn ~= jj && ~found_row
                        if ~isempty(intersect(row_poss{nn}, val))
                            found_row = 1;
                        end
                    end
                    
                    % Check cols
                    if nn ~= ii && ~found_col
                        if ~isempty(intersect(col_poss{nn}, val))
                            found_col = 1;
                        end
                    end
                    
                    % Check sqrs
                    if nn ~= sqr_num && ~found_sqr
                        if ~isempty(intersect(sqr_poss{nn}, val))
                            found_sqr = 1;
                        end
                    end
                end
                
                if ~found_row || ~found_col || ~found_sqr
                    poss_out = val;
                end
            end
        end
        
        % Update Possibilies
        % 
        %   Wrapper function. Takes in the object plus one or two
        %   variables. If one variable is given, then each row, column, and
        %   square is processed by their number. If two variables are
        %   given, then only a specific row, column, and square is
        %   processed.
        function [obj changed] = updatePoss(obj, func, varargin)
            switch nargin
                case 3
                    [obj changed_row] = updatePossRow(...
                        obj, ...
                        func, ...
                        varargin{1});
                    [obj changed_col] = updatePossCol(...
                        obj, ...
                        func, ...
                        varargin{1});
                    [obj changed_sqr] = updatePossSqr(...
                        obj, ...
                        func, ...
                        varargin{1});
                case 4
                    [obj changed_row] = updatePossRow(...
                        obj, ...
                        func, ...
                        varargin{1});
                    [obj changed_col] = updatePossCol(...
                        obj, ...
                        func, ...
                        varargin{2});
                    [obj changed_sqr] = updatePossSqr(...
                        obj, ...
                        func, ...
                        varargin{1}, ...
                        varargin{2});
            end
            
            changed = any([changed_row changed_col changed_sqr]);
        end
        
        % Update Possibilies Row
        %
        %   Wrapper function. Calls updatePossBlock to update a row.
        function [obj changed] = updatePossRow(obj, func, row_num)
            [temp_out changed] = ...
                func(...
                    obj.puzz(row_num, : ), ...
                    {obj.poss{row_num, :}});
            
            for ii = 1:9
                obj.poss{row_num, ii} = temp_out{ii};
            end
        end
        
        % Update Possibilies Column
        %
        %   Wrapper function. Calls updatePossBlock to update a column.
        function [obj changed] = updatePossCol(obj, func, col_num)
            [temp_out changed] = ...
                func(...
                    obj.puzz(:, col_num), ...
                    {obj.poss{:, col_num}}); %#ok<*CCAT>
            
            for ii = 1:9
                obj.poss{ii, col_num} = temp_out{ii};
            end
        end
        
        % Update Possibilities Square
        %
        %   Wrapper function. Calls updatePossBlock to update a square.
        function [obj changed] = updatePossSqr(obj, func, varargin)
            if nargin == 3
                [sqr ind_rows ind_cols] = ...
                    getSqr(obj, varargin{1});
            elseif nargin == 4
                [sqr ind_rows ind_cols] = ...
                    getSqr(obj, varargin{1}, varargin{2});
            end
            
            [temp_out changed] = func(...
                sqr, ...
                {obj.poss{ind_rows, ind_cols}});
            
            for ii = 1:3
                for jj = 1:3
                    obj.poss{ind_rows(ii), ind_cols(jj)} = ...
                        temp_out{ii, jj};
                end
            end
        end
        
        % getSqr
        %
        %   This function is used to get either the square number or the
        %   set of rows and columns of a square.
        function [sqr varargout] = getSqr(obj, varargin)
            
            switch nargin
                case 2
                    sqr_num = varargin{1};
                    if sqr_num <= 3
                        ind_rows = 1:3;
                        
                        if sqr_num == 1
                            ind_cols = 1:3;
                        elseif sqr_num == 2
                            ind_cols = 4:6;
                        elseif sqr_num == 3
                            ind_cols = 7:9;
                        end
                        
                    elseif sqr_num <= 6
                        ind_rows = 4:6;
                        
                        if sqr_num == 4
                            ind_cols = 1:3;
                        elseif sqr_num == 5
                            ind_cols = 4:6;
                        elseif sqr_num == 6
                            ind_cols = 7:9;
                        end
                        
                    elseif sqr_num <= 9
                        ind_rows = 7:9;
                        
                        if sqr_num == 7
                            ind_cols = 1:3;
                        elseif sqr_num == 8
                            ind_cols = 4:6;
                        elseif sqr_num == 9
                            ind_cols = 7:9;
                        end
                    end
                        
                case 3
                    row_num = varargin{1};
                    col_num = varargin{2};
                    
                    if row_num <= 3
                        if col_num <= 3
                            sqr_num = 1;
                            ind_rows = 1:3;
                            ind_cols = 1:3;
                        elseif col_num <= 6
                            sqr_num = 2;
                            ind_rows = 1:3;
                            ind_cols = 4:6;
                        elseif col_num <= 9
                            sqr_num = 3;
                            ind_rows = 1:3;
                            ind_cols = 7:9;
                        else
                            error('Invalid Column Number')
                        end
                    elseif row_num <= 6
                        if col_num <= 3
                            sqr_num = 1;
                            ind_rows = 4:6;
                            ind_cols = 1:3;
                        elseif col_num <= 6
                            sqr_num = 2;
                            ind_rows = 4:6;
                            ind_cols = 4:6;
                        elseif col_num <= 9
                            sqr_num = 3;
                            ind_rows = 4:6;
                            ind_cols = 7:9;
                        else
                            error('Invalid Column Number')
                        end
                    elseif row_num <= 9
                        if col_num <= 3
                            sqr_num = 1;
                            ind_rows = 7:9;
                            ind_cols = 1:3;
                        elseif col_num <= 6
                            sqr_num = 2;
                            ind_rows = 7:9;
                            ind_cols = 4:6;
                        elseif col_num <= 9
                            sqr_num = 3;
                            ind_rows = 7:9;
                            ind_cols = 7:9;
                        else
                            error('Invalid Column Number')
                        end
                    else
                        error('Invalid Row Number')
                    end
            end
            
            sqr = obj.puzz(ind_rows, ind_cols);
            
            if nargout == 2
                varargout{1} = sqr_num;
            elseif nargout == 3
                varargout{1} = ind_rows;
                varargout{2} = ind_cols;
            elseif nargout == 4
                varargout{1} = sqr_num;
                varargout{2} = ind_rows;
                varargout{3} = ind_cols;
            end
        end
        
        function disp(obj)
            for ii = 1:9
                str = '';
                for jj = 1:9
                    str = [str num2str(obj.puzz(ii, jj)) ' ']; %#ok<*AGROW>
                    if mod(jj, 3) == 0
                        str = [str ' '];
                    end
                end
                disp(str)
                if mod(ii, 3) == 0
                    disp(' ')
                end
            end
        end
    end
end

% Solved Update
%
%   This generic function is used to update rows, columns, or squares. All
%   the current values of the puzzle matrix are removed from the
%   possibilities matrix.
function [poss_out changed] = solvedUpdate(puzz_in, poss_in)
    changed = 0;
    [num_rows num_cols] = size(puzz_in);
    puz = reshape(puzz_in, 9, 1);
    pos = reshape(poss_in, 9, 1);
    
    ind_filled = 1:9;
    ind_filled = ind_filled(puz ~= 0);
    for ii = 1:numel(ind_filled)
        pos{ind_filled(ii)} = [];
    end
    
    curr_vals = sort(puz(puz ~= 0));
    
    for ii = 1:numel(curr_vals)
        for jj = 1:9
            po = pos{jj};
            if isempty(po)
                continue
            end
            pos{jj} = po(po ~= curr_vals(ii));
            changed = 1;
        end
    end
    
    poss_out = reshape(pos, num_rows, num_cols);
end

% Subset Update
%
%   This function searches for subsets of repeated numbers within the
%   possibility matrix. If two sets of the same numbers are found, then 
%   those two numbers can be removed from the possibility matrix.
function [poss_out changed] = subsetUpdate(puzz_in, poss_in)
    
    changed = 0;
    poss = reshape(poss_in, 9, 1);
    [num_rows num_cols] = size(puzz_in);
    
    if ~any(puzz_in == 0)
        poss_out = reshape(poss, num_rows, num_cols);
        return
    end
    
    unique_poss = cell(1);
    subset_cntr = zeros(1);
    n = 1;
    
    % Count the number of unique sets
    for ii = 1:9
        if isempty(poss{ii});
            continue
        end
        
        if n == 1
            unique_poss{n} = poss{ii};
            n = n + 1;
            continue
        end
        
        found = 0;
        for nn = 1:numel(unique_poss)
            
            if ((numel(setdiff(poss{ii}, unique_poss{nn})) == 0) && ...
                (numel(unique_poss{nn}) == numel(poss{ii})))
            
                found = 1;
            end
        end
        
        if ~found
            
            temp_poss = {unique_poss{:} poss{ii}};
            unique_poss = temp_poss;
            
            temp_subset_cntr = [subset_cntr 0];
            subset_cntr = temp_subset_cntr;
            
        end
        
        n = n + 1;
    end
    
    for ii = 1:9
        for nn = 1:numel(unique_poss)
            if numel(setdiff(poss{ii}, unique_poss{nn})) == ...
               (numel(poss{ii}) - numel(unique_poss{nn}))
            
                subset_cntr(nn) = subset_cntr(nn) + 1;
            end
        end
    end
    
    if any(subset_cntr > 2)
        ind_uniques = subset_cntr > 2;
        unique_sets = {unique_poss{ind_uniques}};
        unique_subset_cntr = subset_cntr(ind_uniques);
        for ii = 1:numel(unique_sets)
            if numel(unique_sets{ii}) == unique_subset_cntr(ii)
                for jj = 1:9
                    
                    if isempty(poss{jj})
                        continue
                    end
                    
                    if numel(unique_sets{ii}) == numel(poss{jj})
                        if all(unique_sets{ii} == poss{jj})
                            continue
                        end
                    end
                    
                    poss_diff = setdiff(poss{jj}, unique_sets{ii});
                    if numel(poss_diff) == ...
                       numel(poss{jj}) - numel(unique_sets{ii})
                        
                        poss{jj} = unique_sets{ii};
                        changed = 1;
                    end
                    
                end
            end
        end
    end
    
    poss_out = reshape(poss, num_rows, num_cols);
end

% Unique Update
function [poss_out changed] = uniqueUpdate(puzz_in, poss_in)
    
    changed = 0;
    poss = reshape(poss_in, 9, 1);
    [num_rows num_cols] = size(puzz_in);
    
    if ~any(puzz_in == 0)
        poss_out = reshape(poss, num_rows, num_cols);
        return
    end
    
    unique_poss = cell(1);
    unique_cntr = ones(1);
    n = 1;
    
    % Count the number of unique sets
    for ii = 1:9
        if isempty(poss{ii});
            continue
        end
        
        if n == 1
            unique_poss{n} = poss{ii};
            n = n + 1;
            continue
        end
        
        found = 0;
        for nn = 1:numel(unique_poss)
            
            if ((numel(setdiff(poss{ii}, unique_poss{nn})) == 0) && ...
                (numel(unique_poss{nn}) == numel(poss{ii})))
               
                unique_cntr(nn) = unique_cntr(nn) + 1;
                found = 1;
            end
        end
        
        if ~found
            
            temp_poss = {unique_poss{:} poss{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}};
        unique_set_cntr = unique_cntr(ind_uniques);
        for ii = 1:numel(unique_sets)
            
            if numel(unique_sets{ii}) == unique_set_cntr(ii)
                for jj = 1:9
                    
                    if isempty(poss{jj})
                        continue
                    end
                    
                    if numel(unique_sets{ii}) == numel(poss{jj})
                        if all(unique_sets{ii} == poss{jj})
                            continue
                        end
                    end
                    
                    poss_diff = setdiff(poss{jj}, unique_sets{ii});
                    if numel(poss_diff) < numel(poss{jj})
                        poss{jj} = poss_diff;
                        changed = 1;
                    end
                end
            end
            
        end
    end
    
    poss_out = reshape(poss, num_rows, num_cols);
end

Return to index

Advertisements