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