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 endMMM = 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; endendif ~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