function X = sudoku(X,show,H)
% SUDOKU  Solve the Sudoku puzzle using recursive backtracking.
%   sudoku(X), for a 9-by-9 array X, solves the Sudoku puzzle for X.
%   sudoku(X,show) with show = 1, 2, 3 or 4 controls the speed of the gui.
%   sudoku(X,1) is the default, click the step button for each step.
%   sudoku(X,0) skips the gui entirely.
%   See also sudoku_puzzle.

   if nargin < 1
      X = sudoku_puzzle(1);
   end
   if nargin < 2
      show = 1;
   end
   if nargin < 3
      H = gui_init(X,show);
   end
   gui(show,X,H,[]);

   % Fill in all "singletons", which are the cells
   % with only one candidate value.
   % C is an array of candidate values for each cell.
   % s is the first cell, if any, with one candidate. 
   % e is the first cell, if any, with no candidates.

   [C,s,e] = candidates(X);
   while ~isempty(s) && isempty(e)
      gui(show,X,H,C);
      X(s) = C{s};
      gui(show,X,H,C);
      [C,s,e] = candidates(X);
   end
   gui(show,X,H,C);
   
   % Recursive backtracking.

   if any(X(:) == 0) && isempty(e)
      Y = X;
      z = find(X(:) == 0,1);       % Index of the first unfilled cell.
      for r = [C{z}]               % Iterate over the candidates.
         X = Y;
         gui(show,X,H,C);
         X(z) = r;                 % Insert a tentative value.
         gui(show,X,H,C,z);        % Color the tentative value.
         X = sudoku(X,show,H);     % Recursive call.
         if all(X(:) > 0)          % Found a solution.
            break
         end
         gui(show,X,H,C,-z);       % Revert color of tentative value.
      end
   end
   if nargin < 3
      gui_finish(show,X,H,C);
   end

% ------------------------------

   function [C,s,e] = candidates(X)
      % C = candidates(X) is a cell array of vectors.
      % C{i,j} is the set of allowable values for X(i,j).
      % s = the first singleton, a cell with only one candidate.
      % e = the first cell with no candidates.
      C = cell(9,9);
      tri = @(k) 3*ceil(k/3-1) + (1:3);
      for j = 1:9
         for i = 1:9
            if X(i,j)==0
               z = 1:9;
               z(nonzeros(X(i,:))) = 0;
               z(nonzeros(X(:,j))) = 0;
               z(nonzeros(X(tri(i),tri(j)))) = 0;
               C{i,j} = nonzeros(z)';
            end
         end
      end
      L = cellfun(@length,C);   % Number of candidates for each cell.
      s = find(X==0 & L==1,1);  % First singleton.
      e = find(X==0 & L==0,1);  % First cell with no candidates.
   end % candidates

% ------------------------------

   function H = gui_init(X,show)

      % Initialize gui

      if show == 0
         H = [];
         return
      end
      dkblue = [0 0 2/3];
      dkgreen = [0 1/2 0];
      dkmagenta = [1/3 0 1/3];
      grey = [1/2 1/2 1/2];
      fsize = get(0,'defaulttextfontsize');
      fname = 'Lucida Sans Typewriter';
      clf
      shg
      set(gcf,'color','white')
      axis square
      axis off
      
      for m = [2 3 5 6 8 9]
         line([m m]/11,[1 10]/11,'color',grey)
         line([1 10]/11,[m m]/11,'color',grey)
      end
      for m = [1 4 7 10]
         line([m m]/11,[1 10]/11,'color',dkmagenta,'linewidth',4)
         line([1 10]/11,[m m]/11,'color',dkmagenta,'linewidth',4)
      end
   
      H.a = zeros(9,9);
      for j = 1:9
         for i = 1:9
            if X(i,j) > 0
               string = int2str(X(i,j));
               color = dkblue;
            else
               string = ' ';
               color = dkgreen;
            end
            H.a(i,j) = text((j+1/2)/11,(10.5-i)/11,string, ...
              'units','normal','fontsize',fsize+6,'fontweight','bold', ...
              'fontname',fname,'color',color,'horizont','center');
         end
      end
      H.b = zeros(1,4);
      strings = {'step','slow','fast','finish'};
      for k = 1:4
         H.b(k) = uicontrol('style','toggle','string',strings{k}, ...
            'units','normal','position',[(k+3)*0.125,0.05,0.10,0.05], ...
            'background','white','value',0,'userdata',k, ...
            'callback','set(gcf,''userdata'',get(gco,''userdata''))');
      end
      set(H.b(1),'style','pushbutton')
      if show > 1
         set(H.b(show),'value',1)
      end
      set(gcf,'userdata',show)
      H.t = title('0','fontweight','bold','userdata',0, ...
         'handlevis','on','tag','steps');
      drawnow

   end % gui_init

% ------------------------------

   function gui(show,X,H,C,z)

      if show == 0
         return
      end
      t = get(H.t,'userdata') + 0.5;
      set(H.t,'userdata',t,'string',int2str(floor(t)));
      button = get(gcf,'userdata');
      if show == 4 && any(X(:) == 0) || button == 0
         return
      end
      k = 1:4;
      k(button) = [];
      set(H.b(k),'value',0);
      dkblue = [0 0 2/3];
      dkred = [2/3 0 0];
      dkgreen = [0 1/2 0];
      cyan = [0 2/3 2/3];
      fsize = get(0,'defaulttextfontsize');

      % Update entire array, except for initial entries.

      for j = 1:9
         for i = 1:9
            if ~isequal(get(H.a(i,j),'color'),dkblue) && ...
               ~isequal(get(H.a(i,j),'color'),cyan)
               if X(i,j) > 0
                  set(H.a(i,j),'string',int2str(X(i,j)),'fontsize',fsize+6, ...
                     'color',dkgreen)
               elseif isempty(C)
                  set(H.a(i,j),'string',' ')
               elseif length(C{i,j}) == 1
                  set(H.a(i,j),'string',char3x3(C{i,j}),'fontsize',fsize-4, ...
                     'color',dkred)
               else
                  set(H.a(i,j),'string',char3x3(C{i,j}),'fontsize',fsize-4, ...
                     'color',dkgreen)
               end
            end
         end
      end
      if nargin == 5
         if z > 0
            set(H.a(z),'color',cyan)
         else
            set(H.a(-z),'color',dkgreen)
            return
         end
      end

      % Gui action = single step, brief pause, or no pause

      switch button
         case 1
            set(gcf,'userdata',0)
            while get(gcf,'userdata') == 0;
               drawnow
            end
         case 2
            pause(0.5)
         case 3
            drawnow
      end
   
      % ------------------------------
   
      function s = char3x3(c)
         % 3-by-3 character array of candidates.
         b = blanks(5);
         s = {b; b; b};
         for k = 1:length(c)
            d = c(k);
            p = ceil(d/3);
            q = 2*mod(d-1,3)+1;
            s{p}(q) = int2str(d);
         end
      end

   end % gui

% ------------------------------

   function gui_finish(show,X,H,C)
 
      if show == 0
         return
      end
      set(H.b(1:3),'vis','off')
      set(H.b(4),'string','close','value',0, ...
         'callback','close(gcf)')
    
   end % gui_finish

end % sudoku