function result=SudokuSolver(problem)
%--------------------------------------------------------------------------
%SudokuSolver
%Version 1.10
%Created by Stepen
%Created 2 May 2011
%Last modified 8 May 2011
%--------------------------------------------------------------------------
%SudokuSolver reads an incomplete 9x9 Sudoku board represented by 9x9 array
%and completes the board, assuming that a single unique solution is exist
%for the incomplete board. Sudokusolver also generates random Sudoku puzzle
%when no input argument is given.
%--------------------------------------------------------------------------
%Syntax:
%result=SudokuSolver(problem)
%Input argument:
%- problem (9 x 9 int) specifies the incomplete 9x9 Sudoku board where
% value of 0 represent empty box.
%Output argument:
%- result (9 x 9 int) specifies the solution / complete Sudoku board for
% given problem.
%--------------------------------------------------------------------------
%CodeStart-----------------------------------------------------------------
%Providing an example of Sudoku board when no input argument is given
if nargin==0
% problem=[2,0,0,7,0,9,0,3,0;...
% 0,0,1,0,8,0,9,6,0;...
% 0,8,0,5,0,0,7,0,0;...
% 9,0,0,0,1,0,0,5,0;...
% 3,0,5,0,0,0,8,0,2;...
% 0,4,0,0,7,0,0,0,3;...
% 0,0,3,0,0,7,0,4,0;...
% 0,1,7,0,2,0,5,0,0;...
% 0,9,0,8,0,6,0,0,1];
% problem=[0,0,0,1,0,0,0,2,9;...
% 0,0,5,0,0,0,0,0,4;...
% 0,6,8,0,0,0,0,0,0;...
% 0,0,0,7,0,0,5,0,0;...
% 0,2,0,0,6,0,0,8,0;...
% 0,0,3,0,0,9,0,0,0;...
% 0,0,0,0,5,0,1,6,0;...
% 4,0,0,0,3,0,0,0,0;...
% 7,0,0,0,0,2,0,0,0];
problem=zeros(9);
end
%Checking problem array size
[r,c]=size(problem);
if ((r~=9)||(c~=9))
error('Input problem array size must be 9x9!')
end
%Checking and copying problem array
stat=CheckBoard(problem);
if sum(sum(stat))~=0
error('Input problem violates Sudoku rules!')
end
board=problem;
%Generating possibility array
possibility=cell(9);
for row=1:9
for col=1:9
if problem(row,col)==0
possibility{row,col}=[1,2,3,4,5,6,7,8,9];
end
end
end
%Initializing possibility array
for row=1:9
for col=1:9
if problem(row,col)~=0
testvalue=problem(row,col);
%Removing possibility from adjacent row and column element
for count=1:9
possibility{row,count}...
(possibility{row,count}==testvalue)=[];
possibility{count,col}...
(possibility{count,col}==testvalue)=[];
end
%Removing possibility from minigrid
gcrow=ceil(row/3);
gccol=ceil(col/3);
for i=3*gcrow-2:3*gcrow
for j=3*gccol-2:3*gccol
possibility{i,j}(possibility{i,j}==testvalue)=[];
end
end
end
end
end
%Preparing pivot in case guessing value is needed
pivotvalue=cell(1,81);
pivotrow=cell(1,81);
pivotcol=cell(1,81);
pivotboard=cell(1,81);
pivotpossibility=cell(1,81);
%Solving given Sudoku problem
pivot=0;
while sum(sum((board==0)))
%for i=1:20
%Finding twins in possibility array and eliminate it
possibility=FindEliminateTwinsInRow(possibility);
possibility=FindEliminateTwinsInCol(possibility);
possibility=FindEliminateTwinsInMiniGrid(possibility);
%Finding triplets in possibility array and eliminate it
possibility=FindEliminateTripletsInRow(possibility);
possibility=FindEliminateTripletsInCol(possibility);
possibility=FindEliminateTripletsInMiniGrid(possibility);
%Finding location with single possibility value
[value1,rowloc1,colloc1]=FindSinglePossibility(possibility);
%Filling location with single possibility value with its value
[board,possibility]=FillBoard(board,possibility,...
value1,rowloc1,colloc1);
%Finding loneranger
[value2,rowloc2,colloc2]=FindLoneRanger(possibility);
%Filling loneranger value into board
[board,possibility]=FillBoard(board,possibility,...
value2,rowloc2,colloc2);
%Anticipating wrong guess and return to the closest pivot
stat1=CheckBoard(board);
stat2=CheckImpossibility(board,possibility);
if (sum(sum(stat1))~=0)||(sum(sum(stat2))~=0)
board=pivotboard{pivot};
possibility=pivotpossibility{pivot};
testvalue=pivotvalue{pivot}...
(ceil(rand*numel(pivotvalue{pivot})));
pivotvalue{pivot}(pivotvalue{pivot}==testvalue)=[];
[board,possibility]=FillBoard(board,possibility,testvalue,...
pivotrow{pivot},pivotcol{pivot});
if isempty(pivotvalue{pivot})
pivot=pivot-1;
end
end
%Guessing value
if (numel(value1)==0)&&(numel(value2)==0)
pivot=pivot+1;
possibilitycount=CountPossibility(possibility);
for count=2:9
[rcandidate,ccandidate]=find(possibilitycount==count);
if ~isempty(rcandidate)
break
end
end
if isempty(rcandidate)
break
else
pivotrow{pivot}=rcandidate(1);
pivotcol{pivot}=ccandidate(1);
end
testvalue=possibility{pivotrow{pivot},pivotcol{pivot}}...
(ceil(rand*numel(possibility{...
pivotrow{pivot},...
pivotcol{pivot}})));
pivotvalue{pivot}=possibility{pivotrow{pivot},pivotcol{pivot}};
pivotvalue{pivot}(pivotvalue{pivot}==testvalue)=[];
pivotboard{pivot}=board;
pivotpossibility{pivot}=possibility;
[board,possibility]=FillBoard(board,possibility,testvalue,...
pivotrow{pivot},pivotcol{pivot});
end
end
%Assigning result
result=board;
%CodeEnd
end
%--------------------------------------------------------------------------
%Local Function
%--------------------------------------------------------------------------
function stat=CheckBoard(board)
%Generating status array
stat=false(9);
%Performing violation checking
for testvalue=1:9
%Checking for violation in rows
for row=1:9
if sum(sum(board(row,:)==testvalue))>1
errorloc=(board(row,:)==testvalue);
stat(row,:)=stat(row,:)|errorloc;
end
end
%Checking for violation in columns
for col=1:9
if sum(sum(board(:,col)==testvalue))>1
errorloc=(board(:,col)==testvalue);
stat(:,col)=stat(:,col)|errorloc;
end
end
%Checking for violation in minigrid
for gcrow=[1,2,3]
for gccol=[1,2,3]
if sum(sum(board(3*gcrow-2:3*gcrow,3*gccol-2:3*gccol)==...
testvalue))>1
errorloc=(board(3*gcrow-2:3*gcrow,3*gccol-2:3*gccol)==...
testvalue);
stat(3*gcrow-2:3*gcrow,3*gccol-2:3*gccol)=...
(stat(3*gcrow-2:3*gcrow,3*gccol-2:3*gccol)|errorloc);
end
end
end
end
end
%--------------------------------------------------------------------------
function stat=CheckImpossibility(board,possibility)
%Generating status array
stat=false(9);
%Scanning for impossibility
for row=1:9
for col=1:9
if (board(row,col)==0)&&(numel(possibility{row,col})==0)
stat(row,col)=true;
end
end
end
end
%--------------------------------------------------------------------------
function possibility=FindEliminateTwinsInRow(possibility)
%Performing search recursion for all rows
for row=1:9
for col=1:9
if numel(possibility{row,col})==2
%Checking whether a location has its twin or not
temp=zeros(1,9);
for count=1:9
temp(count)=isequal(possibility{row,col},...
possibility{row,count});
end
%Eliminating all twins' values in adjacent row
if sum(sum(temp))==2
value1=possibility{row,col}(1);
value2=possibility{row,col}(2);
for count=1:9
if temp(count)~=1
possibility{row,count}...
(possibility{row,count}==value1)=[];
possibility{row,count}...
(possibility{row,count}==value2)=[];
end
end
end
end
end
end
end
%--------------------------------------------------------------------------
function possibility=FindEliminateTwinsInCol(possibility)
%Performing search recursion for all columns
for col=1:9
for row=1:9
if numel(possibility{row,col})==2
%Checking whether a location has its twin or not
temp=zeros(9,1);
for count=1:9
temp(count)=isequal(possibility{row,col},...
possibility{count,col});
end
%Eliminating all twins' values in adjacent column
if sum(sum(temp))==2
value1=possibility{row,col}(1);
value2=possibility{row,col}(2);
for count=1:9
if temp(count)~=1
possibility{count,col}...
(possibility{count,col}==value1)=[];
possibility{count,col}...
(possibility{count,col}==value2)=[];
end
end
end
end
end
end
end
%--------------------------------------------------------------------------
function possibility=FindEliminateTwinsInMiniGrid(possibility)
%Performing search recursion for all minigrids
for row=1:9
for col=1:9
if numel(possibility{row,col})==2
%Checking whether a location has its twin or not
temp=zeros(3);
gcrow=3*ceil(row/3);
gccol=3*ceil(col/3);
for count1=1:3
for count2=1:3
temp(count1,count2)=isequal(possibility{row,col},...
possibility{gcrow-3+count1,...
gccol-3+count2});
end
end
%Eliminating twins' values in the same minigrid
if sum(sum(temp))==2
value1=possibility{row,col}(1);
value2=possibility{row,col}(2);
for count1=1:3
for count2=1:3
if temp(count1,count2)~=1
possibility{gcrow-3+count1,...
gccol-3+count2}...
(possibility{gcrow-3+count1,...
gccol-3+count2}...
==value1)...
=[];
possibility{gcrow-3+count1,...
gccol-3+count2}...
(possibility{gcrow-3+count1,...
gccol-3+count2}...
==value2)...
=[];
end
end
end
end
end
end
end
end
%--------------------------------------------------------------------------
function possibility=FindEliminateTripletsInRow(possibility)
%Performing search recursion for all rows
for row=1:9
for col=1:9
if numel(possibility{row,col})==3
%Checking whether a location has its twin or not
temp1=zeros(1,9);
test1=possibility{row,col}([1,2]);
temp2=zeros(1,9);
test2=possibility{row,col}([2,3]);
temp3=zeros(1,9);
test3=possibility{row,col}([1,3]);
temp4=zeros(1,9);
for count=1:9
temp1(count)=isequal(test1,possibility{row,count});
temp2(count)=isequal(test2,possibility{row,count});
temp3(count)=isequal(test3,possibility{row,count});
temp4(count)=isequal(possibility{row,col},...
possibility{row,count});
end
temp=temp1+temp2+temp3+temp4;
%Eliminating all twins' values in adjacent row
if sum(sum(temp))==3
value1=possibility{row,col}(1);
value2=possibility{row,col}(2);
value3=possibility{row,col}(3);
for count=1:9
if temp(count)~=1
possibility{row,count}...
(possibility{row,count}==value1)=[];
possibility{row,count}...
(possibility{row,count}==value2)=[];
possibility{row,count}...
(possibility{row,count}==value3)=[];
end
end
end
end
end
end
end
%--------------------------------------------------------------------------
function possibility=FindEliminateTripletsInCol(possibility)
%Performing search recursion for all rows
for col=1:9
for row=1:9
if numel(possibility{row,col})==3
%Checking whether a location has its twin or not
temp1=zeros(9,1);
test1=possibility{row,col}([1,2]);
temp2=zeros(9,1);
test2=possibility{row,col}([2,3]);
temp3=zeros(9,1);
test3=possibility{row,col}([1,3]);
temp4=zeros(9,1);
for count=1:9
temp1(count)=isequal(test1,possibility{count,col});
temp2(count)=isequal(test2,possibility{count,col});
temp3(count)=isequal(test3,possibility{count,col});
temp4(count)=isequal(possibility{row,col},...
possibility{count,col});
end
temp=temp1+temp2+temp3+temp4;
%Eliminating all twins' values in adjacent row
if sum(sum(temp))==3
value1=possibility{row,col}(1);
value2=possibility{row,col}(2);
value3=possibility{row,col}(3);
for count=1:9
if temp(count)~=1
possibility{count,col}...
(possibility{count,col}==value1)=[];
possibility{count,col}...
(possibility{count,col}==value2)=[];
possibility{count,col}...
(possibility{count,col}==value3)=[];
end
end
end
end
end
end
end
%--------------------------------------------------------------------------
function possibility=FindEliminateTripletsInMiniGrid(possibility)
%Performing search recursion for all minigrids
for row=1:9
for col=1:9
if numel(possibility{row,col})==3
%Checking whether a location has its twin or not
temp1=zeros(3);
test1=possibility{row,col}([1,2]);
temp2=zeros(3);
test2=possibility{row,col}([2,3]);
temp3=zeros(3);
test3=possibility{row,col}([1,3]);
temp4=zeros(3);
gcrow=3*ceil(row/3);
gccol=3*ceil(col/3);
for count1=1:3
for count2=1:3
temp1(count1,count2)=isequal(test1,...
possibility{gcrow-3+count1,...
gccol-3+count2});
temp2(count1,count2)=isequal(test2,...
possibility{gcrow-3+count1,...
gccol-3+count2});
temp3(count1,count2)=isequal(test3,...
possibility{gcrow-3+count1,...
gccol-3+count2});
temp4(count1,count2)=isequal(possibility{row,col},...
possibility{gcrow-3+count1,...
gccol-3+count2});
end
end
temp=temp1+temp2+temp3+temp4;
%Eliminating triplets' values in the same minigrid
if sum(sum(temp))==3
value1=possibility{row,col}(1);
value2=possibility{row,col}(2);
value3=possibility{row,col}(3);
for count1=1:3
for count2=1:3
if temp(count1,count2)~=1
possibility{gcrow-3+count1,...
gccol-3+count2}...
(possibility{gcrow-3+count1,...
gccol-3+count2}...
==value1)...
=[];
possibility{gcrow-3+count1,...
gccol-3+count2}...
(possibility{gcrow-3+count1,...
gccol-3+count2}...
==value2)...
=[];
possibility{gcrow-3+count1,...
gccol-3+count2}...
(possibility{gcrow-3+count1,...
gccol-3+count2}...
==value3)...
=[];
end
end
end
end
end
end
end
end
%--------------------------------------------------------------------------
function possibilitycount=CountPossibility(possibility)
%Initiating possibilitycount array
possibilitycount=zeros(9);
%Calculating possibilitycount array
for row=1:9
for col=1:9
possibilitycount(row,col)=numel(possibility{row,col});
end
end
end
%--------------------------------------------------------------------------
function [value,rowloc,colloc]=FindSinglePossibility(possibility)
%Counting members of each possibility element
possibilitycount=CountPossibility(possibility);
%Finding single possibility locations
[rowloc,colloc]=find(possibilitycount==1);
%Finding value to filled in
value=zeros(size(rowloc));
for count=1:numel(rowloc)
value(count)=possibility{rowloc(count),colloc(count)};
end
end
%--------------------------------------------------------------------------
function [value,rowloc,colloc]=FindLoneRanger(possibility)
%Preparing result array
value=[];
rowloc=[];
colloc=[];
%Finding LoneRanger
for row=1:9
for col=1:9
if ~isempty(possibility{row,col})
testarray=possibility{row,col};
gcrow=ceil(row/3);
gccol=ceil(col/3);
for testvalue=testarray
temp1=zeros(1,9);
temp2=zeros(9,1);
temp3=zeros(3);
for count=1:9
temp1(1,count)=sum(sum(possibility{row,count}...
==testvalue));
temp2(count,1)=sum(sum(possibility{count,col}...
==testvalue));
end
for count1=3*gcrow-2:3*gcrow
for count2=3*gccol-2:3*gccol
temp3(count1,count2)=sum(sum(possibility{count1,...
count}...
==testvalue));
end
end
if (sum(sum(temp1))==1)||...
(sum(sum(temp2))==1)||...
(sum(sum(temp3))==1)
value(numel(value)+1)=testvalue;
rowloc(numel(rowloc)+1)=row;
colloc(numel(colloc)+1)=col;
break
end
end
end
end
end
end
%--------------------------------------------------------------------------
function [board,possibility]=FillBoard(board,possibility,...
value,rowloc,colloc)
if numel(value)~=0
for count=1:numel(value)
%Filling value to board
board(rowloc(count),colloc(count))=value(count);
%Updating possibility array
%Removing posibility in filled location
possibility{rowloc(count),colloc(count)}=[];
%Removing filled value in adjacent row
for row=1:9
possibility{row,colloc(count)}...
(possibility{row,colloc(count)}==value(count))=[];
end
%Removing filled value in adjacent column
for col=1:9
possibility{rowloc(count),col}...
(possibility{rowloc(count),col}==value(count))=[];
end
%Removing filled value in the same minigrid
gcrow=ceil(rowloc(count)/3);
gccol=ceil(colloc(count)/3);
for i=3*gcrow-2:3*gcrow
for j=3*gccol-2:3*gccol
possibility{i,j}(possibility{i,j}==value(count))=[];
end
end
end
end
end
%--------------------------------------------------------------------------
