sudokon.m

数独的程序

function  sudokon(g)
%SUDOKON play sudoku onscreen, starting with the g , if given
%
%   SUDOKON(G) generates a sudoku grid from the given matrix G which is 
%   expected to be a 9-by-9 matrix with entries from {0,1,2,...,9}.
%
%   The object of the game is to select, for each cell not already containing
%   a single, bold, number, a number from 1:9 in such a way that, in each row,
%   in each column, and in each of the nine 3-by-3 cell-boxes, each of the
%   numbers 1:9 appears, hence appears exactly once.
%   In the default mode, each of the cells still to be filled in this way shows 
%   all the choices still possible for it under these constraints.
%   
%   To select one of these numbers for a cell, left-click on it.
%
%   If there is only one choice showing, then left-clicking anywhere in that
%   cell will select that number for the cell.
%
%   If there are no such cells, you need to use reasoning to reduce the number
%   of choices. When you come to the conclusion that one of the choices showing
%   is impossible, delete it by right-clicking on it.
%   
%   To undo the most recent change in a cell, click on it (making sure not to
%   click on any of the choices showing). This will bring up an 'undo' button,
%   and clicking it will undo the most recent change in that cell as well as
%   all other changes made since then.
%   To undo the most recent change in a cell that left it with just one choice
%   you must right-click it (since a left-click would make that single choice
%   your choice for this cell).
%
%   If the cell is already settled, then a (left or right) click on it brings 
%   up the 'undo' button.
%
%   If you are in the clueless mode (see the 'hint?' button described below),
%   then the cells still not settled are blank and clicking one such generates
%   a keyboard of all nine buttons. Clicking on one makes the corresponding 
%   number your choice for this cell provided the choice isn't obviously wrong.
%  
%   SUDOKON(N) with N from 1:12 supplies a puzzle from a list of puzzles, with
%   the same N providing seemingly different puzzles, but their difficulty 
%   increasing with N.
%
%   SUDOKON without any input expects you to enter a puzzle directly into the
%   sudoku board, by left-clicking on available choices.
%   
%   The GUI has the following permanent buttons:
%
%   'hint?':  will cycle through the following three modes:
%             (1) showing nothing in cells not yet settled (the clueless mode);
%             (2) showing the choices still possible in cells not yet settled;
%             (3) showing (if left-clicked) the choice to be selected at some 
%               cells based on the present state of the board, or 
%               (if right-clicked) some choices that can safely be deleted from
%               some cells; either way,  detailed hints are printed in the 
%               command window, provided '...choices; print' (see 'checks...')
%               is set.
%   'check...':  will check whatever is indicated on the button to the right of
%             it, and that button cycles through the following four modes:
%             (1) '...choices made' tells you whether or not all selections
%               (and deletions) made so far are correct;
%             (2) '...choices; print' checks the same thing but also prints in
%               the command window various details (such as the order in which
%               choices were found, and by what rules, to obtain a complete
%               solution, starting at the current board);
%             (3) '...# solutions' will tell you the number of solutions;
%             (4) '...all solutions' will print in the command window all
%             solutions (if any).
%   'save':   will save the current board in a file.
%   'load':   will bring back a board saved earlier.
%   'print':  will send the sudoku board in its current state to the printer,
%             to an eps file, or to the command window.

%  Copyright 2006-2009 Carl de Boor
%  All commercial rights and uses, including the name `sudokon', reserved for
%  Carl de Boor.
%   8-29jan06, 8-13feb06, 22feb06, 24-25feb06, 1-2mar06, 3-7mar06, 23mar06,
%   13jun06, 14jul06, 19sep06, 16oct06, 26nov06, 06feb07, 14feb07, 23feb07,
%   15mar07, 15apr07, 22apr07, 12jun07, 13feb08, 04jun08, 26jul08, 17-20jan09,

if ~nargin||~ischar(g)||nargin>1
   action = 'start';
else
   action = g;
   temp = get(gcf,'Userdata'); 
   [hf,p,dg,gr,hc,hst] = deal(temp{:}); 
end

w = [.09,.0866666666];
switch action

case 'start'

   % set up the display
   
   running = findobj(allchild(0),'tag','sudoku');
   if ~isempty(running), close(running), end

   hf = figure('Toolbar','none','menubar','none',...
   'name','sudokon', ...
   'numbertitle','off',...
   'DockControls','off',...
   'tag','sudoku',...
   'Units','normalized',...
   'DeleteFcn','sudokon ''closefigure''',...
   'Position',[.05,.05,.55,.65]);
       
   hc = zeros(85,4);

   ismall = .01; ilarge = .02;
   w3 = 3*(w+ismall)+ilarge;
   xoff = .03; yoff=.94; % 3*w3(2) + yoff = 1
   A = ['1 2 3';'4 5 6';'7 8 9'];
   k = 0;
   for j1=0:2
    for j2=1:3
     for i1=0:2
      for i2=1:3
          k = k+1;
          x = xoff+j1*w3(1)+(j2-1)*(w(1)+ismall); 
          y = yoff-i1*w3(2)-i2*(w(2)+ismall);
         hc(k,[2 3]) = [x,y]+w/2;
         hc(k,1) = uicontrol('Parent',hf,...
          'BackgroundColor',[1 1 1],...
          'ForegroundColor','k',...
          'FontName','FixedWidth',...
          'Fontsize',10,'Fontweight','normal','Style','text',...
          'ButtonDownFcn','sudokon ''works''',...
          'Enable','inactive',...
          'Units','normalized',...
          'Position', [x+.006,y,w(1)-.012,w(2)], ...
          'string',A,'Userdata',k);
      end
     end
    end
   end

      % set up an axes, to plot the sudoku grid when printing
   axes('Parent',hf, ...
              'ButtonDownFcn','sudokon ''works''',...
              'Position',[0 0 1 1]);
      % it seems best to pick the grid directly from the cells just set up
   temp = 1:12; temp([1 5 9 12]) = [];
   xx = zeros(12,1); xx(temp) = (hc(10:9:73,2)+hc(1:9:64,2))/2; 
   ofn = [1 5 9]; ofs = [1 4 7];
   xx(ofn) = 2*hc(ofs*9-8,2) - xx(ofn+1);
   xx(ofn+3) = 2*hc(ofs*9+10,2) - xx(ofn+2);
   yy = zeros(12,1); yy(temp) = (hc(2:9,3)+hc(1:8,3))/2; 
   yy(ofn) = 2*hc(ofs,3) - yy(ofn+1);
   yy(ofn+3) = 2*hc(ofs+2,3) - yy(ofn+2);
   temp = reshape(repmat(1:12,3,1),1,36);
   hc(83,4) = line('Xdata',[repmat([xx([1 end]);NaN],12,1); xx(temp)], ...
                   'Ydata',[yy(temp);repmat([yy([1 end]);NaN],12,1)], ...
                   'Linewidth',.5,'Visible','off');
   axis off

   % set up the background button for doing nothing
   hc(82,4) = uicontrol('Parent',hf,...
       'Style','Pushbutton',...
       'Tooltipstring','don''t do anything',...
       'Units','normalized', ...
       'Callback','sudokon ''donot''',...
       'Visible','off');

   % set up the button for undo'ing the most recent change in a cell
   % and all other changes since then elsewhere
   % ( hc(82,1:2) have become unused )
   hc(82,3) = uicontrol('Parent',hf,...
      'Style','Pushbutton',...
      'Tooltipstring',...
      'return to situation just before the last action on this cell',...
      'Units','normalized',...
      'String','undo',...
      'Callback','sudokon ''undo''',...
      'Visible','off');
       % 'FontName','FixedWidth',...

   % start the list of possibilities
   
   p = ones(82,9);

   % ... and the 3x3 key board
   for j=1:9
      p(82,j) = uicontrol('Parent',hf,...
         'Units','normalized',...
         'Visible','off',...
         'String',num2str(j),...
         'Tooltipstring','click to delete',...
         'Style','Pushbutton');
   end

   % ... and the 6 buttons
   for j=1:3
      hc(83,j) = uicontrol('Parent',hf,...
         'Units','normalized', ...
         'BackgroundColor',[1 1 1],...
         'FontName','FixedWidth',...
         'Style','Pushbutton');
      hc(84,j) = uicontrol('Parent',hf,...
         'Units','normalized', ...
         'BackgroundColor',[1 1 1],...
         'FontName','FixedWidth',...
         'Style','Pushbutton');
   end

   set(hc(83,1),'ButtonDownFcn','sudokon ''hints''',...
          'Enable','inactive',...
          'Tooltipstring','cycles through levels of help',...
          'Position', [hc(1,2)-w(1)/2,.97,w(1),.029], ...
          'string','hint?');
   set(hc(83,2),'Callback','sudokon ''prints''',...
          'Tooltipstring','prints current sudoku board',...
          'Position', [hc(19,2)-w(1)/2,.9375,w(1),.029],...
          'string','print');
   set(hc(83,3),'Callback','sudokon ''checks''',...
          'Tooltipstring','checks consistency of choices made so far',...
          'Userdata','click on empty cell for selection',...
          'Position', [hc(10,2)-w(1)/2,.97,w(1),.029],...
          'string','check...');
   set(hc(84,1),'Callback','sudokon ''save''',...
          'Userdata',0,...
          'Position', [hc(1,2)-w(1)/2,.9375,w(1),.029], ...
          'Tooltipstring','saves current board in a file','String','save')
   set(hc(84,2),'Callback','sudokon ''load''',...
          'Userdata','left/right-click to select/delete',...
          'Position', [hc(10,2)-w(1)/2,.9375,w(1),.029], ...
          'Tooltipstring','brings back a board saved earlier','String','load')
   set(hc(84,3),'Callback','sudokon ''prefer''',...
          'Userdata',1, ...
          'Position', [hc(19,2)-w(1)*.51,.97,w(1)*2.4,.029], ...
          'Tooltipstring','sets what to check for',...
          'HorizontalAlignment','left',...
          'String','...choices made')
          % Horizontal Alignment will not work in a Windows environment

   hc(85,1) = uicontrol('Parent',hf,...
          'BackgroundColor',[1 1 1],...
          'FontName','FixedWidth',...
          'Style','Text',...
          'Visible','on',...
          'Fontweight','bold',...
          'Units','normalized', ...
          'Position', [(hc(46,2)+hc(55,2))/2-.2,.94,.5,.057], ...
          'Userdata','The current selection is inconsistent',...
          'String',get(hc(84,2),'Userdata'));
          % 'Position', [(hc(46,2)+hc(55,2))/2-.3,.94,.6,.057], ...
          
      % if hc(85,2), then choices to be removed rather than singleton
      %              suggestions are shown when hints are asked for and,
      %              if there is printing, more details are printed.

   % initiate the solution matrix
   
   dg = zeros(9,9);
   
   % construct the 27 groups
   
   gr2 = repmat((1:9).',1,9) + repmat(0:9:80,9,1); % its columns are the columns
   gr1 = gr2.'; % its columns are the rows
   gr3 = repmat([1:3, 10:12, 19:21].',1,9) + ...
         repmat([0 3 6 27 30 33 54 57 60],9,1);
                % its columns are the 3-by-3 cells
   
   gr = [gr1 gr2 gr3]; % to be used as i, j+9, c+18
   
   % initiate history

   hst = zeros(0,3);

   % generate the list of given singletons
   
   if nargin
      if numel(g)==1
              g = examples(g);
      else % check that the given input is 9x9 with range 1:9
         if ~isequal(size(g),[9,9])
            delete(findobj(allchild(0),'name','sudokon'))
            error('the input matrix should be of size [9,9]')
         end
         if issparse(g)
            g = full(g);
         end
         d = unique(g);
         d(d==0|d==1|d==2|d==3|d==4|d==5|d==6|d==7|d==8|d==9)=[];
         if ~isempty(d)
            delete(findobj(allchild(0),'name','sudokon'))
            error('the entries of the input matrix should all be from 0:9')
         end
      end

      s = find(g);
      if hc(85,3), fprintf('Insert the given values\n')
      end
      [dg,p,hc] = rm(s,g(s),dg,p,gr,hc);
      hst = [zeros(length(s),1),s,g(s)];
   end
   
   % prevent access to uicontrols and figure by others
   set(hf,'HandleVisibility','callback')

case 'checks'
               % get(hc(84,3),'Userdata')          action
               %        1                check correctness
               %        2                check correctness and print detail
               %        3                check number of solutions
               %        4                print all solutions (if any)

   set(hc(85,1),'Visible','off')
   switch get(hc(84,3),'Userdata')
   case {1,2}
      ok = checkit(dg,p,gr,hc,action);
      if ~ok, set(hc(85,1),'String',get(hc(85,1),'Userdata'))
      else 
         set(hc(85,1),'String','All choices made so far are correct')
      end
   case 3
      pp = p; pp(82,1) = 0;
      [ignored,ignored,pp] = checkit(dg,pp,gr,hc,'allsols');
      if pp(82,1)==1, mess = sprintf('There is exactly one solution.');
      elseif pp(82,1)<0
         mess = sprintf('There are at least %g solutions.',-pp(82,1));
      else  mess = sprintf('There are exactly %g solutions.',pp(82,1));
      end
      set(hc(85,1),'String',mess)
   case 4
      pp = p; pp(82,1) = 0; checkit(dg,pp,gr,hc,'ap'); 
   end
   set(hc(85,1),'Visible','on')

case 'hints'

   if hc(85,4)>0  % we are in the end game, so, simply turn on the cells not