% sudoku, the game in matlab
% copywrite Stefan Bleeck 2005
% bleeck@gmail.com


% strategy: there are two ways to find out a solution. The first I call the
% "possibles" Each cell is tested which entries it _can_ have. If it only
% has one option, then this is it and it will be displayed in small green
% the other is the "necessary" entry, which is defined by when the other
% squares around it define this as the only possible entry. this is defined
% by crossing out all not possible options and see if there is only one
% left.
% the solver uses both in turn. If no more possible or necessary are found
% then the solver guesses one entry (the one with the least options) and
% goes recursivly through the tree until if ends in an
% impossible situation or with a solution. If it ends impossible, it jumpes
% back up and tries the next option.


% parameter structure:
% sudoku_data.entry_value(1:9,1:9) = state
% sudoku_data.number_possible(1:9,1:9)nr pencilmarks
% sudoku_data.possible_entries(1:9,1:9,1:9)= pencilmarks
% sudoku_data.necessary_entries(1:9,1:9) = necessary entries

function sudoku(params,command)
global sudoku_data;
global fignr;
global data_history;
global current_step;
global max_step;

if nargin<1
    params=parameter('sudoku controls');
    params=add(params,'panel','modify',4);
    params=add(params,'button','empty puzzle','sudoku(params,''make new'')');
    params=add(params,'filename','file name','sudoku_saved');
    params=add(params,'button','save puzzle','sudoku(params,''save'')');
    params=add(params,'button','load puzzle','sudoku(params,''load'')');
    %     params=add(params,'bool','show pencilmarks',1);

    params=add(params,'panel','generate',2);
    params=add(params,'pop-up menu','difficulty',{'difficult','mild','easy'},2);
    params=add(params,'button','generate puzzle','sudoku(params,''generate new'')');

    params=add(params,'panel','help and solve',4);
    params=add(params,'button','check possible','sudoku(params,''check possible'')');
    params=add(params,'button','check necessary','sudoku(params,''check necessary'')');
    params=add(params,'button','hide hints','sudoku(params,''hide hints'')');
    params=add(params,'button','solve','sudoku(params,''solve'')');

    params=add(params,'panel','control',2);
    params=add(params,'button','go forward','sudoku(params,''go forward'')');
    params=add(params,'button','go back','sudoku(params,''go back'')');

    % display an empty one at the beginning
    sudoku(params,'make new');

    params=setposition(params,'northeast');
    parametergui(params);
    movegui('northeast');
    
    return
end

if isequal(command,'save')
    filename=get(params,'file name');
    save(filename,'sudoku_data');
    return
end

if isequal(command,'load')
    clear sudoku_data
    filename=get(params,'file name');
    load(filename,'sudoku_data');

    fignr=234234;
    figure(fignr);
    set(gcf,'keypressfcn',@presskeysudoku);
    set(gcf,'WindowButtonDownFcn',@pressbuttonsudoku);
    set(gcf,'units','normalized');
    current_step=1;
    max_step=1;
    data_history{1}=sudoku_data;
    sudoku(params,'hide hints');
    plot_sudoku(sudoku_data);
    return
end

if isequal(command,'make new')
    sudoku_data.entry_value=zeros(9,9);  % all fixed values
    sudoku_data.number_possible=zeros(9,9);    % number of pencilmarkers
    sudoku_data.possible_entries=zeros(9,9,9);  % pencilmarkers for each square
    sudoku_data.necessary_entries=zeros(9,9);  % necessary (forced) entries for each square
    sudoku_data.current_selected_i=0;
    sudoku_data.current_selected_j=0;
    current_step=1;
    max_step=1;
    data_history{1}=sudoku_data;

    fignr=234234;
    figure(fignr);
    set(gcf,'name','Sudoku');
    set(gcf,'keypressfcn',@presskeysudoku);
    set(gcf,'WindowButtonDownFcn',@pressbuttonsudoku);
    set(gcf,'units','normalized');

    plot_sudoku(sudoku_data);
    return
end


if isequal(command,'generate new')
    % ingenious idea to avoid not unique ones: solve it and transposed. If the
    % same then high probability that they are unique
    global recursion_depth;

    unique=0;
    while ~unique
        recursion_depth=0;
        sudoku_data=fill_random;% generate a filled puzzle
        switch get(params,'difficulty')
            case 'easy'
                sudoku_data=delete_random(sudoku_data,5,2);
            case 'mild'
                sudoku_data=delete_random(sudoku_data,6,2);
            case 'difficult'
                sudoku_data=delete_random(sudoku_data,7,2);
        end

        dr1=solver(sudoku_data);
        dr2=solver(sudoku_data');
        dr2=dr2';

        % if identical then unique
        if sum(sum(dr1.entry_value==dr2.entry_value)) == 81
            unique=1;
%         else
%             sum(sum(dr1.entry_value==dr2.entry_value))
        end
    end
    sudoku(params,'hide hints');
    plot_sudoku(sudoku_data);
    return
end

if isequal(command,'check necessary')
    sudoku_data=check_necessary(sudoku_data);
    plot_sudoku(sudoku_data);
    return
end

if isequal(command,'check possible')
    sudoku_data=check_possible(sudoku_data);
    plot_sudoku(sudoku_data);
end

if isequal(command,'hide hints')
    sudoku_data.number_possible=zeros(9,9);    % number of pencilmarkers
    sudoku_data.possible_entries=zeros(9,9,9);  % pencilmarkers for each square
    sudoku_data.necessary_entries=zeros(9,9);  % necessary (forced) entries for each square
    plot_sudoku(sudoku_data);
end

if isequal(command,'go back')
    if current_step>1
        current_step=current_step-1;
        sudoku_data=data_history{current_step};
        plot_sudoku(sudoku_data);
        sudoku(params,'hide hints');
    end
end

if isequal(command,'go forward')
    if current_step<max_step
        current_step=current_step+1;
        sudoku_data=data_history{current_step};
        plot_sudoku(sudoku_data);
        sudoku(params,'hide hints');
    end
end


if isequal(command,'solve')
    global recursion_depth;
    recursion_depth=0;
    [sudoku_data,solved]=solver(sudoku_data);
    if solved
        plot_sudoku(sudoku_data);
    else
        disp('not solved!');
    end
    sudoku(params,'hide hints');
    plot_sudoku(sudoku_data);
end



function [solve_r,solved] = solver(solve_r)
% Copyright Stefan Bleeck 2005
% Solves the whole thing by going through first checking possibles and then
% checking necessary and filling them in. If a point is reached where it is
% stuck, go recursive.

global recursion_depth, global recursion_saved;

if isempty(recursion_depth) recursion_depth = 0; end

recursion_depth = recursion_depth+1;
solved = 0;

while ~solved
	sumbefore = sum(sum(solve_r.entry_value));
	solve_r = check_possible(solve_r);
	solve_r = check_necessary(solve_r);

	% check if anything is found
	fpos1 = find(solve_r.number_possible == 1);
   if ~isempty(fpos1) % cells with only one possible entry
   	u = solve_r.possible_entries(:,:,1);
      solve_r.entry_value(fpos1) = u(fpos1);
      end
   fnec = find(solve_r.necessary_entries > 0);
   if ~isempty(fnec) % necessary ones
      solve_r.entry_value(fnec) = solve_r.necessary_entries(fnec);
   end
  	
   sumafter = sum(sum(solve_r.entry_value));
   if sumafter == sumbefore % no change - go recursive with one more filled in
 		% find one with the fewest options
      minopt=min(min(solve_r.number_possible(find(solve_r.number_possible>0))));
   	if isempty(minopt) % the solution was not found in this recursion
      	solved = 0;
         recursion_depth = recursion_depth-1;
         return % up one level
		end
     	for i = 1:9
      	for j = 1:9
         	if solve_r.number_possible(i,j) == minopt
            	rn = solve_r; % work in a copy
               for k = 1:minopt % it must be one
               	rn.i = i; rn.j = j; rn.k = k; rn.minopt = minopt;
                  recursion_saved{recursion_depth} = rn;
                  rn.entry_value(i,j)=rn.possible_entries(i,j,k); % try that one
                  [rn,solved] = solver(rn); % find recursively
                  if solved
							solve_r = rn; % that was the solution      
                     return
                  else % carry on ...
							rn = recursion_saved{recursion_depth};  % next try                            
							i = rn.i; j = rn.j; k = rn.k; minopt = rn.minopt;
                  end
           		end                        
             % if here, no solution was found in this branch - go back
               solved = 0;
               recursion_depth = recursion_depth-1;
               return   
				end
        	end
   	end
   end
 	if sum(sum(solve_r.entry_value)) == 405
       solved = 1;
   end
end % - while loop

% ***********************************************************************

function sudoku_data=check_possible(sudoku_data)
% For each cell, counts the number of possible entries by checking the row,
% column and sub-square that contain it. Bleek's function needs an additional
% condition to avoid invalid entries.

sudoku_data.number_possible=zeros(9,9); % clear results
sudoku_data.possible_entries=zeros(9,9,9); % clear results

v = sudoku_data.entry_value; % use a copy

for i = 1:9
	for j = 1:9
      count=1;
      xx = 0;
		for x = 1:9 % the number we are looking at
			if v(i,j) == 0
				is_possible=1;
				if is_possible % check its row
					if ~isempty(find(v(i,:) == x)) is_possible = 0; end
				end
				if is_possible % check its column
					if ~isempty(find(v(:,j) == x)) is_possible = 0; end
				end
				if is_possible % check its sub-square

					ii = 3*fix((i-1)/3)+1;
					jj = 3*fix((j-1)/3)+1;
					if ~isempty(find(v(ii:ii+2,jj:jj+2) == x)) is_possible = 0; end
				end
				if is_possible
               sudoku_data.possible_entries(i,j,count) = x;
               xx = x;
					count=count+1;
				end
			end
      end
      count = count-1;
      sudoku_data.number_possible(i,j) = count;
      if count == 1
  		% update v to avoid invalid entries in later cells
        v(i,j) = xx; 
      end
	end
end


% ***********************************************************************

function sudoku_data = check_necessary(sudoku_data);
% For each number, checks every cell for necessary entries and crosses out all that
% can't contain it. If only one of the cells in its sub-square remains free, that
% cell must contain it.

sudoku_data.necessary_entries = zeros(9,9); % clear results

v = sudoku_data.entry_value; % use a copy

for x = 1:9 % the number we are looking at
	% cross out all the cells that are impossible by entering ones in them
	crossed = zeros(9,9);  % initially none is crossed out
   
   fv = find(v > 0);
	if ~isempty(fv) crossed(fv) = 1; end % cross out those already filled
   
   for i = 1:9
		if ~isempty(find(v(i,:) == x)) crossed(i,:) = 1; end % cross out row
		if ~isempty(find(v(:,i) == x)) crossed(:,i) = 1; end % cross out column
   end

	for i = [1,4,7]
		for j = [1,4,7]
			if ~isempty(find(v(i:i+2,j:j+2) == x))
				crossed(i:i+2,j:j+2) = 1; % cross out sub-square
         else
            % this sub-square will contain it
            if sum(sum(crossed(i:i+2,j:j+2))) == 8 % only one possible cell
					[ii,jj] = find(crossed(i:i+2,j:j+2) == 0); % find it
               sudoku_data.necessary_entries(i+ii-1,j+jj-1) = x;
            end
         end
   	end
   end
end


function pressbuttonsudoku(src,evnt)
% global fignr;
global sudoku_data;

% figure(fignr);
xy=get(gcf,'currentpoint');
px=xy(1);
py=xy(2);
[i,j]=find_pos(px,py);
if i>0 && j>0
    plot_sudoku(sudoku_data);
    [sx,sy,w,h]=position(i,j);
    x=[sx sx+w sx+w sx];
    y=[sy sy sy+h sy+h];
    patch(x,y,'r','facealpha',0.5)
    %     pause(0.1)
    %     drawnow
    sudoku_data.current_selected_i=i;
    sudoku_data.current_selected_j=j;
end
% figure(fignr);
% drawnow


function presskeysudoku(src,evnt)
global sudoku_data;
global lastkey;
global fignr;
global data_history;
global current_step;
global max_step;

i=sudoku_data.current_selected_i;
j=sudoku_data.current_selected_j;
if i>0 && j>0
    nr=get(gcf,'currentcharacter');
    sudoku_data.entry_value(i,j)=str2num(nr);
    % add to history
    current_step=current_step+1;
    data_history{current_step}=sudoku_data;
    max_step=current_step;
    plot_sudoku(sudoku_data);
end




function plot_sudoku(sudoku_data)
global fignr;

figure(fignr);
cla;

hold on
xlabel('');
ylabel('');
set(gca,'xtick',[])
set(gca,'ytick',[])
set(gca,'pos',[0.01 0.01 0.98 0.98]);

for i=1:9
    for j=1:9
        [sx,sy,w,h]=position(i,j);
        line([sx sx],[sy sy+h],'color','k','linewidth',1);
        line([sx+w sx+w],[sy sy+h],'color','k','linewidth',1);
        line([sx sx+w],[sy sy],'color','k','linewidth',1);
        line([sx sx+w],[sy+h sy+h],'color','k','linewidth',1);
    end
end
for i=1:3
    for j=1:3
        [sx,sy,w,h]=bigposition(i,j);
        line([sx sx],[sy sy+h],'color','k','linewidth',3);
        line([sx+w sx+w],[sy sy+h],'color','k','linewidth',3);
        line([sx sx+w],[sy sy],'color','k','linewidth',3);
        line([sx sx+w],[sy+h sy+h],'color','k','linewidth',3);
    end
end

% plot the pencil numbers
% if sudoku_data.show_pencilmarks
for i=1:9
    for j=1:9
        nr_pens=sudoku_data.number_possible(i,j);
        if nr_pens==1
            col='g';
            size=14;
        else
            col='b';
            size=10;
        end

        for k=1:nr_pens
            [sx,sy,w,h]=position(i,j);
            nrp=sudoku_data.possible_entries(i,j,k);
            if nrp>0
                switch k
                    case 1
                        text(sx+0.01,sy+h,num2str(nrp),'fontsize',size,'color',col,'hor','left','vert','top');
                    case 2
                        text(sx+0.01+w/2,sy+h,num2str(nrp),'fontsize',size,'color',col,'hor','center','vert','top');
                    case 3
                        text(sx-0.01+w,sy+h,num2str(nrp),'fontsize',size,'color',col,'hor','right','vert','top');
                    case 4
                        text(sx+0.01,sy+h/2,num2str(nrp),'fontsize',size,'color',col,'hor','left','vert','middle');
                    case 5
                        text(sx+0.01+w/2,sy+h/2,num2str(nrp),'fontsize',size,'color',col,'hor','center','vert','middle');
                    case 6
                        text(sx-0.01+w,sy+h/2,num2str(nrp),'fontsize',size,'color',col,'hor','right','vert','middle');
                    case 7
                        text(sx+0.01,sy,num2str(nrp),'fontsize',size,'color',col,'hor','left','vert','botto');
                    case 8
                        text(sx+0.01+w/2,sy,num2str(nrp),'fontsize',size,'color',col,'hor','center','vert','botto');
                    case 9
                        text(sx-0.01+w,sy,num2str(nrp),'fontsize',size,'color',col,'hor','right','vert','botto');
                end
            end
        end
    end
end
% end

% plot the forced numbers fat
for i=1:9
    for j=1:9
        nr=sudoku_data.necessary_entries(i,j);
        if nr>0
            [sx,sy,w,h]=position(i,j);
            text(sx+w/2,sy+h/2,num2str(nr),'fontsize',20,'color','g');
        end
    end
end


% plot the numbers
% check if finished
if is_solved(sudoku_data.entry_value)
    col='g';
else
    col='k';
end
for i=1:9
    for j=1:9
        nr=sudoku_data.entry_value(i,j);
        if nr>0
            [sx,sy,w,h]=position(i,j);
            text(sx+w/2,sy+h/2,num2str(nr),'fontsize',20,'color',col);
        end
    end
end





% check validity
v=sudoku_data.entry_value;
for i=1:9
    for j=1:9
        if i<4          iii=[1 2 3]; end    % subsquare
        if i>3 && i<7   iii=[4 5 6]; end
        if i>6          iii=[7 8 9]; end
        if j<4          jjj=[1 2 3]; end
        if j>3 && j<7   jjj=[4 5 6]; end
        if j>6          jjj=[7 8 9]; end
        x=v(i,j); % the number
        if v(i,j)~=0
            is_valid=1;
            for ii=1:9   % check the row
                if v(ii,j)==x && ii~=i
                    is_valid=0;
                    break;
                end
            end
            if is_valid
                for jj=1:9   % check the column
                    if v(i,jj)==x && jj~=j
                        is_valid=0;
                        break;
                    end
                end
            end
            if is_valid
                for ii=iii   % check the subsquare
                    for jj=jjj   %
                        if v(ii,jj)==x && ii~=i && jj~=j
                            is_valid=0;
                            break;
                        end
                    end
                end
            end
            if ~is_valid
                [sx,sy,w,h]=position(i,j);
                text(sx+w/2,sy+h/2,num2str(x),'fontsize',20,'color','r');
            end
        end
    end
end



function dr=fill_random

    d=zeros(9,9);
    r=randperm(9);
    d(1,1:end)=r;
    k.entry_value=d; % the original
    dr=solver(k);


function d=delete_random(d,nr,vari)
% delete so many numbers in each square with a variance of var
for i=1:9
    if i==1 iii=[1 2 3]; jjj=[1 2 3]; end
    if i==2 iii=[1 2 3]; jjj=[4 5 6]; end
    if i==3 iii=[1 2 3]; jjj=[7 8 9]; end
    if i==4 iii=[4 5 6]; jjj=[1 2 3]; end
    if i==5 iii=[4 5 6]; jjj=[4 5 6]; end
    if i==6 iii=[4 5 6]; jjj=[7 8 9]; end
    if i==7 iii=[7 8 9]; jjj=[1 2 3]; end
    if i==8 iii=[7 8 9]; jjj=[4 5 6]; end
    if i==9 iii=[7 8 9]; jjj=[7 8 9]; end

    real_nr=nr+round(rand*2*vari-vari);
    real_nr=min(7,real_nr);
    r=randperm(9);
    r=r(1:real_nr);
    for j=1:real_nr
        c1=1;
        for ii=iii
            c2=1;
            for jj=jjj
                if c1+3*(c2-1)==r(j)
                    d.entry_value(ii,jj)=0;
                end
                c2=c2+1;
            end
            c1=c1+1;
        end
    end
end



% find out if the solution is found
function solved=is_solved(vals)
solved=1; % assume found
% shortcut:
if sum(sum(vals))~=405
    solved=0;
    return
end

for i=1:9
    for j=1:9
        if i<4          iii=[1 2 3]; end    % subsquare
        if i>3 && i<7   iii=[4 5 6]; end
        if i>6          iii=[7 8 9]; end
        if j<4          jjj=[1 2 3]; end
        if j>3 && j<7   jjj=[4 5 6]; end
        if j>6          jjj=[7 8 9]; end
        if sum(sum(vals(iii,jjj)))~=45
            solved=0;
            return
        end
    end
end
for i=1:9
    if sum(vals(i,:))~=45 % test all rows
        solved=0;
        return
    end
    if sum(vals(:,i))~=45 % test all columns
        solved=0;
        return
    end
end


function [sx,sy,w,h]=position(i,j)
off_x=0.0;
off_y=0.0;
dx=(1-off_x)/9;
dy=(1-off_y)/9;
sx=(i-1)*dx+off_x;
sy=(j-1)*dy+off_x;
w=dx;
h=dy;
return

function [i,j]=find_pos(sx,sy)
off_x=0.0;
off_y=0.0;
dx=(1-off_x)/9;
dy=(1-off_y)/9;
for i=1:9
    for j=1:9
        sxl=(i-1)*dx+off_x;
        syl=(j-1)*dy+off_x;
        sxh=sxl+dx;
        syh=syl+dy;
        if sxl<=sx && sxh>=sx && syl<=sy && syh>=sy
            return
        end
    end
end
i=0;j=0;
return

function [sx,sy,w,h]=bigposition(i,j)
off_x=0.0;
off_y=0.0;
dx=(1-off_x)/3;
dy=(1-off_y)/3;
sx=(i-1)*dx+off_x;
sy=(j-1)*dy+off_x;
w=dx;
h=dy;
return