image thumbnail

Sudoku

by

 

09 Feb 2012 (Updated )

This code generates a random Sudoku puzzle or solves any given Sudoku puzzle.

result=SudokuSolver(problem)
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
%--------------------------------------------------------------------------

Contact us