function Sol=sudoku_lvl2(A)
% SUDOKU_LVL2 - A Sudoku Solver.
%
% Usage : Sol=sudoku_lvl2(A)
% Where A is a incomplete sudoku grid (9 x 9) represented as a 9 x 9 matrix
% of integers (0-9) with the empty cells being filled with zeros.
%
% The algorithm presented here uses the following techniques.
% (*) Filling a cell by candidate elimination
% (*) Filling a cell by position exclusion for a given candidate
% (*) Refining choices of candidates in a given cell by eliminating members
% of locked pairs, locked triplets and so on..
% (*) Filling the remaining cells by brute force method.
%
% An example is shown below.
% Example :
%A =
%
% 3 0 1 0 8 0 7 0 2
% 0 6 0 5 0 0 0 0 0
% 7 0 2 0 9 0 6 0 5
% 0 9 0 8 0 0 0 0 0
% 1 0 3 0 6 0 2 0 4
% 0 0 0 0 0 0 0 0 0
% 2 0 6 0 7 0 9 0 3
% 0 0 0 0 0 0 0 0 0
% 8 0 5 0 1 0 4 0 7
%
% [Sol]=sudoku_lvl2(A)
%
%
% Sol =
%
% 3 5 1 6 8 4 7 9 2
% 4 6 9 5 2 7 3 1 8
% 7 8 2 1 9 3 6 4 5
% 5 9 4 8 3 2 1 7 6
% 1 7 3 9 6 5 2 8 4
% 6 2 8 7 4 1 5 3 9
% 2 1 6 4 7 8 9 5 3
% 9 4 7 3 5 6 8 2 1
% 8 3 5 2 1 9 4 6 7
%
% Author : S. Janardhanan (janas@ee.iitd.ac.in)
% Last Modified : 25-Sep-2008.
[m n]=size(A);
if ~isequal([m n],[9 9])
error('9 x 9 Matrix expected');
end
A1=A(:);
if any((A1-fix(A1))~=0) || any(~isreal(A1)) || any(A1>9) || any(A1<0)
error('Matrix A should be composed of integers (1-9)');
end
Choices=Initialize_Choices(A);
StartCount=length(find(A(:)==0));
EndCount=max(StartCount,0)-1;
while (StartCount > EndCount) && (EndCount > 0)
StartCount=length(find(A(:)==0));
[A,Choices]=sudoku_fn(A,StartCount,Choices);
if ~isempty(find(A(:)==0,1))
[A,Choices]=refine_choice(A,Choices);
end
EndCount=length(find(A(:)==0));
end
if all(A(:)>0)
Sol=A;
else
Id1=find(A(:)==0);
[Ilist,Jlist]=ind2sub([9,9],Id1);
Chlist(length(Ilist))=0;
for i=1:length(Ilist)
Chlist(i)=length(Choices{Ilist(i),Jlist(i)});
end
[ChList,ChInd]=sort(Chlist);
Ilist=Ilist(ChInd);
Jlist=Jlist(ChInd);
Sol=brute_force(A,Choices,Ilist,Jlist,1);
end
return
function Choices=Initialize_Choices(A)
Choices{9,9}=1:9;
for i=1:9
for j=1:9
if A(i,j) == 0
Choices{i,j}=1:9;
else
Choices{i,j}=A(i,j);
end
end
end
return
function [Sol,Choices]=sudoku_fn(A,InitNos,Choices)
ToFill=find(A(:)==0);
if ~exist('InitNos','var')
InitNos=length(ToFill);
end
StartCount=length(ToFill);
if ~isempty(ToFill)
for i=1:length(ToFill)
[ThisI,ThisJ]=ind2sub([9 9],ToFill(i));
RestCol=A(:,ThisJ);
RestRow=A(ThisI,:);
ii = (ceil(ThisI/3)-1)*3+1;
jj = (ceil(ThisJ/3)-1)*3+1;
iirange=ii:ii+2;
jjrange=jj:jj+2;
ThisBox=A(iirange,jjrange);
Choices{ThisI,ThisJ}=setdiff(Choices{ThisI,ThisJ},[RestCol;RestRow';ThisBox(:)]');
LeftOut=Choices{ThisI,ThisJ};
if length(LeftOut)==1
A(ThisI,ThisJ)=LeftOut;
else
OtherRow=setdiff(iirange,ThisI);
OtherCol=setdiff(jjrange,ThisJ);
for j=LeftOut
condi(5) = ~ismember(j,ThisBox(:));
condi(1)=(ismember(j,A(OtherRow(1),:))) && condi(5) ;
condi(2)=(ismember(j,A(OtherRow(2),:))) && condi(5);
condi(3)=(ismember(j,A(:,OtherCol(1)))) && condi(5);
condi(4)=(ismember(j,A(:,OtherCol(2)))) && condi(5);
condi(6) = A(OtherRow(1),ThisJ)~=0;
condi(7) = A(OtherRow(2),ThisJ)~=0;
condi(8) = A(ThisI,OtherCol(1))~=0;
condi(9) = A(ThisI,OtherCol(2))~=0;
cond_ab= condi(1) && condi(2);
cond_cd= condi(3) && condi(4);
cond_AB=condi(6) && condi(7);
cond_CD=condi(8) && condi(9);
cond_4cross= (cond_ab && cond_cd );
cond_2row=(cond_ab && cond_CD );
cond_2col=(cond_AB && cond_cd );
success= cond_4cross || cond_2row || cond_2col ;
if ~success
for jpass=1:2
for kpass=3:4
success=success || (all(condi([jpass kpass 5+([3 7]-[jpass kpass])]))&& (A(OtherRow(3-jpass),OtherCol(5-kpass)) ~=0)) ;
end
end
end
if ~success
switch length(find(condi(6:9)))
case 1
Single=find(condi(6:9));
success=all(condi(setdiff(1:4,Single)));
case 3
if cond_AB
for jpass=1:2
success=success || (all(A(iirange,OtherCol(jpass))~=0) && condi(5-jpass));
end
end
if cond_CD
for jpass=1:2
success=success || (all(A(OtherRow(jpass),jjrange)~=0) && condi(3-jpass));
end
end
end
end
if success && condi(5)
A(ThisI,ThisJ)=j;
Choices{ThisI,ThisJ}=j;
break
end
end
end
end
EndCount=length(find(A(:)==0));
if StartCount>EndCount
[Sol,Choices]=sudoku_fn(A,InitNos,Choices);
else
Sol=A;
end
else
Sol=A;
end
return
function [A,Choices]=refine_choice(A,Choices)
%return
[A,Choices]=refine_rows(A,Choices);
if ~isempty(find(A(:)==0,1))
[A,Choices]=refine_rows(A',Choices');
A=A';
Choices=Choices';
end
if ~isempty(find(A(:)==0,1))
for i=1:3
for j=1:3
ii=(i-1)*3+1;
jj=(j-1)*3+1;
ThisBox=Choices(ii:(ii+2),jj:(jj+2));
ThisBox=ThisBox(:);
for i1=1:8
This=ThisBox{i1};
Vec=i1;
for j1=setdiff(1:9,i1);
Other=ThisBox{j1};
if isequal(This,Other)
Vec=[Vec j1];
end
end
if length(This)==length(Vec)
[indI,indJ]=ind2sub([3 3],setdiff(1:9,Vec));
for i2=1:length(indI)
Choices{indI(i2)+ii-1,indJ(i2)+jj-1}=setdiff(Choices{indI(i2)+ii-1,indJ(i2)+jj-1},This);
if length(Choices{indI(i2)+ii-1,indJ(i2)+jj-1})==1
A(indI(i2)+ii-1,indJ(i2)+jj-1)=Choices{indI(i2)+ii-1,indJ(i2)+jj-1};
end
end
end
end
end
end
end
% Add an extra refinement if the puzzle is still not solved
if ~isempty(find(A(:)==0,1))
[A,Choices]=refine_again(A,Choices);
if ~isempty(find(A(:)==0,1))
[A,Choices]=refine_again(A',Choices');
A=A';
Choices=Choices';
end
end
return
function [A,Choices]=refine_rows(A,Choices)
for row=1:9
for i1=1:8
This=Choices{row,i1};
Vec=i1;
for i2=setdiff(1:9,i1);
Other=Choices{row,i2};
if isequal(This,Other)
Vec=[Vec i2];
end
end
if length(This)==length(Vec)
Modif=setdiff(1:9,Vec);
for i2=Modif
Choices{row,i2}=setdiff(Choices{row,i2},This);
if length(Choices{row,i2}) == 1
A(row,i2)=Choices{row,i2};
end
end
end
end
end
return
function [A, Choices]=refine_again(A, Choices)
RowBlk(9,3,9)=0;
for i=1:9
for j=1:9
jj=ceil(j/3);
for k=Choices{i,j}
RowBlk(i,jj,k)=RowBlk(i,jj,k)+1;
end
end
end
for i=1:3
for j=1:3
for k=1:9
Ex=RowBlk(3*(i-1)+(1:3),j,k);
Ex=Ex(:);
I=find(Ex>0);
if length(I)==1
I=I+(i-1)*3;
other_col=setdiff(1:9,(j-1)*3+(1:3));
for j1=other_col
jj=ceil(j/3);
if ~isempty(intersect(Choices{I,j1},k))
RowBlk(I,jj,k)=RowBlk(I,jj,k)-1;
Choices{I,j1}=setdiff(Choices{I,j1},k);
if length(Choices{I,j1})==1
A(I,j1)=Choices{I,j1};
end
end
end
end
end
end
end
function [Sol]=brute_force(A,Choices,Ilist,Jlist,i,Sol)
if ~exist('Sol','var')
Sol = zeros([size(A) 0]);
end
Id1=find(A(:)==0);
if isempty(Id1)
Sol=A;
else
indI=Ilist(i);indJ=Jlist(i);
ii = (ceil(indI/3)-1)*3+1;
jj = (ceil(indJ/3)-1)*3+1;
iirange=ii:ii+2;
jjrange=jj:jj+2;
ThisBox=A(iirange,jjrange);
for i1=Choices{indI,indJ}
if isempty(find(A(:,indJ)==i1,1)) && isempty(find(A(indI,:)==i1,1)) && isempty(find(ThisBox(:)==i1,1))
A(indI,indJ)=i1;
Sol=brute_force(A,Choices,Ilist,Jlist,i+1,Sol);
end
end
end
return
