image thumbnail

GUI for Hybrid Sudoku Solver

by

 

A simple GUI to solve Sudoku puzzles. Uses both logical and bruteforce methods.

SudokuSolver(C)
%%%%%%%%%%Programmed by: Chi-Hang Kwan%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%Creation Date: November 3, 2012%%%%%%%%%%%%%%%%%%%%
function C = SudokuSolver(C) 

counter = 0;


SecVal = zeros(9,9); %assigning the section codes

for ii=1:9
    for jj=1:9
        if floor((ii-1)/3)==0 %Here we are assigning the section numbers for each square
            SecVal(ii,jj) = 1 + floor((jj-1)/3);
        elseif floor((ii-1)/3)==1
            SecVal(ii,jj) = 4 + floor((jj-1)/3);
        else
            SecVal(ii,jj) = 7 + floor((jj-1)/3);
        end
    end
end


iter = 1;
count_new=1;
count_old=0;

while count_new>count_old
    
count_old=counter;

RowSum = zeros(9,9); %determine if a number can only appear once in a row 
RowOrder = zeros(9,9); %deciphering where to place that number in the row
ColSum = zeros(9,9); %determine if a number can only appear once in a column 
ColOrder = zeros(9,9); %deciphering where to place that number in the column
SecSum = zeros(9,9); %determine if a number can only appear once in a section 
SecRowOrder = zeros(9,9); %deciphering which Row to place in a section
SecColOrder = zeros(9,9); %deciphering which Column to place in a section
    
    
Pos=SudokuUpdate(C, SecVal); %Calculate possible values for each cell

%Determine all hidden singles (an integer with one possible location within each row or col or section. )
for ii=1:9 %for each 
    for jj=1:9
        for kk=1:9 %for the possbilities 1 to 9
            if C(ii,jj)==0 %Only cares about the empty (zero) entries
                if Pos(ii,jj,kk)==1; %If the number is possible within the cell
                    RowSum(ii,kk) = RowSum(ii,kk) + 1;
                    RowOrder(ii,kk) = RowOrder(ii,kk)+jj;
                    ColSum(jj,kk) = ColSum(jj,kk) + 1;
                    ColOrder(jj,kk) = ColOrder(jj,kk)+ii;
                    SecSum(SecVal(ii,jj),kk) = SecSum(SecVal(ii,jj),kk) + 1;
                    SecRowOrder(SecVal(ii,jj),kk) = SecRowOrder(SecVal(ii,jj),kk)+ii;
                    SecColOrder(SecVal(ii,jj),kk) = SecColOrder(SecVal(ii,jj),kk)+jj;
                end
            end
        end
   end
end

%enter hidden singles within each Row
for ii=1:9
    for kk = 1:9
        if RowSum(ii,kk)==1
            C(ii,RowOrder(ii,kk))=kk;
            counter =counter +1;
        end
    end
end   

%enter hidden singles within each column
for jj=1:9
    for kk = 1:9
        if ColSum(jj,kk)==1
            C(ColOrder(jj,kk),jj)=kk;
            counter=counter+1;
        end
    end
end

%enter hidden singles within each section
for ss=1:9
    for kk = 1:9
        if SecSum(ss,kk)==1
            C(SecRowOrder(ss,kk), SecColOrder(ss,kk))=kk;
            counter=counter+1;
        end
    end
end  

iter=iter+1;
count_new=counter;

end %end of Logical Approach


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Brute force approach now!
Pos=SudokuUpdate(C, SecVal); %Update cell possibilities

%find empty cells
m = 1;
for n=1:81
    if C(n)==0;
        empty(m)=n;
        Col(m) = floor((n-1)/9)+1; 
        Row(m) = rem(n-(Col(m)-1)*9,10);
        m=m+1;
    end
end 

m = m - 1;
if m == 0 %if no entries all empty, we are done!
    return;
end

PosVal = zeros(m,9);
for n = 1:m
    PosVal(n,:)=Pos(Row(n),Col(n),:); %Get Possbilities for all empty cells
end


%Enter Bruteforce function with matrix,start location,... 
%iteration count and possible values for each empty location                                                   
iter = 0;
[bool, C, iter]=BruteForce(C,1,empty,iter,PosVal); 


                                          

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%Function to Calculate Cell Possbilities%%%%%%%%%%%%%
function Pos = SudokuUpdate(C, SecVal)

RowPos = ones(9,9); %possibiliites for each row
ColPos = ones(9,9); %possibiliites for each column
SecPos = ones(9,9); %possibiliites for each section
Pos = ones(9,9,9);  %possibilities for each square

for ii=1:9  
    for jj=1:9
        if C(ii,jj)>0 % from all non zero entries
            RowPos(ii,C(ii,jj))=0;
            ColPos(jj,C(ii,jj))=0;
            SecPos(SecVal(ii,jj),C(ii,jj))=0;
        end
    end
end 
for ii=1:9
    for jj=1:9
        if C(ii,jj)==0 %Calculate all possibilities for zero entries
            Pos(ii,jj,:) = RowPos(ii,:).*ColPos(jj,:).*SecPos(SecVal(ii,jj),:);
        end
    end
end










Contact us