Brute force sudoku solver using Matlab/Octave.

sudoku_solver.m

function [B, REM] = sudoku_solver(A)
%
% [B, REM] = sudoku_solver(A);
%
% Solves the sudoku given by A. Only works if there is no guessing needed.
%

% A,B are 9x9 matricies of the values, with 0 for blanks
% REM is a 9x9x9 matrix of the possible values, with 0 indicating it is not possible, 1 indicating
% it is, -1 indicating that it is set to that value

global REM B;

%setup REM matrix
REM = ones(9,9,9);

%setup B matrix
B = zeros(9,9);

%tackle the given values first: find them and set them
[i,j] = find(A);
for COUNT = 1:length(i)
	set_square(i(COUNT), j(COUNT), A(i(COUNT), j(COUNT)));
end;

%start solving the rest
LOOPCOUNT = 1;
while ~isempty(find(B == 0)) && LOOPCOUNT < 100
	fill_only_in_square;
	fill_only_in_row;
	fill_only_in_column;
	fill_only_in_box;

	LOOPCOUNT = LOOPCOUNT + 1;
end;

%print the output
print_puzzle(LOOPCOUNT);

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function set_square(i,j,VAL)

global REM B;

%loop for value
for k = 1:9
	%test for given value and set it to -1
	if k == VAL
		REM(i,j,k) = -1;
	else
		REM(i,j,k) = 0;
	end;
end;

%update B
B(i,j) = VAL;

%scrub k from row, column and box
scrub_row(i,VAL);
scrub_column(j,VAL);
scrub_box(i,j,VAL);

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function scrub_row(i,k)

global REM B;

%loop for column
for j = 1:9
	%test for given value and skip it
	if B(i,j) ~= k
		REM(i,j,k) = 0;
	end;
end;

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function scrub_column(j,k)

global REM B;

%loop for row
for i = 1:9
	%test for given value and skip it
	if B(i,j) ~= k
		REM(i,j,k) = 0;
	end;
end;

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function scrub_box(i,j,k)

global REM B;

%find start of box
i_init = floor((i-1)/3) * 3 + 1;
j_init = floor((j-1)/3) * 3 + 1;

%loop for row
for i1 = i_init:i_init+2
	%loop for column
	for j1 = j_init:j_init+2
		%test for given value and skip it
		if B(i1,j1) ~= k
			REM(i1,j1,k) = 0;
		end;
	end;
end;

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function fill_only_in_square

global REM;

%take the sum of the number of the possible values in each square, squares that can only have one
%value will return 1
[i,j] = find(sum(REM,3) == 1);

%figure out what value these squares should have and fill them with that value
for COUNT = 1:length(i)
	k = find(REM(i(COUNT),j(COUNT),:) == 1);
	set_square(i(COUNT), j(COUNT), k);
end;

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function fill_only_in_row

global REM;

%loop for rows
for i = 1:9
	%loop for value
	for k = 1:9
		%test for a 1
		if sum(REM(i,:,k),2) == 1
			%find the 1
			j = find(REM(i,:,k) == 1);
			set_square(i, j, k);
		end;
	end;
end;

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function fill_only_in_column

global REM;

%loop for columns
for j = 1:9
	%loop for value
	for k = 1:9
		%test for a 1
		if sum(REM(:,j,k),1) == 1
			%find the 1
			i = find(REM(:,j,k) == 1);
			set_square(i, j, k);
		end;
	end;
end;

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function fill_only_in_box

global REM;

%loop for columns
for i = 1:3:8
	%loop for column
	for j = 1:3:8
		%loop for value
		for k = 1:9
			%test for a 1, need 3 sums to get a single value instead of an array
			if sum(sum(sum(REM(i:i+2,j:j+2,k),3),2),1) == 1
				%find the 1, remember that REM is a 3x3 matrix here
				[i1,j1,k1] = find(REM(i:i+2,j:j+2,k) == 1);
				set_square(i+i1-1, j+j1-1, k);
			end;
		end;
	end;
end;

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function print_puzzle(LOOP)

global B;

if LOOP == 100
	fprintf('The sudoku_solver script was unable to finish your sudoku\n');
	fprintf('You probably need to use trial and error to solve it.\n\n');
else
	fprintf('The sudoku_solver script solved your sudoku in only %d loops.\n\n', LOOP);
end;

fprintf('=====================================\n');
for i = 1:9
	fprintf('| %d : %d : %d | %d : %d : %d | %d : %d : %d |\n', B(i,1:9));
	if mod(i,3) == 0
		fprintf('=====================================\n');
	end;
end;

return

https://www.youtube.com/watch?v=NwC1bFQ-cvo