数独小程序
clear allclc
% Sandeep S Kumar
% MATH 4034
%% 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.
tic
A=[7 0 0 0 0 4 0 2 0
0 9 0 0 0 0 3 0 0
0 0 0 0 0 6 0 0 8
0 8 0 9 0 0 0 0 0
0 3 5 0 0 0 0 0 9
0 0 0 0 7 2 0 4 0
0 0 9 5 2 0 0 0 0
0 0 0 0 0 0 8 6 7
1 0 0 3 0 0 0 0 0];
unsolvedSudoku = A;
% 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.
=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.
ifrand < 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 看看怎么样 有成品不？ 这个可以 Wuaisunjie 发表于 2022-7-23 03:37
什么语言？
看起来像matlab 可以试着写一个vba的 Wuaisunjie 发表于 2022-7-23 03:37
什么语言？
matlab
muye1212 发表于 2022-7-23 09:33
可以试着写一个vba的
好的，谢谢
页:
[1]