Update: I found another puzzle that breaks the code, click here for Revision 3.0!
I never claimed that my Sudoku Solver worked for every puzzle. In fact, it was pretty careless of me to post the code checking it against only two puzzles. And for those two puzzles, it worked just fine.
Two weekends ago, I went to Barnes and Noble, typed in one of the harder puzzles, and found out that my code broke. Oops.
The good news is that I fixed my code and it works again! I’ve tested it on a few puzzles from the New York Times and Web Sudoku. The new code was able to solve 8 new puzzles varying from easy to evil.
So I’ve only tested it against 10 puzzles total… But it’s better than 2. If it breaks again, I’ll post a fix. But I think I’m in the clear for now. Here’s the code!
main.m
clear
clc
% Puzzles from rev 2
% ========================================================================
websudoku_easy = ...
[0 3 0 0 6 0 5 1 2; ...
2 4 0 0 0 0 3 0 0; ...
0 0 1 0 0 0 8 0 6; ...
...
0 0 5 0 0 8 0 3 0; ...
3 6 2 0 7 0 1 8 4; ...
0 9 0 4 0 0 6 0 0; ...
...
9 0 4 0 0 0 7 0 0; ...
0 0 3 0 0 0 0 5 8; ...
1 8 7 0 4 0 0 9 0];
sudokuSolver(websudoku_easy)
% websudoku_evil_2 = ...
% [6 0 0 0 0 0 0 0 4; ...
% 1 0 0 5 0 0 0 3 0; ...
% 0 0 0 0 8 0 7 0 2; ...
% ...
% 2 0 3 0 0 6 0 0 0; ...
% 0 0 0 1 0 5 0 0 0; ...
% 0 0 0 9 0 0 6 0 5; ...
% ...
% 8 0 1 0 9 0 0 0 0; ...
% 0 7 0 0 0 4 0 0 9; ...
% 9 0 0 0 0 0 0 0 3];
%
% sudokuSolver(websudoku_evil_2)
% websudoku_evil_1 = ...
% [0 0 0 0 0 7 3 0 2; ...
% 0 0 0 2 0 0 1 0 0; ...
% 3 0 2 4 0 0 0 0 0; ...
% ...
% 8 0 0 6 0 1 0 0 5; ...
% 0 6 0 0 0 0 0 1 0; ...
% 5 0 0 3 0 9 0 0 4; ...
% ...
% 0 0 0 0 0 5 6 0 8; ...
% 0 0 8 0 0 4 0 0 0; ...
% 7 0 1 9 0 0 0 0 0];
%
% sudokuSolver(websudoku_evil_1)
% puzz_nyt_diff_27_oct_2010 = ...
% [2 0 0 1 0 7 0 0 4; ...
% 0 0 0 0 0 0 2 3 0; ...
% 9 0 0 6 0 0 0 0 0; ...
% ...
% 0 6 0 0 0 5 0 4 0; ...
% 0 0 4 3 0 0 0 2 0; ...
% 0 0 7 0 0 6 0 0 8; ...
% ...
% 0 7 1 2 0 3 0 0 0; ...
% 0 0 0 4 0 0 0 0 5; ...
% 0 0 0 0 0 0 0 0 0];
%
% sudokuSolver(puzz_nyt_diff_27_oct_2010)
% puzz_nyt_med_27_oct_2010 = ...
% [8 0 1 0 0 0 5 0 0; ...
% 0 3 4 0 0 8 0 0 0; ...
% 0 2 0 0 0 7 1 9 0; ...
% ...
% 0 0 0 3 0 0 7 4 6; ...
% 0 0 0 0 0 2 0 0 0; ...
% 0 0 0 0 0 4 0 0 5; ...
% ...
% 1 0 0 8 0 6 0 0 0; ...
% 2 0 0 1 0 0 9 0 0; ...
% 0 8 0 0 4 0 0 0 0];
%
% sudokuSolver(puzz_nyt_med_27_oct_2010)
% puzz_nyt_easy_27_oct_2010 = ...
% [0 5 0 0 0 0 3 0 0; ...
% 0 3 0 0 0 1 8 0 2; ...
% 9 8 0 2 0 0 0 0 6; ...
% ...
% 6 2 0 0 0 9 0 0 8; ...
% 0 0 0 7 6 0 0 1 0; ...
% 0 1 8 3 0 0 0 0 7; ...
% ...
% 4 0 0 0 0 0 5 0 0; ...
% 1 0 0 4 0 2 0 8 9; ...
% 0 6 5 0 0 0 0 0 0];
%
% sudokuSolver(puzz_nyt_easy_27_oct_2010)
% puzz_nyt_diff_12_oct_2010 = ...
% [0 0 0 7 0 0 0 0 0; ...
% 3 2 0 0 0 0 7 8 0; ...
% 0 6 0 0 9 0 0 5 0; ...
% ...
% 0 0 1 0 8 0 9 0 0; ...
% 0 0 0 4 0 2 0 0 0; ...
% 0 0 7 0 1 0 0 0 2; ...
% ...
% 0 0 0 0 0 0 3 0 0; ...
% 6 1 0 0 0 0 0 0 4; ...
% 8 0 0 1 7 0 0 0 0];
%
% sudokuSolver(puzz_nyt_diff_12_oct_2010);
% puzz_182 = ...
% [0 0 5 0 0 0 0 0 0; ...
% 0 0 4 8 6 0 9 0 0; ...
% 0 0 0 3 0 7 8 0 0; ...
% ...
% 0 0 0 0 4 2 0 0 7; ...
% 0 0 2 0 0 0 0 0 0; ...
% 1 0 0 0 0 8 6 0 0; ...
% ...
% 0 8 0 0 9 0 7 0 0; ...
% 0 0 0 0 1 5 0 0 6; ...
% 6 0 0 0 0 0 0 0 4];
%
% ans_182 = ...
% [8 7 5 9 2 4 1 6 3; ...
% 2 3 4 8 6 1 9 7 5; ...
% 9 1 6 3 5 7 8 4 2; ...
% ...
% 3 9 8 6 4 2 5 1 7; ...
% 5 6 2 1 7 9 4 3 8; ...
% 1 4 7 5 3 8 6 2 9; ...
% ...
% 4 8 3 2 9 6 7 5 1; ...
% 7 2 9 4 1 5 3 8 6; ...
% 6 5 1 7 8 3 2 9 4];
%
% sudokuSolver(puzz_182)
% Puzzles from rev 1
% ========================================================================
% puzz_1 = ...
% [0 3 0 0 0 0 0 1 0; ...
% 5 0 0 0 6 0 0 9 2; ...
% 6 0 2 9 0 5 8 0 0; ...
% ...
% 0 9 3 7 0 0 0 2 5; ...
% 2 0 0 4 0 9 0 0 8; ...
% 4 8 0 0 0 3 1 6 0; ...
% ...
% 0 0 1 6 0 4 2 0 3; ...
% 3 7 0 0 2 0 0 0 4; ...
% 0 2 0 0 0 0 0 5 1];
%
% ans_1 = ...
% [7 3 9 8 4 2 5 1 6; ...
% 5 4 8 1 6 7 3 9 2; ...
% 6 1 2 9 3 5 8 4 7; ...
% ...
% 1 9 3 7 8 6 4 2 5; ...
% 2 6 5 4 1 9 7 3 8; ...
% 4 8 7 2 5 3 1 6 9; ...
% ...
% 8 5 1 6 9 4 2 7 3; ...
% 3 7 6 5 2 1 9 8 4; ...
% 9 2 4 3 7 8 6 5 1];
%
% soln_1 = sudokuSolver(puzz_1);
% puzz_2 = ...
% [0 0 5 4 2 9 3 0 0; ...
% 0 7 0 0 0 0 0 6 0; ...
% 0 9 8 0 0 0 2 4 0; ...
% ...
% 0 0 0 2 3 1 0 0 0; ...
% 0 0 0 0 0 0 0 0 0; ...
% 0 0 0 7 6 5 0 0 0; ...
% ...
% 0 6 7 0 0 0 9 3 0; ...
% 0 5 0 0 0 0 0 2 0; ...
% 0 0 9 6 1 8 7 0 0];
%
% ans_2 = ...
% [6 1 5 4 2 9 3 8 7; ...
% 4 7 2 8 5 3 1 6 9; ...
% 3 9 8 1 7 6 2 4 5; ...
% ...
% 7 4 6 2 3 1 5 9 8; ...
% 5 2 1 9 8 4 6 7 3; ...
% 9 8 3 7 6 5 4 1 2; ...
% ...
% 8 6 7 5 4 2 9 3 1; ...
% 1 5 4 3 9 7 8 2 6; ...
% 2 3 9 6 1 8 7 5 4];
%
% soln_2 = sudokuSolver(puzz_2);
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
num.m
classdef num
properties
puzz_orig
puzz
poss
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
% repeatedly to check the possibilities cell array. If only one
% possibily exists in a cell, then that possibility is written
% into the puzzle matrix. After writing the puzzle matrix, the
% specific row, column, and square of the possibilities matrix is
% updated.
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(obj.puzz == 0)
new_obj = num(obj.puzz_orig);
obj = new_obj;
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
end
% Loops through every cell to check if only one possibility exists.
function [obj changed] = 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
end
% Loops over all rows/columns/squares to check for subsets
function [obj changed] = solveSubset(obj)
changed = 0;
for ii = 1:9
[obj subset_changed] = updatePoss(...
obj, ...
@subsetUpdate, ...
ii);
if subset_changed
changed = 1;
end
end
end
% Loops over all rows/columns/squares to check for unique sets
function [obj changed] = solveUnique(obj)
changed = 0;
for ii = 1:9
[obj unique_changed] = updatePoss(...
obj, ...
@uniqueUpdate, ...
ii);
if unique_changed
changed = 1;
end
end
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 nummbers 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
Stochastic Observations 
One thought on “MATLAB – Sudoku Solver Rev. 2.0”