前言
老婆最近迷上了数独，还给我拍了张照片，初步了解了规则之后，试着玩了一下，浪费了半个小时还做不出来，于是想到了用matlab算。
提示：小白diy的代码，不够优美，但很好懂
一、数独的规则
在9×9的方阵中，根据已有数字，在空位上填入1~9，使得：
1.同一行数字不重复；
2.同一列数字不重复；
3.粗线所分隔出的9宫格同一格内数字不重复。
二、算法
1.思路
一开始按枚举法，走迷宫的思路，从左至右，从上至下测试，遇到走不下去，就换数字重新走，结果这种思路机器一直都在运行，算法复杂度太高（70多个格子，每个格子平均3-4个可能性）；
请教了老婆，才知道，一般人在做数独时，是先把确定的填下，再挑解少的试。于此得到启发：
1.先算每个格子的解集；
2.只有一个解的，那肯定是答案，就先填入，但不是都填，而是随机选一格，填入；
3.如果最少的都是多个解，就在解少的格子中随机选一格填入解空间的第一个数；
4.前面填过数字的格，它的解集中需要删除已经填过的数。
4.一次填一个数，填完了如果还有空格，就继续按上述法则填空；
5.如果按上述法则，填不下去了，说明路子走错了，就清空方阵重新开始上述步骤。
由于有“随机选一格”存在，算法往往不会超过2秒，就能给出正确答案。
2.流程图
3.Matlab代码
首先自定义一个function，输入A表示方阵，i表示行序号，j表示列序号，能够计算空格的解集data：
function [data] = ketianrushu(A,i,j)
if A(i,j)==0
if i<=3&&j<=3 %在a11
a11=A(1:3,1:3);
paichu = [a11(a11~=0)];
else if i<=3&&j<=6 %在a12
a12=A(1:3,4:6);
paichu = [a12(a12~=0)];
else if i<=3&&j<=9 %在a13
a13=A(1:3,7:9);
paichu = [a13(a13~=0)];
else if i<=6&&j<=3 %在a21
a21=A(4:6,1:3);
paichu = [a21(a21~=0)];
else if i<=6&&j<=6 %在a22
a22=A(4:6,4:6);
paichu = [a22(a22~=0)];
else if i<=6&&j<=9 %在a23
a23=A(4:6,7:9);
paichu = [a23(a23~=0)];
else if i<=9&&j<=3 %在a31
a31=A(7:9,1:3);
paichu = [a31(a31~=0)];
else if i<=9&&j<=6 %在a32
a32=A(7:9,4:6);
paichu = [a32(a32~=0)];
else
a33=A(7:9,7:9);
paichu = [a33(a33~=0)];
end
end
end
end
end
end
end
end
x=A(i,:);
paichuhang = [x(find(x~=0))]';
%不与所在列重复
x=A(:,j);
paichulie = [x(find(x~=0))];
pc = union(union(paichu,paichuhang),paichulie);
psb = [1,2,3,4,5,6,7,8,9];
data = setdiff(psb, pc);
else
data=[];
end
再自定义另一个function，能把格子的序号k（1~81）映射为i,j（行序号、列序号）：
function [i,j] = yingshe(k)
%yingshe 把k转化为i j
% 此处显示详细说明
if mod(k,9)~=0
i=floor(k/9)+1;
j=k-9*(i-1);
else
i=k/9;
j=9;
end
然后是主程序。
A=[5,7,0,0,1,0,3,0,0;
0,0,0,5,0,0,9,0,7;
8,3,0,0,0,0,0,0,0;
0,0,0,0,3,0,0,2,0;
6,0,0,4,0,5,0,0,9;
0,1,0,0,6,0,0,0,0;
0,0,0,0,0,7,0,0,4;
2,0,5,0,0,0,0,9,0;
0,0,7,0,5,0,0,1,2;]
A0=A;
data = cell(1,81);
len_data = zeros(1,81);
while ismember(0,A)
for k=1:81
[i,j]=yingshe(k);
if A0(i,j)==0
data{k}=ketianrushu(A,i,j);
end
end %计算当前矩阵各空格的可填入数
for k=1:81
len_data(k)=length(data{k});
end %计算当前矩阵各空格可填入数个数
A1=A;
if ismember(1,len_data) %有唯一解时
id = find(len_data==1);%算出都有哪些格有唯一解
id_suiji = id(ceil(rand*length(id)));%随机选一格填数
[i,j] = yingshe(id_suiji);%算出这一格的行列
A(i,j) = data{id_suiji};%直接填入这一格可以填的唯一数
data{id_suiji}=[];%这一格可以填的唯一数删除；
else if ismember(2,len_data) %最少的有两个解时
id = find(len_data==2);%算出都有哪些格有唯二解
id_suiji = id(ceil(rand*length(id))); %随机选一格填数
[i,j] = yingshe(id_suiji);%算出这一格的行列
A(i,j) = data{id_suiji}(1);%直接填入这一格可以填的第一个数
data{id_suiji}(1)=[];%这一格可以填的第一个数删除
else if ismember(3,len_data) %最少的有三个解时
id = find(len_data==3);%算出都有哪些格有唯三解
id_suiji = id(ceil(rand*length(id)));%随机选一格填数
[i,j]=yingshe(id_suiji);%算出这一格的行列
A(i,j) = data{id_suiji}(1);
data{id_suiji}(1)=[];%这一格可以填的第一个数删除
else if ismember(4,len_data)
id = find(len_data==4);%算出都有哪些格有唯四解
id_suiji = id(ceil(rand*length(id)));%随机选一格填数
[i,j]=yingshe(id_suiji);%算出这一格的行列
A(i,j) = data{id_suiji}(1);
data{id_suiji}(1)=[];%这一格可以填的第一个数删除
else if ismember(5,len_data)
id = find(len_data==5);%算出都有哪些格有唯五解
id_suiji = id(ceil(rand*length(id)));%随机选一格填数
[i,j]=yingshe(id_suiji);%算出这一格的行列
A(i,j) = data{id_suiji}(1);
data{id_suiji}(1)=[];%这一格可以填的第一个数删除
else if ismember(6,len_data)
id = find(len_data==6);%算出都有哪些格有唯六解
id_suiji = id(ceil(rand*length(id)));%随机选一格填数
[i,j]=yingshe(id_suiji);%算出这一格的行列
A(i,j) = data{id_suiji}(1);
data{id_suiji}(1)=[];%这一格可以填的第一个数删除
else if ismember(7,len_data)
id = find(len_data==7);%算出都有哪些格有唯七解
id_suiji = id(ceil(rand*length(id)));%随机选一格填数
[i,j]=yingshe(id_suiji);%算出这一格的行列
A(i,j) = data{id_suiji}(1);
data{id_suiji}(1)=[];%这一格可以填的第一个数删除
else if ismember(8,len_data)
id = find(len_data==8);%算出都有哪些格有唯八解
id_suiji = id(ceil(rand*length(id)));%随机选一格填数
[i,j]=yingshe(id_suiji);%算出这一格的行列
A(i,j) = data{id_suiji}(1);
data{id_suiji}(1)=[];%这一格可以填的第一个数删除
else if ismember(9,len_data)
id = find(len_data==9);%算出都有哪些格有唯九解
id_suiji = id(ceil(rand*length(id)));%随机选一格填数
[i,j]=yingshe(id_suiji);%算出这一格的行列
A(i,j) = data{id_suiji}(1);
data{id_suiji}(1)=[];%这一格可以填的第一个数删除
end
end
end
end
end
end
end
end
end
if A1==A %如果经过以上操作，数字不再变化
A=A0;%从头开始
end
end
A
总结
运行上述代码，可以得到最初图中那道数独题目的答案是：
可惜最后我老婆说题目不是我自己做的。。。白瞎=。=