Recursively Solving Su Doku using MATLAB

I’ve been solving Sudoku almost daily from quite some time now. Thanks to Times of India for publishing a new puzzle almost every day. Finally, I thought of writing a small program to solve Sudoku Puzzle.

I decided on using MATLAB because of the ease with which it handles Matrices. Also with recursion I can get MATLAB to give all the possible solutions. Although, a well-constructed Sudoku problem usually has one solution but then it is possible to have more than one solution for the same problem.

I have used the traditional Brute Force method to get to the right solution. The program consists of two functions i.e. check_sudoku and run_sudoku to solve the puzzle. The first function checks whether the given Sudoku puzzle has a solution or not (it basically checks that none of the digits in rows, columns and 3x3 square matrix are repeated) and the other one looks for a blank and start filling it with numbers from 1 to 9 checking the puzzle every time a number is filled. This is done recursively till there are no blank spaces left.

To get this program running, just fill Sudoku in to MATLAB with all the missing digits filled with zeroes and then call “run_sudoku” function (it only takes in Sudoku puzzle as the input).

Here is the code (though poorly commented) for the two functions:

%Check Su Doku

function OK = check_sudoku(puzzle)

  OK = true;

  %Checking along the rows

  for r = 1:9

     row = puzzle(r,1:9);

    for n = 1:9

       num_count = 0;

       for c = 1:9

         if(row(c) == n)

           num_count = num_count + 1;

         end

       end

       if(num_count > 1)

         OK = false;

       end

     end

  end

  %Check in Columns

  for co =1:9

     col = puzzle(1:9,co);

     for n = 1:9

       num_count = 0;

       for c = 1:9

         if(col(c) == n)

           num_count = num_count + 1;

         end

       end

       if(num_count > 1)

         OK = false;

       end

     end

  end

  %3x3 Square Matrix Check

  for c_m = 1:3:9

     for i = 1:3:9

       mat = puzzle(i:i+2,c_m:c_m+2);

       for n = 1:9

         num_count = 0;

           for c = 1:3

             for r = 1:3

               if(mat(c,r) == n)

                 num_count = num_count +1;

               end

             end

           end

           if(num_count > 1)

             OK = false;

           end

        end

     end

  end

end

%Run Su Doku

function blank = run_sudoku(puzzle)

  blank = false;

  %look for a blank (0)

  row = 1;

  while(row<=9 && (~blank))

     col = 1;

     while(col <=9 && (~blank))

       if(puzzle(row,col) == 0)

         blank = true;

       else

         col = col + 1;

       end

     end

     if(~blank)

       row = row + 1;

     end

  end

  %Fill in the blank with numbers 1 to 9

  %check the puzzle every time a number is filled

  if(blank)

     for value = 1:9

     puzzle(row,col) = value;

     if(check_sudoku(puzzle))

       run_sudoku(puzzle);

     end

   end

  else

     puzzle

  end

end 

Example Puzzle (You can see that the blanks are filled with zeros):

And this was the ouput -