Solving Sudoku in MATLAB | Recursive Backtracking


Human puzzle-solvers and computer programs use very different Sudoku-solving techniques. The fascination with solving Sudoku by hand derives from the discovery and mastery of a myriad of subtle combinations and patterns that provide hints about the final solution. It is not easy to program a computer to duplicate these human pattern-recognition capabilities. For this reason, most Sudoku-solving programs take a very different approach, relying on the computer’s almost limitless capacity to carry out brute-force trial and error.

As you probably know, solving a Sudoku involves filling in a 9-by-9 grid so that each row, column, and major 3-by-3 block contains all the digits 1 through 9. The initial grid is populated with a few digits, known as clues. In contrast to magic squares and other numeric puzzles, no arithmetic is involved; the elements in a Sudoku grid could just as well be letters of the alphabet or any other symbols.

Solving Sudoku with Recursive Backtracking

MATLAB program uses only one pattern—singletons—together with a basic computer science technique, recursive backtracking.

  1. function X = sudoku(X)
  2. % SUDOKU Solve Sudoku using recursive backtracking.
  3. % sudoku(X), expects a 9-by-9 array X.
  4. % Fill in all singletons”.
  5. % C is a cell array of candidate vectors for each cell.
  6. % s is the first cell, if any, with one candidate.
  7. % e is the first cell, if any, with no candidates.
  8. [C,s,e] = candidates(X);
  9. while ~isempty(s) && isempty(e)
  10. X(s) = C{s};
  11. [C,s,e] = candidates(X);
  12. end
  13. % Return for impossible puzzles.
  14. if ~isempty(e)
  15. return
  16. end
  17. % Recursive backtracking.
  18. if any(X(:) == 0)
  19. Y = X;
  20. z = find(X(:) == 0,1); % The first unfilled cell.
  21. for r = [C{z}] % Iterate over candidates.
  22. X = Y;
  23. X(z) = r; % Insert a tentative value.
  24. X = sudoku(X); % Recursive call.
  25. if all(X(:) > 0) % Found a solution.
  26. return
  27. end
  28. end
  29. end
  30. % ------------------------------
  31. function [C,s,e] = candidates(X)
  32. C = cell(9,9);
  33. tri = @(k) 3*ceil(k/3-1) + (1:3);
  34. for j = 1:9
  35. for i = 1:9
  36. if X(i,j)==0
  37. z = 1:9;
  38. z(nonzeros(X(i,:))) = 0;
  39. z(nonzeros(X(:,j))) = 0;
  40. z(nonzeros(X(tri(i),tri(j)))) = 0;
  41. C{i,j} = nonzeros(z)’;
  42. end
  43. end
  44. end
  45. L = cellfun(@length,C); % Number of candidates.
  46. s = find(X==0 & L==1,1);
  47. e = find(X==0 & L==0,1);
  48. end % candidates
  49. end % sudoku

" Thanks for helping me in my Smart Grid MATLAB Assignment. You guys are awesome..! "


Tom Henry
Australia

All Reviews