Making a Sudoku Puzzle Solver

Sudoku is a traditional number game that requires the 1~9 to be put on a 9 by 9 grid such that on every row, every column, and every 3 by 3 block there is exactly one of each number. Usually people solve this as a hobby to kill time, but have you thought about giving a computer the power to solve all possible Soduku puzzles in only a fraction of a second?

The advantage of computer over human brains is that a computer can check millions of possibilities per second. Even though computer is not so good at reasoning or imagining things like we do, we can still teach computers to think in a different way to fully use their computing power. In the case of this Sudoku puzzle solver, we first scan the board to see what numbers are already on it, and then we enter a while loop to iteratively solve the it piece by piece until the entire board is filled with correct numbers.

The while loop is as following:

• for each cell, check if it is already filled

• if it is, then remember what number is filled

• if not, check the row, the column, and the 3 by 3 block to see what valid numbers can be filled in

• if there is only one valid number for that cell, then fill it in

• check if the cell is the only one in the 3 by 3 block that has a certain valid number

• check if the cell is the only one in the row that has a certain valid number

• check if the cell is the only one in the column that has a certain valid number

• update valid candidates for each cell

• repeat

And the result:

The MATLAB code is as following:

%% take board as an input (just an example)

board = [

0 0 6 0 3 0 0 0 9;

7 8 0 0 2 0 6 4 3;

0 9 0 4 0 0 1 0 0;

0 0 0 0 0 7 0 0 8;

0 0 3 0 0 0 7 0 0;

6 0 0 3 0 0 0 0 0;

0 0 8 0 0 9 0 6 0;

1 6 9 0 7 0 0 8 4;

4 0 0 0 5 0 3 0 0]

original = board;

%% solve board

tic;

allValid = zeros(9, 9) + 1;

boardValid = zeros(9, 9);

iteration = 0;

usableNum = zeros(9, 9, 9);

while(sum(sum(boardValid == allValid)) ~= 81)

iteration = iteration + 1;

fprintf('Iteration %d\n', iteration);

for i = 1:9

for j = 1:9

blockX = ceil(i/3);

blockY = ceil(j/3);

index = 1;

usableNum(i, j, :) = 0;

% if (i, j) is filled, then it is done

if (board(i, j) ~= 0)

boardValid(i, j) = 1;

else

% if (i, j) is empty, find all valid numbers for it

for num = 1:9

if((checkValidity(board, num, i, j) == 1))

usableNum(i, j, index) = num;

index = index + 1;

end

end

% check if (i, j) has only one valid number

if (index == 2)

board(i, j) = usableNum(i, j, 1);

%fprintf('Using single candidate at %d %d\n', i, j);

% update valid numbers

% itself

usableNum(i, j, :) = 0;

% row

rowUsable = usableNum(i, :, :);

rowUsable(find(rowUsable == num)) = 0;

usableNum(i, :, :) = rowUsable;

% column

columnUsable = usableNum(:, j, :);

columnUsable(find(columnUsable == num)) = 0;

usableNum(:, j, :) = columnUsable;

% block

blockUsable = usableNum(((blockX-1)*3 + 1):((blockX-1)*3 + 3), ((blockY-1)*3 + 1):((blockY-1)*3 + 3), :);

blockUsable(find(blockUsable == num)) = 0;

usableNum(((blockX-1)*3 + 1):((blockX-1)*3 + 3), ((blockY-1)*3 + 1):((blockY-1)*3 + 3), :) = blockUsable;

end

if(iteration > 5)

% check if (i, j) is the only cell in the block that has a

% certain valid number

for r = 1:9

block = board(((blockX-1)*3 + 1):((blockX-1)*3 + 3), ((blockY-1)*3 + 1):((blockY-1)*3 + 3));

blockUsable = usableNum(((blockX-1)*3 + 1):((blockX-1)*3 + 3), ((blockY-1)*3 + 1):((blockY-1)*3 + 3), :);

if(checkBlock(block, blockUsable, r, i-(blockX-1)*3, j-(blockY-1)*3) == 1)

board(i, j) = r;

% update valid numbers

% itself

usableNum(i, j, :) = 0;

% row

rowUsable = usableNum(i, :, :);

rowUsable(find(rowUsable == r)) = 0;

usableNum(i, :, :) = rowUsable;

% column

columnUsable = usableNum(:, j, :);

columnUsable(find(columnUsable == r)) = 0;

usableNum(:, j, :) = columnUsable;

end

end

% check if (i, j) is the only cell in the row that has a

% certain valid number

for r = 1:9

if (checkRow(board(i, :), usableNum(i, :, :), r, j) == 1)

board(i, j) = r;

% update valid numbers

% it self

usableNum(i, j, :) = 0;

% column

columnUsable = usableNum(:, j, :);

columnUsable(find(columnUsable == r)) = 0;

usableNum(:, j, :) = columnUsable;

% block

blockUsable = usableNum(((blockX-1)*3 + 1):((blockX-1)*3 + 3), ((blockY-1)*3 + 1):((blockY-1)*3 + 3), :);

blockUsable(find(blockUsable == r)) = 0;

usableNum(((blockX-1)*3 + 1):((blockX-1)*3 + 3), ((blockY-1)*3 + 1):((blockY-1)*3 + 3), :) = blockUsable;

end

end

% check if (i, j) is the only cell in the column that has a

% certain valid number

for r = 1:9

if (checkColumn(board(:, j), usableNum(:, j, :), r, i) == 1)

board(i, j) = r;

% update valid numbers

% itself

usableNum(i, j, :) = 0;

% row

rowUsable = usableNum(i, :, :);

rowUsable(find(rowUsable == r)) = 0;

usableNum(i, :, :) = rowUsable;

% block

blockUsable = usableNum(((blockX-1)*3 + 1):((blockX-1)*3 + 3), ((blockY-1)*3 + 1):((blockY-1)*3 + 3), :);

blockUsable(find(blockUsable == r)) = 0;

usableNum(((blockX-1)*3 + 1):((blockX-1)*3 + 3), ((blockY-1)*3 + 1):((blockY-1)*3 + 3), :) = blockUsable;

end

end

end

end

end

end

sum(sum(boardValid))

end

elapsedTime = toc;

%% display results

figure;

hold on;

l = 5;

for i = 0:8

for j = 0:8

rectangle('Position', [i*l, j*l, l, l], 'LineWidth', 3)

txt = sprintf('%d', board(9-j, i+1));

text(i*l + l/2, j*l + l/2, txt, 'HorizontalAlignment', 'right', 'FontSize', 20);

end

end

hold off;

txt = sprintf('Time: %.2f s', elapsedTime);

h = msgbox(txt);

ah = get( h, 'CurrentAxes' );

ch = get( ah, 'Children' );

set( ch, 'FontSize', 20 );

figure;

hold on;

for i = 0:8

for j = 0:8

rectangle('Position', [i*l, j*l, l, l], 'LineWidth', 3)

txt = sprintf('%d', original(9-j, i+1));

if(original(9-j, i+1) ~= 0)

text(i*l + l/2, j*l + l/2, txt, 'HorizontalAlignment', 'right', 'FontSize', 20);

end

end

end