function SudokuSolver(M)
% Adam Hebert
% EE 4780
% Sudoku Solver
%----------------------------------------
FlagON='Ori';
PlotTitle='Unfinished Sudoku';
PlotM(M,FlagON,PlotTitle,M,M);

SavwM=M;
WorkMat=SudokuMethod1(M);
NewMat=WorkMat(1:9,1:9,10);
% calculates undetermined elements
UndeterEle=zeros(9,9);
for iCounter=1:9
    for jCounter=1:9
        counter=0;
        for hCounter=1:9
            if WorkMat(iCounter,jCounter,hCounter)==1
                counter=counter+1;
            end
        end
        UndeterEle(iCounter,jCounter)=counter;
    end
end
for iCounter=1:9
    for jCounter=1:9
        if UndeterEle(iCounter,jCounter)==2
            guessxy=[iCounter,jCounter];
            guessval=find(WorkMat(guessxy(1),guessxy(2),1:9));
            MGuess1=NewMat;
            MGuess2=NewMat;
            MGuess1(guessxy(1),guessxy(2))=guessval(1);
            MGuess2(guessxy(1),guessxy(2))=guessval(2);
            WorkMatGuess1=SudokuMethod1(MGuess1);
            WorkMatGuess2=SudokuMethod1(MGuess2);
            CheckPossRe1=ChechPossibility(WorkMatGuess1);
            CheckPossRe2=ChechPossibility(WorkMatGuess2);
            if (CheckPossRe1==1)&&(CheckPossRe2==0)
                NewMat=MGuess1;
            end
            if (CheckPossRe1==0)&&(CheckPossRe2==1)
                NewMat=MGuess2;
            end
            if (CheckPossRe1==0)&&(CheckPossRe2==0)
                fprintf('Check the question again\n');
                return;
            end
            WorkMat=SudokuMethod1(NewMat);
            NewMat=WorkMat(1:9,1:9,10);
            for iiCounter=1:9
                for jjCounter=1:9
                    counter=0;
                    for hhCounter=1:9
                        if WorkMat(iiCounter,jjCounter,hhCounter)==1
                            counter=counter+1;
                        end
                    end
                    UndeterEle(iiCounter,jjCounter)=counter;
                end
            end
        end
    end
end

WorkMat=SudokuMethod1(NewMat);
NewMat=WorkMat(1:9,1:9,10);
FlagON='New';
PlotTitle='Sudoku Solved!';
PlotM(NewMat,FlagON,PlotTitle,SavwM,WorkMat);

% Check the results
if ~isempty(find(NewMat==0))
    fprintf('Unable to determine the results!\n');
end
1;
%%--------------------------------------------------
function WorkMat=SudokuMethod1(M)
% M is put into WorkMat
WorkMat=ones(9,9,10);
WorkMat(1:9,1:9,10)=M(1:9,1:9);

for kCounter=1:99
    % Initialize WorkMat according to Matrix
    for iCounter=1:9
        for jCounter=1:9
            if WorkMat(iCounter,jCounter,10)~=0
                val=WorkMat(iCounter,jCounter,10);
                WorkMat(iCounter,jCounter,1:9)=0;
                WorkMat(iCounter,jCounter,val)=1;
            end
        end
    end
    KnownMat=WorkMat(1:9,1:9,10);
    for iCounter=1:9
        for jCounter=1:9
            if WorkMat(iCounter,jCounter,10)==0
                xrow=iCounter;
                xcol=jCounter;
                for xCounter=1:9
                    CheckResults=CheckRow(xrow,xcol,xCounter,KnownMat);
                    if CheckResults==0
                        WorkMat(iCounter,jCounter,xCounter)=0;
                    end
                    CheckResults=CheckCol(xrow,xcol,xCounter,KnownMat);
                    if CheckResults==0
                        WorkMat(iCounter,jCounter,xCounter)=0;
                    end
                    CheckResults=CheckBlk(xrow,xcol,xCounter,KnownMat);
                    if CheckResults==0
                        WorkMat(iCounter,jCounter,xCounter)=0;
                    end
                end
            end
        end
    end
    FlagFind=0;
    FlagFindBefore=0;
    for iCounter=1:9
        for jCounter=1:9
            if WorkMat(iCounter,jCounter,10)==0
                if sum(WorkMat(iCounter,jCounter,1:9))==1
                    FlagFind=1;
                    val=find(WorkMat(iCounter,jCounter,1:9));
                    WorkMat(iCounter,jCounter,10)=val;
                    WorkMat(iCounter,jCounter,1:9)=0;
                    WorkMat(iCounter,jCounter,val)=1;
                end
            end
        end
    end
    for xCounter=1:9
        % Check each row
        MWorkVal=WorkMat(1:9,1:9,xCounter);
        M10Val=WorkMat(1:9,1:9,10);
        for iCounter=1:9
            RowM10Val=M10Val(iCounter,1:9);
            RowMWorkVal=MWorkVal(iCounter,1:9);
            if isempty(find(RowM10Val==xCounter))
                if sum(RowMWorkVal)==1
                    FlagFind=1;
                    val=find(RowMWorkVal);
                    WorkMat(iCounter,val,10)=xCounter;
                    WorkMat(iCounter,val,1:9)=0;
                    WorkMat(iCounter,val,xCounter)=1;
                end
            end
        end
        % Check each column
        MWorkVal=WorkMat(1:9,1:9,xCounter);
        M10Val=WorkMat(1:9,1:9,10);
        for iCounter=1:9
            ColM10Val=M10Val(1:9,iCounter);
            ColMWorkVal=MWorkVal(1:9,iCounter);
            if isempty(find(ColM10Val==xCounter))
                if sum(ColMWorkVal)==1
                    FlagFind=1;
                    val=find(ColMWorkVal);
                    WorkMat(val,iCounter,10)=xCounter;
                    WorkMat(val,iCounter,1:9)=0;
                    WorkMat(val,iCounter,xCounter)=1;
                end
            end
        end
        MWorkVal=WorkMat(1:9,1:9,xCounter);
        M10Val=WorkMat(1:9,1:9,10);
        for iCounter=1:9
            count=0;
            RowSt=fix((iCounter-1)/3)*3;
            ColSt=mod(iCounter-1,3)*3;
            BlkM10Val=zeros(9,1);
            BlkMWorkVal=zeros(9,1);
            for pCounter=RowSt+1:RowSt+3
                for qCounter=ColSt+1:ColSt+3
                    count=count+1;
                    BlkM10Val(count)=...
                        M10Val(pCounter,qCounter);
                    BlkMWorkVal(count)=...
                        MWorkVal(pCounter,qCounter);
                end
            end
            if isempty(find(BlkM10Val==xCounter))
                if sum(BlkMWorkVal)==1
                    FlagFind=1;
                    val=find(BlkMWorkVal);
                    ival=RowSt+fix((val-1)/3)+1;
                    jval=ColSt+mod(val-1,3)+1;
                    WorkMat(ival,jval,10)=xCounter;
                    WorkMat(ival,jval,1:9)=0;
                    WorkMat(ival,jval,xCounter)=1;
                end
            end
        end
    end
    if FlagFind==1
        for iCounter=1:9
            for jCounter=1:9
                if WorkMat(iCounter,jCounter,10)~=0
                    val=WorkMat(iCounter,jCounter,10);
                    WorkMat(iCounter,jCounter,1:9)=0;
                    WorkMat(iCounter,jCounter,val)=1;
                end
            end
        end
        FlagFindBefore=FlagFind;
    else
        if (FlagFindBefore==0)&&(FlagFind==0)&&(kCounter>1)
            break
        end
    end
end
%%--------------------------------------------------
function CheckPossRe=ChechPossibility(WorkMat)
CheckPossRe=1;
for iCounter=1:9
    for jCounter=1:9
        if sum(WorkMat(iCounter,jCounter,1:9))==0
            CheckPossRe=0;
            return;
        end
    end
end
%%--------------------------------------------------
function CheckResults=CheckRow(xrow,xcol,x,KnownMat)
CheckResults=1;
for iCounter=1:9
    if iCounter~=xcol
        if (x-KnownMat(xrow,iCounter))==0
            CheckResults=0;
            break;
        end
    end
end
%%--------------------------------------------------
function CheckResults=CheckCol(xrow,xcol,x,KnownMat)
CheckResults=1;
for iCounter=1:9
    if iCounter~=xrow
        if (x-KnownMat(iCounter,xcol))==0
            CheckResults=0;
            break;
        end
    end
end
%%--------------------------------------------------
function CheckResults=CheckBlk(xrow,xcol,x,KnownMat)
BigRow=ceil(xrow/3);
BigCol=ceil(xcol/3);
CheckResults=1;
for iCounter=(BigRow-1)*3+1:BigRow*3
    for jCounter=(BigCol-1)*3+1:BigCol*3
        if ~((iCounter==xrow)&&(jCounter==xcol))
            if (x-KnownMat(iCounter,jCounter))==0
                CheckResults=0;
                break;
            end
        end
    end
end
%%--------------------------------------------------
function PlotM(PlotMat,FlagON,PlotTitle,AuxMat1,AuxMat2)
figure;
axis equal
PlotPossM=zeros(9,9);
for iCounter=1:9
    for jCounter=1:9
        RecCornerX=iCounter-1;
        RecCornerY=jCounter-1;
        if mod((fix((iCounter-1)/3)+fix((jCounter-1)/3)),2)==0
            rectangle('Position',[RecCornerX,RecCornerY,1,1],...
                'Curvature',[0.0,0.0],'FaceColor',[1 1 1]);
        else
            rectangle('Position',[RecCornerX,RecCornerY,1,1],...
                'Curvature',[0.0,0.0],'FaceColor',[.8 .8 .8]);
        end
        plotnum=num2str(PlotMat(10-jCounter,iCounter));
        if AuxMat1(10-jCounter,iCounter)~=0
            text(RecCornerX+0.5,RecCornerY+0.5,plotnum,'Fontsize',16,...
                'HorizontalAlignment','center',...
                'FontWeigh','light','color',[0 0 0]);
        else
            if strcmp(FlagON,'New')
                if PlotMat(10-jCounter,iCounter)~=0
                    text(RecCornerX+0.5,RecCornerY+0.5,plotnum,'Fontsize',16,...
                        'HorizontalAlignment','center',...
                        'FontWeigh','bold','color',[0 0 0]);
                else
                    PossM=AuxMat2(10-jCounter,iCounter,1:9);
                    for pCounter=1:9
                        if PossM(pCounter)==0
                            PlotPossM(fix((pCounter-1)/3)+1,...
                                mod(pCounter-1,3)+1)=0;
                        else
                            PlotPossM(fix((pCounter-1)/3)+1,...
                                mod(pCounter-1,3)+1)=pCounter;
                        end
                    end
                    for iiCounter=1:3
                        for jjCounter=1:3
                            if PlotPossM(4-jjCounter,iiCounter)~=0
                                plotpossnum=...
                                    num2str(PlotPossM(4-jjCounter,iiCounter));
                                text(RecCornerX+0.5/3+1/3*(iiCounter-1),...
                                    RecCornerY+0.5/3+1/3*(jjCounter-1),...
                                    plotpossnum,'Fontsize',8,...
                                    'HorizontalAlignment','center',...
                                    'FontWeigh','light','color',[0 0.3 0]);
                            end
                        end
                    end
                end
            end
        end
    end
end
title(PlotTitle);