Solving Soduko in Matlab

Sudoku is a solitaire game involving combinatorics. For the rules visit sudoku.com. According to some mathematician and his computer enumeration there are 9!×72²×2⁷×27,704,267,971 different sudoku puzzles - the last factor being prime.

Update: This super brief source code was communicated to me by a math professor.

function Y=sudoku(X)

if ~nargin
  X=[  
    0 2 0 0 3 0 0 4 0
    6 0 0 0 0 0 0 0 3
    0 0 4 0 0 0 5 0 0  
    0 0 0 8 0 6 0 0 0
    8 0 0 0 1 0 0 0 6
    0 0 0 7 0 5 0 0 0  
    0 0 7 0 0 0 6 0 0
    4 0 0 0 0 0 0 0 8
    0 3 0 0 4 0 0 2 0
  ];
end

E=eye(9);
e=eye(3);
O=ones(9);
o=ones(3);

K=kron(E,O)|kron(O,E)|kron(e,kron(o,kron(e,o)));

lhs=X(:)*o(:)';
rhs=O(:)*(1:9);
P=1.0*K*(lhs==rhs);

[m,k]=min(~P*o(:)+10*X(:));
Y=X*(m>9);
E(:)=1:81;
for i=find(m>0 & m<10 & ~P(k,:))
  Y=sudoku(X+i*(E==k));
  if Y
    return
  end
end

Below is my own straightforward implementation:

We provide a simple Matlab function sudoku.m to find all solutions to a given sudoku puzzle. Furthermore, the code decides if the puzzle is fiendish, i.e. if branching is necessary.

The code can be naively modified to generate your own puzzles: From an initially full array, successivly delete an entry while the puzzle implies yet uniquely the initially array. Good puzzles are those with few entries given. The current record is 17, i.e. there is a puzzle with 17 initial entries that yet has a unique solution.

Here is the listing of sudoku.m:

function SOLUTIONS=sudoku(PUZZLE)
%Retrieves all solutions to the sudoku given by PUZZLE.
% PUZZLE    is a 9x9 matrix with 0's as the missing entries
% SOLUTIONS is a 1xN cell where SOLUTIONS{i} is the i-th solution.
%
%Example: P=[0 4 0 0 0 5 1 0 0
%            5 6 0 0 0 3 0 0 2
%            0 0 2 6 0 8 0 0 4
%            7 0 5 0 0 0 0 3 0
%            0 0 0 0 0 0 0 0 0
%            0 1 0 0 0 0 5 0 7
%            2 0 0 9 0 6 4 0 0
%            3 0 0 8 0 0 0 2 6
%            0 0 6 4 0 0 0 8 0];
%         S=sudoku(P);
%         then S is a 1x1 cell and
%         S{1}=[8 4 7 2 9 5 1 6 3
%               5 6 1 7 4 3 8 9 2
%               9 3 2 6 1 8 7 5 4
%               7 8 5 1 6 4 2 3 9
%               4 2 3 5 7 9 6 1 8
%               6 1 9 3 8 2 5 4 7
%               2 5 8 9 3 6 4 7 1
%               3 7 4 8 5 1 9 2 6
%               1 9 6 4 2 7 3 8 5];

global SOLUTIONS
SOLUTIONS=cell(0);

jisudoku(PUZZLE)
function jisudoku(PUZZLE)
global SOLUTIONS

A=cell(9); num=zeros(9); %---initialize---
[X,Y]=meshgrid([0 0 0 3 3 3 6 6 6],[0 0 0 1 1 1 2 2 2]);
T=X+Y+1;
I=repmat(find(T==1),[1 9])+repmat([0 3 6 27 30 33 54 57 60],[9 1]);

%---list available elements for free entries,
%   i.e. unique in row/column/field
for c1=1:numel(PUZZLE)
  x=ceil(c1/9);
  y=mod(c1-1,9)+1;
  if ~PUZZLE(y,x)
    A{c1}=1:9;
    A{c1}=setdiff(A{c1},PUZZLE(:,x));
    A{c1}=setdiff(A{c1},PUZZLE(y,:));
    A{c1}=setdiff(A{c1},PUZZLE(I(:,T(y,x))));
  end
  num(c1)=numel(A{c1});
end
  
if any(any(~num&~PUZZLE))%---free entry but no available => quit!  
  return
end
  
[y,x]=find(num==1);      %---exactly one available => put!
if length(x)
  for c1=1:length(x)
    PUZZLE(y(c1),x(c1))=A{y(c1),x(c1)};
  end
  jisudoku(PUZZLE);
  return
end

cnt=0;
for c1=1:9               %---forall 3x3 fields
  u=[];
  for c2=I(:,c1)'        %----collect availables 
    u=[u A{c2}];
  end
  [u,U]=jiunique(u);  
  if length(intersect(1:9,[u PUZZLE(I(:,c1))']))<9
    %---union in field of available & occupied != 1:9 => quit!
    return
  end
  for c3=find(U==1)      %---entry with unique available => put!
    for c2=I(:,c1)'
      if ismember(u(c3),A{c2})
        PUZZLE(c2)=u(c3);
        cnt=cnt+1;        
      end
    end
  end
end

if cnt
  jisudoku(PUZZLE);
  return
end

if all(all(PUZZLE))      %---found solution
  disp('solution')
  SOLUTIONS{numel(SOLUTIONS)+1}=PUZZLE;
else  
  [mv,mp]=min(reshape(num+10*~~PUZZLE,[1 81]));
  disp('fiendish')
  for c1=A{mp}
    PUZZLE(mp)=c1;
    jisudoku(PUZZLE);
    PUZZLE(mp)=0;
  end
end

function [u,U,I,J]=jiunique(x)
  [u,I,J]=unique(x);
  o=ones(size(x));
  U=full(sparse(o,J,o));

Ich habe so lange ein Motivationsproblem,
bis ich ein Zeitproblem habe.