sudokon.m

数独的程序

             % other groups containing this cell
             j = ceil(k/9); i = k - 9*(j-1); % get corresp. col and row index
             c = ceil(i/3)+ 3*(ceil(j/3)-1); % get corresp. box index
             % recall that gr = [gr1 gr2 gr3], to be used as i, j+9, c+18
             p(unique(gr(:,[i j+9 c+18])),d) = 0;   p(k,d) = 1;
          end
       end
    
       tt = sum(p(gr(:,r),:));
       sp2 = find(tt==2); % these are the 'rare' digits in this group;
                         % if their sites also belong to another group,
                     % then this digit should be removed from any other site
                     % in that other group
       sp = [sp2 find(tt==3)]; lsp = numel(sp);
       kk = cell(1,lsp);
       for l = 1:lsp
             d = sp(l);
          k = gr(p(gr(:,r),d)==1,r); kk{1,l} = k;
          j = ceil(k/9); i = k - 9*(j-1); % get corresp. col and row index
          c = ceil(i/3)+ 3*(ceil(j/3)-1); % get corresp. box index
 
          p(k,d) = 0;
          if r<19, % the group is a column or row; the only possible other 
                   % group is a box
             if ~diff(c)
                if any(p(gr(:,18+c),d))
                   if hc(85,3)
                      if action(1)=='h'
                         if r<10
                            fprintf([' ** %g occurs in row %g only ',...
                           'in box %g|%g; remove it elsewhere in box\n'],...
                            d,r,ceil(i(1)/3),ceil(j(1)/3))
                         else
                            fprintf([' ** %g occurs in col %g only ',...
                           'in box %g|%g; remove it elsewhere in box\n'],...
                            d,r-9,ceil(i(1)/3),ceil(j(1)/3))
                         end
                      else , counts(2) = counts(2)+1;
                      end
                   end
                   p(gr(:,18+c),d) = 0;
                end
             end
              
          else     % the group is a box; depending on the exact location of
                   % the sites, the other group may be a row or a column
             if ~diff(i),      % the group is a row
                if any(p(gr(:,i),d))
                   if hc(85,3)
                      if action(1)=='h'
                         fprintf([' ** %g occurs in box %g|%g only',...
                         ' in row %g; remove it elsewhere in row\n'],...
                            d,ceil(i(1)/3),ceil(j(1)/3),i(1))
                      else, counts(4) = counts(4)+1;
                      end
                   end
                   p(gr(:,i),d) = 0;
                end
             elseif ~diff(j), % the group is a column
                if any(any(p(gr(:,j+9),d)))
                   if hc(85,3)
                      if action(1)=='h'
                         fprintf([' ** %g occurs in box %g|%g only',...
                         ' in col %g; remove it elsewhere in col\n'],...
                            d,ceil(i(1)/3),ceil(j(1)/3),j(1))
                      else, counts(3) = counts(3)+1;
                      end
                   end
                   p(gr(:,j+9),d) = 0;
                end   
             end        
          end
          p(k,d) = 1;
       end
                 % if two share the two same sites (or three the
                 % same three), remove all others from those sites.
       for i=1:lsp-1
          for j=i+1:lsp
             kkk = unique([kk{i}(:);kk{j}(:)]);
             switch numel(kkk)
             case 2
                dd = 1:9; dd(sp([i j])) = [];
                if any(any(p(kkk,dd)))
                   if hc(85,3)
                      if action(1)=='h', cid = cellid(kkk).';  
                      fprintf([' ** remove all but %g and %g from cells',...
                      ' %g|%g and %g|%g\n'],sort(sp([i j])),cid(:))
                      else, counts(5)=counts(5)+1;
                      end
                   end
                   p(kkk,dd) = 0; 
                end
             case 3 
                for jj=j+1:lsp
                   kkkk = unique([kkk;kk{jj}(:)]);
                   if numel(kkkk)==3
                      dd = 1:9; dd(sp([i j jj])) = [];
                      if any(any(p(kkkk,dd)))
                         if hc(85,3)
                            if action(1)=='h', cid = cellid(kkkk).';  
                               fprintf([' ** remove all but %g, %g, ',...
                               'and %g from cells %g|%g, %g|%g, and ',...
                               '%g|%g\n'],sort(sp([i j jj])),cid(:))
                            else, counts(6)=counts(6)+1;
                            end
                         end
                         p(kkkk,dd) = 0; 
                      end
                   end
                end
             end
          end
       end
 
       tc = sum(p(gr(:,r),:),2);
       if ~all(tc), ok = 0; return, end %inconcistency: some cell is now empty

       sc = find(tc==1&dg(gr(:,r))==0); %these are the singleton cells in the
                                    % group not yet settled.
       for k=gr(sc,r).'
          d = find(p(k,:)==1); 
            % remove this digit from all the other cells in the three
            % groups containing this cell
          j = ceil(k/9); i = k - 9*(j-1); % get corresp. col and row index
          c = ceil(i/3)+ 3*(ceil(j/3)-1); % get corresp. box index
            % recall that gr = [gr1 gr2 gr3], to be used as i, j+9, c+18
          kk = unique(gr(:,[i j+9 c+18])); p(k,d) = 0;
          if any(any(p(kk,d)))
             p(kk,d) = 0; 
             if hc(85,3)&&action(1)=='h'
                fprintf(' ** select cell %g|%g for digit %g\n',cellid(k),d)
             end
          end
          p(k,d) = 1;
       end
 
       sc = find(tc==2); % these are the cells in the group having exactly
                        % two choices left. If these choices are the same for
                       % two such cells, then the two choices should be removed
                       % from all other cells of any group containing these
                       % two cells.
               % If we are looking for good hints, append the cells in the
               % group having exactly three choices left.
       if action(1)=='h', sc = [sc; find(tc==3)]; end
       lsc3 = numel(sc); kk = gr(sc,r);
       for i=1:lsc3-1
          for j=i+1:lsc3
             ddd = unique([find(p(kk(i),:)),find(p(kk(j),:))]);
             if numel(ddd)==2
                kkk = 1:9; kkk(sc([i j])) = [];
                if hc(85,3)&&action(1)=='h'&&any(any(p(gr(kkk,r),ddd)))
                   fprintf([' ** %g and %g are the only choices in two ',...
                       'cells of ', getgroup(r),';\n'],ddd)
                   fprintf(['   remove these digits from all other cells', ...
                         ' in ', getgroup(r),'.\n'])
                end
                p(gr(kkk,r),ddd) = 0;
             elseif action(1)=='h'&&numel(ddd)<5
                for jj=j+1:lsc3
                   dddd = unique([ddd,find(p(kk(jj),:))]);
                   if numel(dddd)==3
                      kkk = 1:9; kkk(sc([i j jj])) = [];
                      if hc(85,3)&&action(1)=='h'&&any(any(p(gr(kkk,r),dddd)))
                         fprintf([' ** %g, %g and %g are the only choices ',...
                                  'in three cells of ',getgroup(r),';\n'],dddd)
                         fprintf(['   remove these digits from all other',...
                                  ' cells in ', getgroup(r),'.\n'])
                      end
                      p(gr(kkk,r),dddd) = 0;
                   elseif numel(dddd)==4
                      for jjj=jj+1:lsc3
                         if all(ismember(find(p(kk(jjj),:)),dddd))
                            kkk = 1:9; kkk(sc([i j jj jjj])) = [];
                            if hc(85,3)&&action(1)=='h'&&any(any(p(gr(kkk,r),dddd)))
                              fprintf([' ** %g, %g, %g, and %g are the only '...
                            'choices in four cells of ',getgroup(r),';\n'],dddd)
                              fprintf(['   remove these digits from all ',...
                                       'other cells in ',getgroup(r),'.\n'])
                            end
                            p(gr(kkk,r),dddd) = 0;
                        end
                      end
                   end 
                end
             end
          end
       end
    end % for r

    % here is the list of newly found singletons
    ns = find(dg(:)==0&sum(p(1:81,:),2)==1); 
    % terminate this loop as soon as there are newly found singletons (since
    % this loop is repeated only in case we are looking for hints and, in that
    % case, it is easier to understand a suggestion resulting from just the
    % first pass through this loop).
    if ~isempty(ns), break, end
   end % for rep
   if hc(85,3)&&~(action(1)=='h')
      counts(1) = counts(1)+1;
      fprintf('%g:  %grcb, %gbc, %gbr, %gtwo, %gthree',counts),
   end

   if isempty(ns) % try for x-wings
     rbeg = 1; rend = 9; kadd = 9;
     for rs=1:2
      for r=rbeg:rend-1
         sp2 = find(sum(p(gr(:,r),:))==2);
          % these are the 'rare' digits in this group;
         for l=1:numel(sp2)
            d = sp2(l); k = find(p(gr(:,r),d)==1);
            for s=r+1:rend
               if p(gr(k(1),s),d) && p(gr(k(2),s),d)
                  temp = 1:9; temp(k) = [];
                  if ~any(p(gr(temp,s),d)) % can erase d from columns k
                     if hc(85,3), temp1 = p(gr(:,kadd+k),d); end
                     p(gr(:,kadd+k),d) = 0; p(gr(k,[r,s]),d) = 1;
                     if hc(85,3)&&any(temp1-p(gr(:,kadd+k),d)) 
                        if rs==1  
                           fprintf('\n  X-wing for %g at (%g,%g),(%g,%g)',...
                               d,r,k(1),s,k(2))
                           fprintf(['; remove the digit %g elsewhere in',...
                           '\n   columns %g and %g'],...
                               d,k)
                        else 
                           fprintf('\n  X-wing for %g at (%g,%g),(%g,%g)',...
                               d,k(1),r-9,k(2),s-9)
                           fprintf(['; remove the digit %g elsewhere in',...
                           '\n    in rows %g and %g.'],...
                              d,k)
                        end
                     end
                     break
                  end
               end
            end
         end
      end
      rbeg = 10; rend = 18; kadd = 0;
     end
     ns = find(dg(:)==0&sum(p(1:81,:),2)==1); 
     if ~isempty(ns)&&action(1)=='h'&&hc(85,3)
        for k=ns.'
           fprintf('\n ** select cell %g|%g for digit %g', ...
                    cellid(k),find(p(k,:)==1))
        end
        fprintf('\n')
     end
   end % for Xwings

   switch action(1)
 
   case 'h'
      isemptyns=false; if isempty(ns), isemptyns=true; end           
      if hc(85,3), fprintf('\n'), end
      nc = find(sum(pstart-p,2));
      if isempty(nc)&&isemptyns, break, end
      ok = 1;
      if isemptyns||hc(85,2), ok = 2; ns = nc; hc(85,2) = 1; end
      for k=ns(:)'  % replace each new singleton by a star
                    % or each deletable choice by a circle
         A = get(hc(k,1),'String');
         temp = [1 7 13 2 8 14 3 9 15]; 
         if hc(85,2), A(temp(p(k,:)~=pstart(k,:))) = 'o';
         else A(temp(p(k,:)==1)) = '*';
         end
         set(hc(k,1),'String',A,'Fontweight','bold','Foregroundcolor','r')
      end
      if ~isemptyns, break, end
   
   case {'c','a'}
      if isempty(ns), break, end
      lns = length(ns); dns = zeros(lns,1);
      for r=1:lns
         dns(r) = find(p(ns(r),:));
      end
      if hc(85,3)
         j = ceil(ns/9); i = ns - 9*(j-1); % get corresp. col and row index
         ij = [i(:)'; j(:)'];
          
         fprintf(['\n      insert singleton at%2g|%1g%2g|%1g%2g|%1g%2g|', ...
                       '%1g%2g|%1g%2g|%1g%2g|%1g%2g|%1g%2g|%1g%2g|%1g'],ij(:))
         fprintf(['\n        with value       %3g%4g%4g%4g%4g%4g%4g%4g', ...
                                 '%4g%4g'],dns)
         fprintf('\n')
      end
      [dg,p,hc] = rm(ns,dns,dg,p,gr,hc,action);
   end % for switch action(1)
   if all(dg), break, end
end % for tries

if action(1)=='c' || action(1)=='a'
   sz = find(dg==0);
   if isempty(sz), ok = 1;
      if action(1)=='a'
         p(82,1) = p(82,1)+1;
         if action(2)=='p', fprintf('\n solution %g :\n',p(82,1)), disp(dg),
         end 
         ok = 0;
         if p(82,1)==50
            button = questdlg('Continue?',...
            '50 solutions found so far; continue?',...
            'No','Yes','No');
            if button(1)=='N', ok = 1; p(82,1) = -p(82,1); return, end
         end
      end
   else % at some locations, we still don't have a singleton
        % so, find a nonsingleton solution with the smallest number
        % of possibilities and run through each of them until the one
        % that works is found. Note that this could lead to further
        % branchings (and should be set up that way). The trick is to
        % interpret any inconsistency found merely as a wrong choice
        % made along the way, calling for a different choice at an 
        % earlier point.
      
      % find the first digit appearing the least in settled cells,
      % [nm,dig] = min(sum(p(dg>0,:))); sz(~p(sz,dig)) = [];
      % find the first digit appearing the most in unsettled cells,
      [nm,dig] = max(sum(p(sz,:))); sz(~p(sz,dig)) = [];
      % then determine the first shortest nonsingleton containing it:
      [nm,ni] = min(sum(p(sz,:),2)); k = sz(ni);
      j = ceil(k/9); i = k - 9*(j-1); cc = find(p(k,:)>0);
      %  cc(cc==dig)=[]; cc = [dig,cc]; % this attempt didn't work at all
      if hc(85,3)
           fprintf(['\ntry the %g remaining possibilities at location %g|%g:'...
                    '  %g,%g,%g,%g'],nm,i,j,cc)
      end
      for nn=1:nm
         if hc(85,3)
            fprintf('\n   try possibility %g, namely %g, at location %g|%g',...
               nn,cc(nn),i,j)
         end