sudoku_solve(action,map,tee)

function sudoku_solve(action,map,tee)
% Sudoku Solver
% sudoku_solve(action,map,[tee])
% Func : sudoku_makemap

% Set constants.
c1 = [0 0 0 3 3 3 6 6 6];
c2 = [1 2 3 1 2 3 1 2 3];
c3 = [1 1 1 2 2 2 3 3 3];

% Initialize.
tic, flops(0)
d = [];
h = [0,0,0,0];

% Set table.
if nargin < 3
   tee = cell(9,9);
   for k1 = 1:9
      u1 = map(k1,:);
      for k2 = 1:9
         if map(k1,k2) == 0
            u2 = map(:,k2);
            u3 = map(c1(k1)+(1:3),c1(k2)+(1:3));
            ut = [u1(:); u2; u3(:)];
            for k3 = 1:9, if ~any(ut == k3), tee{k1,k2}(end+1) = k3; end, end
            if length(tee{k1,k2}) == 1, d(end+1,:) = [k1 k2]; end
         end
      end
   end
end

while ~all(map(:))
   
   h(1) = h(1)+1;
   
   % Eliminate singles in rows.
   for k1 = 1:9
      [s,t] = singles(tee(k1,:));
      for k2 = 1:length(t)
         tee{k1,t(k2)} = s(k2);
         d(end+1,:)    = [k1 t(k2)];
      end
   end
   
   % Eliminate hidden singles in rows.
   for k1 = 1:9
      [s,t] = hsingles(tee(k1,:));
      for k2 = 1:length(t)
         tee{k1,t(k2)} = s(k2);
         d(end+1,:)    = [k1 t(k2)];
      end
   end
   
   % Eliminate hidden singles in columns.
   for k1 = 1:9
      [s,t] = hsingles(tee(:,k1));
      for k2 = 1:length(t)
         tee{t(k2),k1} = s(k2);
         d(end+1,:)    = [t(k2) k1];
      end
   end
   
   % Eliminate hidden singles in boxes.
   for k1 = 0:3:6
      for k2 = 0:3:6
         [s,t] = hsingles(tee(k1+(1:3),k2+(1:3)));
         for k3 = 1:length(t)
            u1         = k1+c2(t(k3));
            u2         = k2+c3(t(k3));
            tee{u1,u2} = s(k3);
            d(end+1,:) = [u1 u2];
         end
      end
   end
   
   if ~isempty(d)
      
      % Chain elimination.
      while ~isempty(d)
         m      = d(1,1);
         n      = d(1,2);
         d(1,:) = [];
         if ~isempty(tee{m,n})
            map(m,n) = tee{m,n};
            tee{m,n} = [];
            
            for k1 = 1:9
               if ~isempty(tee{k1,n}) & any(tee{k1,n} == map(m,n))
                  tee{k1,n} = remove(tee{k1,n},map(m,n));
                  if length(tee{k1,n}) == 1, d(end+1,:) = [k1 n]; end
               end
            end
            for k1 = 1:9
               if ~isempty(tee{m,k1}) & any(tee{m,k1} == map(m,n))
                  tee{m,k1} = remove(tee{m,k1},map(m,n));
                  if length(tee{m,k1}) == 1, d(end+1,:) = [m k1]; end
               end
            end
            for k1 = c1(m)+(1:3)
               for k2 = c1(n)+(1:3)
                  if ~isempty(tee{k1,k2}) & any(tee{k1,k2} == map(m,n))
                     tee{k1,k2} = remove(tee{k1,k2},map(m,n));
                     if length(tee{k1,k2}) == 1, d(end+1,:) = [k1 k2]; end
                  end
               end
            end
         end
      end
   else
      
      stop = sum(h(2:3));
      
      % Check locked candidates.
      [tee,h0] = sudoku_lock(tee);
      h(2)     = h(2)+h0;
      
      % Check hidden pairs in rows, columns and boxes.
      [tee,h0] = sudoku_hpairs(tee);
      h(3)     = h(3)+h0;
      
      if stop == sum(h(2:3)), break, end
   end
end

% Display results.
switch action,
case 'gui'
   sudoku_makemap(map,tee);
otherwise
   for k = 1:9, disp(sprintf('%s',int2str(map(k,:)))); end
   disp(' ');
   disp(sprintf('Locked candidates : %d',h(2)));
   disp(sprintf('Hidden pairs      : %d',h(3)));
   disp(sprintf('Guesses made      : %d',h(4)));
   disp(sprintf('Difficulty        : %d',sum([1,2,4,8].*h)));
   disp(sprintf('Number of kflops  : %.2f',flops/1e3));
   disp(sprintf('Elapsed time      : %.2f',toc));
   disp(' ');
end

% FUNCTIONS

function [s,t] = singles(T)

s = [];
t = [];
for k = 1:9
   if length(T{k}) == 1
      s(end+1) = T{k};
      t(end+1) = k;
   end
end

function [s,t] = hsingles(T)

u1 = zeros(1,9);
u2 = zeros(1,9);
for k = 1:9
   u1(T{k}) = u1(T{k})+1;
   u2(T{k}) = k;
end
s = find(u1 == 1);
t = u2(s);

function v = remove(v,u)

v(find(v == u)) = [];

% SUDOKU_LOCK

function [tee,h0] = sudoku_lock(tee)

c1 = zeros(9,9);
c2 = [1:9];

h0 = 0;
for k1 = 0:3:6
   for k2 = 0:3:6
      T            = tee(k1+(1:3),k2+(1:3));
      U            = c1;
      for k3 = 1:9, U(k3,T{k3}) = 1; end
      m1           = c2;
      m1(k1+(1:3)) = [];
      m2           = c2;
      m2(k2+(1:3)) = [];
      for k3 = find(sum(U,1) > 0)
         u = reshape(U(:,k3),3,3);
         v = find(sum(u,1) > 0);
         if length(v) == 1
            for k4 = m1
               if ~isempty(tee{k4,k2+v}) & any(tee{k4,k2+v} == k3)
                  tee{k4,k2+v} = remove(tee{k4,k2+v},k3);
                  h0           = h0+1;
               end
            end
         end
         v = find(sum(u,2) > 0);
         if length(v) == 1
            for k4 = m2
               if ~isempty(tee{k1+v,k4}) & any(tee{k1+v,k4} == k3)
                  tee{k1+v,k4} = remove(tee{k1+v,k4},k3);
                  h0           = h0+1;
               end
            end
         end
      end
   end
end

% SUDOKU_HPAIRS

function [tee,h0] = sudoku_hpairs(tee)

c1 = [1 2 3 1 2 3 1 2 3];
c2 = [1 1 1 2 2 2 3 3 3];

h0 = 0;
for k1 = 1:9
   [s,t] = hpairs(tee(k1,:));
   for k2 = 1:length(t)
      if length(tee{k1,t(k2)}) > 2
         tee{k1,t(k2)} = s(k2,:);
         h0            = h0+1;
      end
   end
end
for k1 = 1:9
   [s,t] = hpairs(tee(:,k1));
   for k2 = 1:length(t)
      if length(tee{t(k2),k1}) > 2
         tee{t(k2),k1} = s(k2,:);
         h0            = h0+1;
      end
   end
end
for k1 = 0:3:6
   for k2 = 0:3:6
      [s,t] = hpairs(tee(k1+(1:3),k2+(1:3)));
      for k3 = 1:length(t)
         u1 = k1+c1(t(k3));
         u2 = k2+c2(t(k3));
         if length(tee{u1,u2}) > 2
            tee{u1,u2} = s(k3,:);
            h0         = h0+1;
         end
      end
   end
end

function [s,t] = hpairs(T)

U = zeros(9,9);
for k = 1:9, U(k,T{k}) = 1; end
m = find(sum(U,1) == 2);

s    = [];
t    = [];
c    = zeros(1,9);
c(m) = 1;
for k = 1:length(m)
   u = c.*(transpose(U(:,m(k)))*U);
   if length(find(u == 2)) == 2
      v            = find(u == 2);
      s(end+1,:)   = v;
      s(end+1,:)   = v;
      t(end+(1:2)) = find(U(:,m(k)) == 1);
      c(v)         = 0;
   end
end

% SUDOKU_GUESS

function g = sudoku_guess(tee)

for k1 = 1:9, for k2 = 1:9, U(k1,k2) = ~isempty(tee{k1,k2}); end, end

u  = find(U);
r1 = randint(1,1,[1,length(u)]);
t  = u(r1);

s  = tee{t};
r2 = randint(1,1,[1,length(s)]);

g  = [1+rem(t-1,9),1+floor((t-1)/9),s(r2)];