Code covered by the BSD License

# Sudoku

### Chaowei Chen (view profile)

16 Apr 2012 (Updated )

Solves sudoku puzzle. Generates all possible answers.

sudoku_solver
```function sudoku_solver
clc
set(0,'DefaultFigureWindowStyle','docked');

show(s);copyfig;
tic;sudoku_solver_routine(s);toc
close(figure(987));

end

function sudoku_solver_routine(s)
action='clean1';
while(~isempty(action))
switch(action)
case 'clean1'
scopy=s;
s=clean_1(s);
if isequal(s,scopy),action='clean2';else action='clean1';end
case 'clean2'
scopy=s;
s=clean_3(s);
if isequal(s,scopy),action='make_a_guess';else action='clean1';end
case 'done'
show(s);
copyfig;
break;
case 'make_a_guess'
% recursively making a guess and call the solver again
member_guess=find(cellfun(@numel,s)>1,1);
V=s{member_guess};
for k=1:numel(V)
[X,Y]=ind2sub([9,9],member_guess);
fprintf(' guess: s{%d,%d}=%s -> %s\n',X,Y,int2str(V),int2str(V(k)));
s_guess=move(s,member_guess,V(k)); % make the guess
try sudoku_solver_routine(s_guess);
catch e,
fprintf('        s{%d,%d}~=%s\n',X,Y,int2str(V(k)));
end
end
break;
case 'not_solvable'
error('Not solvable');
end % switch
if any(any(cellfun(@numel,s)==0)),action='not_solvable';end
if all(all(cellfun(@numel,s)==1)),action='done';end
end
end

function s=move(s,m,v)
if isequal(s{m},v),return;end % abort set
% [X,Y]=ind2sub([9,9],m);
% fprintf(' s{%d,%d}=%s -> %s\n',X,Y,int2str(v_ori),int2str(v));
% show(s);
s{m}=v;
end

function show(s)
h=figure(987);
delete(allchild(h));
for x=9:-1:1,
for y=9:-1:1,
h(x,y)=uicontrol('tag',[int2str(x) int2str(y)],'style','pushbutton',...
'units','normalized','position',[y/10 1-x/10 0.09 0.09]);
end
end;clear x y;

color_order=jet(9);
for e=1:81,
[X,Y]=ind2sub([9,9],e);
V=s{e};
switch(numel(V))
case 0, error('Not solvable');
case 1, % done
set(h(X,Y),'enable','off','Fontsize',12,'Fontweight','bold');
set(h(X,Y),'string',V);
set(h(X,Y),'backgroundcolor',color_order(V,:));
otherwise
set(h(X,Y),'string',int2str(V));
set(h(X,Y),'Fontsize',5);
end
end
drawnow;
end
function h2=copyfig(h1)
if nargin<1, h1=gcf;end
h2=figure;
copyobj(get(h1,'children'),h2);
end
function members=get_members(g)
switch(g)
case 27, members=1:9;
case 26, members=10:18;
case 25, members=19:27;
case 24, members=28:36;
case 23, members=37:45;
case 22, members=46:54;
case 21, members=55:63;
case 20, members=64:72;
case 19, members=73:81;
case 18, members=1:9:73;
case 17, members=2:9:74;
case 16, members=3:9:75;
case 15, members=4:9:76;
case 14, members=5:9:77;
case 13, members=6:9:78;
case 12, members=7:9:79;
case 11, members=8:9:80;
case 10, members=9:9:81;
case 9, members=[1 10 19 2 11 20 3 12 21];
case 8, members=[4 13 22 5 14 23 6 15 24];
case 7, members=[7 16 25 8 17 26 9 18 27];
case 6, members=[28 37 46 29 38 47 30 39 48];
case 5, members=[31 40 49 32 41 50 33 42 51];
case 4, members=[34 43 52 35 44 53 36 45 54];
case 3, members=[55 64 73 56 65 74 57 66 75];
case 2, members=[58 67 76 59 68 77 60 69 78];
case 1, members=[61 70 79 62 71 80 63 72 81];
end

end
function gg=member_belongs_to(m)
% each member 1-81 belongs to 3 groups out of 27
gg=[];
for g=1:27
members=get_members(g);
if any(members==m),gg=[gg g];    end
end
end
%%%% solver kernal %%%%
function s=clean_3(s)
certain_members=find(cellfun(@numel,s)==1); % uncertain indices
for g=1:27,
members=get_members(g);
um=setdiff(members,certain_members); % uncertain members

if numel(um)>1 , % if only one uncertain, it is certain and will be certain by clean_1
% generate histogram of all s{um(k)}, k=1:numel(um)
V=s{um(1)};    for k=2:numel(um),    V=[V s{um(k)}];    end
histV=hist(V,0:10);
histV=histV(2:10);
%
cm=find(histV==1); % certain member
if numel(cm)==1
for k=1:numel(um),
if any(s{um(k)}==cm),
s=move(s,um(k),cm);
break;
end
end
end
end
end
end
function s=clean_1(s)

um=find(cellfun(@numel,s)>1); % uncertain member
for k=1:numel(um)
umk=um(k);
umkV=s{umk};
gg=member_belongs_to(umk);
for g=gg
gm=get_members(g);
for j=1:numel(gm)
gmj=gm(j);
gmjV=s{gmj};
if numel(gmjV)==1,
umkV=setdiff(umkV,gmjV);
end
end
end
s=move(s,umk,umkV);
end

end
```