% 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
