Update: This was my first crack at this problem, and while it works for the two given puzzles, it breaks on other puzzles. Please see Revision 2.0 for an updated version of the code.
I went on travel last week; flew from the east coast to the west coast, non-stop. It’s a pretty long flight, about 5 hours. To amuse myself, I started doing the sudoku puzzle from the in-flight magazine. As I was finishing up the easy puzzle, I got this crazy idea to write up my own sudoku solver. “It can’t possibly be difficult, right?” I thought to myself. After all, solving a sudoku puzzle is just applied set theory; finding subsets and narrowing down the possibilities.
So once they announced that we were at a high enough altitude to use portable electronics, I whipped out my trusty laptop and went to work. Here’s the result.
main
This is just a main file that you can use to test out the program. Puzzle 1 is the warm up puzzle from the back of the magazine. Puzzle 2 is a slightly harder puzzle I found on the internet after I landed.
clear
clc
puzzle_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];
answer_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 iters_1] = sudokuSolver(puzzle_1);
puzzle_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];
answer_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 iters_2] = sudokuSolver(puzzle_2);
sudokuSolver
This next hunk of code is really just a wrapper for the actual code. This code just runs solveStep until the puzzle no longer changes. After this point, the wrapper code ends and spits out your solution.
function [soln n] = sudokuSolver(A)
% Input: 9x9 matrix, unknowns should be populated with 0.
n = 0;
puzzle = num(A);
done = 0;
while ~done
[puzzle changed] = solveStep(puzzle);
if ~changed
done = 1;
end
n = n + 1;
end
soln = puzzle.puzz;
end
num
This final piece of code is the workhorse. Basically, I decided to organize things using MATLAB’s object oriented structure. There are only two properties to a num object: a puzzle, puzz and a possible, poss. puzz is a matrix which stores the values of the puzzle and poss is a cell matrix which stores the possible values of each location. Each time you run solveStep the two matrices are updated and you end up one step closer to the solution.
classdef num
properties
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;
% 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 Step
%
% 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 changed] = solveStep(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 = updatePoss(obj, @solvedUpdate, ii, jj);
changed = 1;
return
end
end
end
for ii = 1:9
obj = updatePoss(obj, @subsetUpdate, ii);
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 = updatePoss(obj, func, varargin)
switch nargin
case 3
obj = updatePossRow(obj, func, varargin{1});
obj = updatePossCol(obj, func, varargin{1});
obj = updatePossSqr(obj, func, varargin{1});
case 4
obj = updatePossRow(obj, func, varargin{1});
obj = updatePossCol(obj, func, varargin{2});
obj = updatePossSqr(obj, func, varargin{1}, ...
varargin{2});
end
end
% Update Possibilies Row
%
% Wrapper function. Calls updatePossBlock to update a row.
function obj = updatePossRow(obj, func, row_num)
temp_out = ...
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 = updatePossCol(obj, func, col_num)
temp_out = ...
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 = 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 = 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
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 = solvedUpdate(puzz_in, poss_in)
[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));
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 = subsetUpdate(puzz_in, poss_in)
poss = reshape(poss_in, 9, 1);
[num_rows num_cols] = size(puzz_in);
unique_poss = cell(1);
unique_cntr = ones(1);
n = 1;
% Count the number of unique sets
for ii = 1:9
if isempty(poss_in{ii});
continue
end
if n == 1
unique_poss{n} = poss_in{ii};
n = n + 1;
continue
end
found = 0;
for nn = 1:numel(unique_poss)
if numel(intersect(unique_poss{nn}, poss_in{ii})) == ...
numel(unique_poss{nn})
unique_cntr(nn) = unique_cntr(nn) + 1;
found = 1;
end
end
if ~found
temp_poss = {unique_poss{:} poss_in{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}};
for ii = 1:numel(unique_sets)
if numel(unique_sets{ii}) == unique_cntr(ii)
for jj = 1:9
if numel(intersect(poss{jj}, unique_sets{ii})) ...
== numel(unique_sets{ii})
poss{jj} = intersect(poss{jj}, unique_sets{ii});
end
end
end
end
end
poss_out = reshape(poss, num_rows, num_cols);
end
Final Thoughts
After ~3 hours, the battery on my computer started to die. So I packed it away and finished it up on the plane ride back home. At the end of the first plane ride, it was able to solve easy puzzles. During the ride home, I added the subset functionality to solve the harder puzzles.
I’ll probably comment later on about the different algorithms and thought processes involved in this code. But for now, I just wanted to share it.
Stochastic Observations 
2 thoughts on “MATLAB – Sudoku Solver”