Suduko solver

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...!

[Walter Roberson]

You missed actually asking a question ;-)

Answer 1

[Sean de Wolski]

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

http://www.mathworks.com/matlabcentral/fileexchange/?term=sudoku