solve_sudoku (board, varargin)

function [solved_board, success] = solve_sudoku (board, varargin)
% SOLVE_SUDOKU Attempts to solve a sudoku grid
%
% solve_sudoku (board, current_row, current_col) -- Expects a 
% 9-by-9 grid with zeros in the location where numbers are 
% not known.  All other numbers in the grid must be integers 
% between 1 and 9.  The current_row and current_col arguments allow
% the iteration to begin at a particular point.
%

% Perform some basic error checking on inputs
if (nargin == 1)
    % If only one input argument, start solving at first row, first column
    current_row = 1;
    current_col = 1;
elseif (nargin == 3)
    % If three input arguments, start from the specified row and column
    current_row = varargin{1};
    current_col = varargin{2};
else
    % If any other number of arguments, display an error
    error ('Must pass either one or three arguments.');
end

% Perform some basic error checking on the board:
%  * Board must be 9-by-9
%  * Each element must be an integer between 0 and 9
[m,n] = size (board);
check = ismember(board, 0:9);
bad_elements = sum(check(:) == 0);
if (m ~= 9 || n ~= 9 || bad_elements > 0)
    error('A Sudoku Board must be 9-by-9 and consist of the elements 0-9');
end


% Set up the base case -- reached the last row, last column
if (current_row > 9 && current_col == 1)
    solved_board = board;
    success = 1;
    return;
end

% If a number already exists in the grid, solve for the next location
if (board(current_row, current_col) ~= 0)
    
    % Find the next location
    [next_row, next_col] = findNextPos(current_row, current_col);

    % Solve the rest of the grid and return whether or not successful
    [solved_board, success] = solve_sudoku(board, next_row, next_col);
    return;
    
end

   
% Find the elements that exist in the current row
row_elements = board(current_row, :);

% Find the elements that exist in the current column
col_elements = board(:, current_col)';

% Find the begining points of the local 3-by-3 grid
local_row = current_row - mod(current_row - 1, 3);
local_col = current_col - mod(current_col - 1, 3);

% Find the elements that exist in the local 3-by-3 grid
local_elements = board(local_row:local_row+2, local_col:local_col+2);
local_elements = reshape(local_elements, 1, 9);

% Find the possible elements that can fill this space
possibilities = setdiff(1:9, row_elements);
possibilities = setdiff(possibilities, col_elements);
possibilities = setdiff(possibilities, local_elements);

% Find next location to solve for
[next_row, next_col] = findNextPos(current_row, current_col);

% If there are no elements that fit, return failure
if (isempty (possibilities))
    solved_board = board;
    success = 0;
    return;
else

    % Try each of the possibilities until finding one that works
    for current_pos = 1:length(possibilities)

        % Maintain copy of board, in case the choice does not work
        old_board = board;

        % Try a possiblity from the list
        board (current_row, current_col) = possibilities(current_pos);

        % Using the choice, solve the rest of the board
        [solved_board, success] = solve_sudoku(board, next_row, next_col);

        % If the choice worked, exit the function successfully
        % Otherwise, restore the board
        if (success == 1)
            return;
        else
            board = old_board;
        end
    end

    % I have exhausted the possibilities, report failure and return
    solved_board = old_board;
    success = 0;
    return;
end
            


function [next_row, next_col] = findNextPos(current_row, current_col)

% Calculate the next location to solve for:
% If at the last column, wrap around to next row
% Otherwise, advance to the next column

if (current_col == 9)
    next_col = 1;
    next_row = current_row + 1;
else
    next_col = current_col + 1;
    next_row = current_row;
end