image thumbnail

Sudoku

by

 

16 Apr 2012 (Updated )

Solves sudoku puzzle. Generates all possible answers.

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

load('sudoku_solver_109.mat','s');
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

Contact us