%% Solving Sudoku using Annealing
% The Sudoku matrix (Matrix A) is initially filled with missing elements by
% replacing the 0 elements in each of the 9 blocks with
% the ones that are absent in the block. Thus each Block is filled
% with elements from 1 to 9, satisfying one of the conditions of a solved
% sudoku. Annealing is now performed of the Sudoku matrix (Matrix A)
% by selecting one of the 9 blocks by random and interchanging
% two filled in elements in the block and checking whether the matrix
% is better than the previous, if so the the new matrix is assigned as the
% Sudoku matrix (Matrix A). A rarer case of moving to a worse Sudoku matrix
% is also implimented to escape local minimas.
% Cell arrays to store the index of the elements that are not present in
% the sudoku matrix (elements with 0). Cell arrays were chosen as
% arrays of different sizes(jagged arrays) can be stored in a single cell array.
blockx={[] [] [] [] [] [] [] [] []};
blocky={[] [] [] [] [] [] [] [] []};
index=1;
% Fills each of the 9 blocks with the missing elements and
% stores the indices of the elements that are filled in cell arrays
% blockx and blocky.
for i=0:2
for k=0:2
% Finds the index of the 0 elements in the sumbatrix/Block of the Sudoku matrix.
[x,y]=find(~A(1+i*3:3+i*3, 1+k*3:3+k*3));
% Finds and stores the indices of 0 elements with respect to
% the Sudoku matrix (A) in the cell arrays blockx and blocky.
blockx{index} = x + 3*i;
blocky{index} = y + 3*k;
index=index+1;
% Fills each block with the missing elements.
A(1+i*3:3+i*3, 1+k*3:3+k*3)=fillBlock(A(1+i*3:3+i*3, 1+k*3:3+k*3));
end
end
cond=check(A);
% Performs annealing
while cond~=0
% Interchanges two of the filled in elements of one of the
% 9 ranodly chosen blocks.
% Selects a Block.
Blocknumber = ceil(rand*9);
% Selects the index of two interchangable indices in cell array blockx and blocky.
T = randperm(length(blockx{Blocknumber}),2);
% Interchanges the two elements based of the index stored in blocky and blockx.
B = interchange(A,blockx{Blocknumber}(T(1)),blocky{Blocknumber}(T(1)),blockx{Blocknumber}(T(2)),blocky{Blocknumber}(T(2)));
cond=check(A);
% Checks if the new sudoku matrix is better than the old one.
if cond >= check(B)
A = B;
else
% Breaks away from local minimas.
if rand < 0.01
A = B;
end
end
end
disp('Unsolved Sudoku :')
disp(unsolvedSudoku)
disp('Solved Sudoku :')
disp(A)
toc
%% Functions
% Checks if the matrix is a solution.
% The number of unique elements in each row and column is calculated,
% then subtracted form 162, which is the number of unique elements in each
% row and column for a solved sudoku. Thus if the fucnton relturns 0 then
% the sudoku is solved.
function score=check(A)
score=162;
for i=1:9
score=score-(length(unique(A(1:9,i)))+length(unique(A(i,1:9))));
end
end
% Fills the matrix/block with missing elements
% by replacing the zero elements with numbers that are
% not in the matrix/block.
function A = fillBlock(A)
index = 1;
missingElements = setdiff(1:9, A);
for i=1:9
if(A(i) == 0)
A(i)= missingElements(index);
index = index + 1;
end
end
end
% Interchanges two elements of the matrix at the specified indices
% and returns the new matrix.
function A = interchange(A, i1, k1, i2, k2)
temp = A(i1, k1);
A(i1, k1) = A(i2, k2);
A(i2, k2) = temp;
end
发表于 2022-7-22 20:53
|
发表于 2022-7-30 21:19
