sudoku(puzzle)

function result = sudoku(puzzle)

% NAME:   Suri's Sudoku Solver (SSS)
% AUTHOR: Suri Like ([e-mail])
% DATE:   April 9, 2008
%
% DESCRIPTION:
% This function is a sudoku puzzle solver that uses a recursive algorithm
% described below.
%
%   Step 1. Take a standard sudoku puzzle in matrix form with all the blank
%   spots filled with zeroes. For example, you could type
%   puzzle=[7 0 0 5 8 3 0 0 6; 0 0 6 0 0 1 4 0 5; 0 5 2 0 0 6 0 8 3; 3 0 0 2
%   0 0 9 5 8; 5 0 0 0 7 8 0 6 0; 6 4 8 0 1 0 3 0 0; 0 6 0 8 0 2 5 0 0; 0 0 3
%   1 5 0 0 7 2; 2 1 5 6 0 0 0 3 0]
%
%   and MATLAB will give you
%
%   puzzle =
%      7     0     0     5     8     3     0     0     6
%      0     0     6     0     0     1     4     0     5
%      0     5     2     0     0     6     0     8     3
%      3     0     0     2     0     0     9     5     8
%      5     0     0     0     7     8     0     6     0
%      6     4     8     0     1     0     3     0     0
%      0     6     0     8     0     2     5     0     0
%      0     0     3     1     5     0     0     7     2
%      2     1     5     6     0     0     0     3     0
%
%   Step 2. Find the locations of all zeros. For each of them, determine
%   which numbers (between 1 and 9) are missing in the row, column and 3x3
%   box (region) that the zero belongs to. For example, the first zero in
%   the first row in the example above belongs to row 1 ( 7 0 0 5 8 3 0 0 6
%   ), column 2 ( 0 0 5 0 0 4 6 0 1 ) and the top-left region ( 7 0 0; 0 0
%   6; 0 5 2 ).
%
%   Step 3. The function determines that the numbers ( 1 2 4 9 )
%   are missing in row 1, the numbers ( 2 3 7 8 9 ) are missing in column
%   2, and finally the numbers ( 1 3 4 8 9 ) are missing in the top-left
%   region.
%
%   Step 4. The intersection ( common elements ) of the three arrays found 
%   in Step 3 is calculated. In this case, the only number that are common
%   to the three arrays above is 9. The function then fills the number 9 to
%   the location (1, 2) to replace the zero. However, if the intersection
%   of the three arrays has more than one number, the zero is not replaced
%   with any number and the incomplete puzzle will be fed into this
%   function again. This is where the recursion occurs. The recursion
%   continues until all zeros in the puzzle are replaced with numbers
%   (between 1 and 9). Then the result (solved puzzle) will be displayed.
%
%   HOW TO USE THIS FUNCTION:
%   It is easy. Simply place the files 'sudoku.m', 'rcb.m' and 'whichbox.m'
%   in the same folder, navigate to that folder in MATLAB, and then type up
%   the puzzle in the matrix form as shown in Step 1. Then just call the
%   function in Command Window by typing 'result = sudoku(puzzle)' and hit
%   enter.

% First determine whether the puzzle has been solved (whether to end
% recursion)
[zeror zeroc] = find(puzzle == 0); %The row and column indices of all zeros
cont = numel(zeror);               %If cont = 0, the puzzle is solved

% Two cases (puzzle is solved or not solved)
if cont == 0
    % This means all zeros are replaced with 1-9 and the puzzle is solved
    result = puzzle;
else
    % Solve by recursive function
    for i = 1:numel(zeror)
        % Find the missing numbers in the row that this zero belongs to
        rcand = rcb(puzzle(zeror(i), :));
        % Find the missing numbers in the column that this zero belongs to
        ccand = rcb(puzzle(:, zeroc(i)));
        % Find the missing numbers in the 3x3 box that this zero belongs to
        bcand = rcb(whichbox(puzzle, zeror(i), zeroc(i)));
        % Find the intersection of the three results above
        candidates = intersect(intersect(rcand, ccand), bcand);
        % If the intersection contains only one number, then it is the
        % number that should be filled into that spot
        if numel(candidates) == 1
            puzzle(zeror(i), zeroc(i)) = candidates;
        end
    end
    % Recursion. If there are still some zeros in the puzzle matrix, keep
    % solving it using recursive function.
    result = sudoku(puzzle);
end