MATLAB: Suduko solver

recursive backtrackingsudoku

I am trying to write a program/function that will solve a given Sudoku problem. So far I have been successful in solving an easy puzzle (one that is straight forward and requires no guess and check). I believe the the computer science term is recursive backtracking that I am having trouble with, that is I want to guess a number then solve the Sudoku completely and see if the answer is correct if not then guess again. But it is not working this is what I have so far.
function MM = suduko(P,M)
M = P;
% suduko solver: Solves a 9 by 9 standard suduko puzzule
%written by Steven Haim 6/29/2011
% M = [0 0 3 0 2 0 6 0 0
% 9 0 0 3 0 5 0 0 1;
% 0 0 1 8 0 6 4 0 0;
% 0 0 8 1 0 2 9 0 0;
% 7 0 0 0 0 0 0 0 8;
% 0 0 6 7 0 8 2 0 0;
% 0 0 2 6 0 9 5 0 0;
% 8 0 0 2 0 3 0 0 9;
% 0 0 5 0 1 0 3 0 0;]
%
% M = [2 0 0 0 8 0 3 0 0;
% 0 6 0 0 7 0 0 8 4;
% 0 3 0 5 0 0 2 0 9;
% 0 0 0 1 0 5 4 0 8;
% 0 0 0 0 0 0 0 0 0;
% 4 0 2 7 0 6 0 0 0;
% 3 0 1 0 0 7 0 4 0;
% 7 2 0 0 4 0 0 6 0;
% 0 0 4 0 1 0 0 0 3;]
% M = [0 0 0 0 0 0 9 0 7;
% 0 0 0 4 2 0 1 8 0;
% 0 0 0 7 0 5 0 2 6;
% 1 0 0 9 0 4 0 0 0;
% 0 5 0 0 0 0 0 4 0;
% 0 0 0 5 0 7 0 0 9;
% 9 2 0 1 0 8 0 0 0;
% 0 3 4 0 5 9 0 0 0;
% 5 0 7 0 0 0 0 0 0]
tic
%Seperate in to zones
zone1 = M((1:3),(1:3));
zone2 = M((1:3),(4:6));
zone3 = M((1:3),(7:9));
zone4 = M((4:6),(1:3));
zone5 = M((4:6),(4:6));
zone6 = M((4:6),(7:9));
zone7 = M((7:9),(1:3));
zone8 = M((7:9),(4:6));
zone9 = M((7:9),(7:9));
Test = find(M == 0, 1);
if isempty(Test) %Problem solved
if check(zone1,zone2,zone3,zone4,zone5,zone6,zone7,zone8,zone9) == 1 %checks to see if the answer is valid
MM = M;
toc
return
else
M = P;
end
end
MMM = M;
for I = 1:9;
for J = 1:9;
if M(I,J) == 0
switch I && J %Determines which subset to use

case I <= 3 && J <=3
Zoneuse = zone1;
case I <= 3 && J <=6 && J > 3
Zoneuse = zone2;
case I <= 3 && J <=9 && J > 6
Zoneuse = zone3;
case I >= 3 && I<7 && J <=3
Zoneuse = zone4;
case I >= 3 && I<7 && J <=6 && J > 3
Zoneuse = zone5;
case I >= 3 && I<7 && J <=9 && J > 6
Zoneuse = zone6;
case I >= 7 && J <=3
Zoneuse = zone7;
case I >= 7 && J <=6 && J > 3
Zoneuse = zone8;
case I >= 7 && J <=9 && J > 6
Zoneuse = zone9;
end
Rownumbers = M(I,:); %Determines which Rows to use

Colnumber = M(:,J); %Determines which Columns to use

Possible = Candidates(Zoneuse,Rownumbers,Colnumber);
if length(Possible) == 1;
M(I,J) = Possible;
end
end
end
end
if M == MMM %Enters this if statment if requires a guess and check
[I,J] = find(M == 0,1);
switch I && J %Determines which subset to use
case I <= 3 && J <=3
Zoneuse = zone1;
case I <= 3 && J <=6 && J > 3
Zoneuse = zone2;
case I <= 3 && J <=9 && J > 6
Zoneuse = zone3;
case I >= 3 && I<7 && J <=3
Zoneuse = zone4;
case I >= 3 && I<7 && J <=6 && J > 3
Zoneuse = zone5;
case I >= 3 && I<7 && J <=9 && J > 6
Zoneuse = zone6;
case I >= 7 && J <=3
Zoneuse = zone7;
case I >= 7 && J <=6 && J > 3
Zoneuse = zone8;
case I >= 7 && J <=9 && J > 6
Zoneuse = zone9;
end
Rownumbers = M(I,:); %Determines which Rows to use
Colnumber = M(:,J); %Determines which Columns to use
[Possible] = Candidates(Zoneuse,Rownumbers,Colnumber);
for P = 1:length(Possible) %attempt at cycling through guesses
M(I,J) = Possible(P);
if isempty(Test)
return
else
suduko(M);
end
end
end
suduko(M) %recursive call
With these two functions
function Pos = Candidates(Zoneuse,Rownumbers,Colnumbers)
count = 1;
for num = 1:9
A = find(Zoneuse == num, 1);
B = find(Rownumbers == num, 1);
C = find(Colnumbers == num, 1);
if isempty(A) && isempty(B) && isempty(C)
Pos(count) = num;
count = count + 1;
end
end
if ~exist('Pos')
Pos = [0 0 0 0 0];
end
AND
function A = check(zone1,zone2,zone3,zone4,zone5,zone6,zone7,zone8,zone9)
zone1 = sum(sum(zone1));
zone2 = sum(sum(zone2));
zone3 = sum(sum(zone3));
zone4 = sum(sum(zone4));
zone5 = sum(sum(zone5));
zone6 = sum(sum(zone6));
zone7 = sum(sum(zone7));
zone8 = sum(sum(zone8));
zone9 = sum(sum(zone9));
if zone1 == 45 && zone2 == 45 && zone3 == 45 && zone4 == 45 && zone5 == 45 && zone6 == 45 && zone7 == 45 && zone8 == 45 && zone9
A = 1;
else
A = 0;
end
For the three test Sudoku the first one solves no problem. The second one requires guess and check and looks like it solves but it ignores the return function and the third one just doesn't solve…
I don't know if this is the correct place to be asking my question but I thought I give it a shot… If I am doing something dumb and it is easy to fix let me know…!

Best Answer

There are many sudoku files on the FEX, perhaps you could look there: