空的位置用0補(bǔ)扁瓢,用空格分隔忽匈,將題目記錄到txt文檔中种蘸。
data.txt
0 0 0 0 0 0 0 0 0
0 2 3 0 0 0 7 8 0
1 0 0 4 0 6 0 0 9
4 0 0 0 5 0 0 0 1
9 0 0 0 0 0 0 0 6
0 6 0 0 0 0 0 9 0
0 0 5 0 0 0 8 0 0
0 0 0 3 0 1 0 0 0
0 0 0 0 9 0 0 0 0
檢查某個(gè)數(shù)字能否填入某個(gè)空格鞠值,只檢查那一橫行媚创。
check_row.m
function [result] = check_row(matrix, i, j, num)
result = true;
for col = 1 : 9
if matrix(i, col) == num
result = false;
break;
end
end
end
檢查某個(gè)數(shù)字能否填入某個(gè)空格,只檢查那一列齿诉。
check_col.m
function [result] = check_col(matrix, i, j, num)
result = true;
for row = 1 : 9
if matrix(row, j) == num
result = false;
break;
end
end
end
檢查某個(gè)數(shù)字能否填入某個(gè)空格筝野,只檢查所在的3*3小方陣。
check_block.m
function [result] = check_block(matrix, i, j, num)
result = true;
% 計(jì)算此i,j所屬小九宮格的坐標(biāo)
block_row = floor( (i-1) / 3 ) + 1;
block_col = floor( (j-1) / 3 ) + 1;
block_row_from = (block_row * 3) - 2;
block_row_to = block_row * 3;
block_col_from = (block_col * 3) - 2;
block_col_to = block_col * 3;
for row = block_row_from : block_row_to
for col = block_col_from : block_col_to
if matrix(row, col) == num
result = false;
break;
end
end
end
end
檢查某個(gè)數(shù)字能否填入某個(gè)空格粤剧,聯(lián)合檢查:所在行歇竟、所在列、所在的3*3小方陣抵恋。
check_all.m
function [result] = check_all(matrix, i, j, num)
result = check_row(matrix, i, j, num) && check_col(matrix, i, j, num) && check_block(matrix, i, j, num);
end
繪制格子和數(shù)據(jù)的 function :
function [] = draw(matrix, isSubplot, rows, cols, rank)
if isSubplot == true
subplot(rows, cols, rank);
matrix0 = dlmread('data.txt', '');
matrix0 = matrix0';
plot(0,0);
hold on
for i = 0 : 9
if rem(i,3) == 0
plot([0;9],[i,i],'linewidth',3,'color','black');
plot([i;i],[0,9],'linewidth',3,'color','black');
else
plot([0;9],[i,i],'linewidth',1,'color','black');
plot([i;i],[0,9],'linewidth',1,'color','black');
end
end
matrix = matrix';
for i = 1 : 9
for j = 1 : 9
if matrix(i,j) ~= 0
if matrix(i,j) == matrix0(i,j)
text(i-0.5, 9.5-j, strcat('\color{red}',num2str(matrix(i,j))));
else
text(i-0.5, 9.5-j, num2str(matrix(i,j)));
end
end
end
end
end
使用窮舉解決方案焕议。
solve.m
% 整個(gè)大九宮格的index編號(hào)(從左到右,從上到下):1 ~ 81
function solve(matrix, index)
if index > 81 % 已經(jīng)找到解
disp(matrix);
draw(matrix, true, 1, 2, 2);
else
% 計(jì)算此index對(duì)應(yīng)i弧关、j
i = floor((index - 1) / 9) + 1;
j = mod((index-1), 9) + 1;
if matrix(i, j) ~= 0 % 如果是個(gè)已知數(shù)的話盅安,直接跳到下一格
solve(matrix, index+1);
else % 未知數(shù)
for num = 1 : 9 % 試值
if check_all(matrix, i, j, num) == true % 可以
matrix(i, j) = num; % 賦值
solve(matrix, index+1); % 跳到下一格
end
end
end
end
end
主程序:將文本讀入到二維數(shù)組中,調(diào)用解決程序世囊,從位置1開(kāi)始别瞭。
sudoku.m
matrix = dlmread('data.txt', ' ');
disp(matrix);
draw(matrix, true, 1, 2, 1);
solve(matrix, 1);
運(yùn)行結(jié)果:
>> sudoku
0 0 0 0 0 0 0 0 0
0 2 3 0 0 0 7 8 0
1 0 0 4 0 6 0 0 9
4 0 0 0 5 0 0 0 1
9 0 0 0 0 0 0 0 6
0 6 0 0 0 0 0 9 0
0 0 5 0 0 0 8 0 0
0 0 0 3 0 1 0 0 0
0 0 0 0 9 0 0 0 0
5 4 9 7 3 8 1 6 2
6 2 3 9 1 5 7 8 4
1 8 7 4 2 6 3 5 9
4 3 8 6 5 9 2 7 1
9 5 1 8 7 2 4 3 6
7 6 2 1 4 3 5 9 8
3 9 5 2 6 4 8 1 7
2 7 6 3 8 1 9 4 5
8 1 4 5 9 7 6 2 3