数独游戏程序.docx
《数独游戏程序.docx》由会员分享，可在线阅读，更多相关《数独游戏程序.docx（21页珍藏版）》请在冰点文库上搜索。
数独游戏程序
%数独游戏程序，可以破解绝大部分数独题。
%用法：
将所有文件复制到MATLAB工作目录下，或是将MATLAB工作目录修改为本文件夹所在路径。
%A是一个初始的99的方阵，空白处用0代替，调用TT=shudu（A）,则生成结果。
functionTT=fill1（A）
T=A;
i=1;
n1=0;n2=0;
flag1=judge1（T）;
whilei<10
n1=0;n2=0;
forj=1:
9
ifT（i,j）==0&i~=flag1（:
1）&j~=flag1（:
2）&iden（i,j,1,T）==0
n1=n1+1;
end
end
ifn1==1
forj=1:
9
ifT（i,j）==0&i~=flag1（:
1）&j~=flag1（:
2）&iden（i,j,1,T）==0
T（i,j）=1;
flag1=judge1（T）;
end
end
end
forj=1:
9
ifT（j,i）==0&j~=flag1（:
1）&i~=flag1（:
2）&iden（j,i,1,T）==0
n2=n2+1;
end
end
ifn2==1
forj=1:
9
ifT（j,i）==0&j~=flag1（:
1）&i~=flag1（:
2）&iden（j,i,1,T）==0
T（j,i）=1;
flag1=judge1（T）;
end
end
end
ifn1==1|n2==1
i=0;
end
i=i+1;
end
TT=T;
functionTT=fill2（A）
T=A;
i=1;
n1=0;n2=0;
flag2=judge2（T）;
whilei<10
n1=0;n2=0;
forj=1:
9
ifT（i,j）==0&i~=flag2（:
1）&j~=flag2（:
2）&iden（i,j,2,T）==0
n1=n1+1;
end
end
ifn1==1
forj=1:
9
ifT（i,j）==0&i~=flag2（:
1）&j~=flag2（:
2）&iden（i,j,2,T）==0
T（i,j）=2;
flag2=judge2（T）;
end
end
end
forj=1:
9
ifT（j,i）==0&j~=flag2（:
1）&i~=flag2（:
2）&iden（j,i,2,T）==0
n2=n2+1;
end
end
ifn2==1
forj=1:
9
ifT（j,i）==0&j~=flag2（:
1）&i~=flag2（:
2）&iden（j,i,2,T）==0
T（j,i）=2;
flag2=judge2（T）;
end
end
end
ifn1==1|n2==1
i=0;
end
i=i+1;
end
TT=T;
functionTT=fill3（A）
T=A;
i=1;
n1=0;n2=0;
flag3=judge3（T）;
whilei<10
n1=0;n2=0;
forj=1:
9
ifT（i,j）==0&i~=flag3（:
1）&j~=flag3（:
2）&iden（i,j,3,T）==0
n1=n1+1;
end
end
ifn1==1
forj=1:
9
ifT（i,j）==0&i~=flag3（:
1）&j~=flag3（:
2）&iden（i,j,3,T）==0
T（i,j）=3;
flag3=judge3（T）;
end
end
end
forj=1:
9
ifT（j,i）==0&j~=flag3（:
1）&i~=flag3（:
2）&iden（j,i,3,T）==0
n2=n2+1;
end
end
ifn2==1
forj=1:
9
ifT（j,i）==0&j~=flag3（:
1）&i~=flag3（:
2）&iden（j,i,3,T）==0
T（j,i）=3;
flag3=judge3（T）;
end
end
end
ifn1==1|n2==1
i=0;
end
i=i+1;
end
TT=T;
functionTT=fill4（A）
T=A;
i=1;
n1=0;n2=0;
flag4=judge4（T）;
whilei<10
n1=0;n2=0;
forj=1:
9
ifT（i,j）==0&i~=flag4（:
1）&j~=flag4（:
2）&iden（i,j,4,T）==0
n1=n1+1;
end
end
ifn1==1
forj=1:
9
ifT（i,j）==0&i~=flag4（:
1）&j~=flag4（:
2）&iden（i,j,4,T）==0
T（i,j）=4;
flag4=judge4（T）;
end
end
end
forj=1:
9
ifT（j,i）==0&j~=flag4（:
1）&i~=flag4（:
2）&iden（j,i,4,T）==0
n2=n2+1;
end
end
ifn2==1
forj=1:
9
ifT（j,i）==0&j~=flag4（:
1）&i~=flag4（:
2）&iden（j,i,4,T）==0
T（j,i）=4;
flag4=judge4（T）;
end
end
end
ifn1==1|n2==1
i=0;
end
i=i+1;
end
TT=T;
functionTT=fill5（A）
T=A;
i=1;
n1=0;n2=0;
flag5=judge5（T）;
whilei<10
n1=0;n2=0;
forj=1:
9
ifT（i,j）==0&i~=flag5（:
1）&j~=flag5（:
2）&iden（i,j,5,T）==0
n1=n1+1;
end
end
ifn1==1
forj=1:
9
ifT（i,j）==0&i~=flag5（:
1）&j~=flag5（:
2）&iden（i,j,5,T）==0
T（i,j）=5;
flag5=judge5（T）;
end
end
end
forj=1:
9
ifT（j,i）==0&j~=flag5（:
1）&i~=flag5（:
2）&iden（j,i,5,T）==0
n2=n2+1;
end
end
ifn2==1
forj=1:
9
ifT（j,i）==0&j~=flag5（:
1）&i~=flag5（:
2）&iden（j,i,5,T）==0
T（j,i）=5;
flag5=judge5（T）;
end
end
end
ifn1==1|n2==1
i=0;
end
i=i+1;
end
TT=T;
functionTT=fill6（A）
T=A;
i=1;
n1=0;n2=0;
flag6=judge6（T）;
whilei<10
n1=0;n2=0;
forj=1:
9
ifT（i,j）==0&i~=flag6（:
1）&j~=flag6（:
2）&iden（i,j,6,T）==0
n1=n1+1;
end
end
ifn1==1
forj=1:
9
ifT（i,j）==0&i~=flag6（:
1）&j~=flag6（:
2）&iden（i,j,6,T）==0
T（i,j）=6;
flag6=judge6（T）;
end
end
end
forj=1:
9
ifT（j,i）==0&j~=flag6（:
1）&i~=flag6（:
2）&iden（j,i,6,T）==0
n2=n2+1;
end
end
ifn2==1
forj=1:
9
ifT（j,i）==0&j~=flag6（:
1）&i~=flag6（:
2）&iden（j,i,6,T）==0
T（j,i）=6;
flag6=judge6（T）;
end
end
end
ifn1==1|n2==1
i=0;
end
i=i+1;
end
TT=T;
functionTT=fill7（A）
T=A;
i=1;
n1=0;n2=0;
flag7=judge7（T）;
whilei<10
n1=0;n2=0;
forj=1:
9
ifT（i,j）==0&i~=flag7（:
1）&j~=flag7（:
2）&iden（i,j,7,T）==0
n1=n1+1;
end
end
ifn1==1
forj=1:
9
ifT（i,j）==0&i~=flag7（:
1）&j~=flag7（:
2）&iden（i,j,7,T）==0
T（i,j）=7;
flag7=judge7（T）;
end
end
end
forj=1:
9
ifT（j,i）==0&j~=flag7（:
1）&i~=flag7（:
2）&iden（j,i,7,T）==0
n2=n2+1;
end
end
ifn2==1
forj=1:
9
ifT（j,i）==0&j~=flag7（:
1）&i~=flag7（:
2）&iden（j,i,7,T）==0
T（j,i）=7;
flag7=judge7（T）;
end
end
end
ifn1==1|n2==1
i=0;
end
i=i+1;
end
TT=T;
functionTT=fill8（A）
T=A;
i=1;
n1=0;n2=0;
flag8=judge8（T）;
whilei<10
n1=0;n2=0;
forj=1:
9
ifT（i,j）==0&i~=flag8（:
1）&j~=flag8（:
2）&iden（i,j,8,T）==0
n1=n1+1;
end
end
ifn1==1
forj=1:
9
ifT（i,j）==0&i~=flag8（:
1）&j~=flag8（:
2）&iden（i,j,8,T）==0
T（i,j）=8;
flag8=judge8（T）;
end
end
end
forj=1:
9
ifT（j,i）==0&j~=flag8（:
1）&i~=flag8（:
2）&iden（j,i,8,T）==0
n2=n2+1;
end
end
ifn2==1
forj=1:
9
ifT（j,i）==0&j~=flag8（:
1）&i~=flag8（:
2）&iden（j,i,8,T）==0
T（j,i）=8;
flag8=judge8（T）;
end
end
end
ifn1==1|n2==1
i=0;
end
i=i+1;
end
TT=T;
functionTT=fill9（A）
T=A;
i=1;
n1=0;n2=0;
flag9=judge9（T）;
whilei<10
n1=0;n2=0;
forj=1:
9
ifT（i,j）==0&i~=flag9（:
1）&j~=flag9（:
2）&iden（i,j,9,T）==0
n1=n1+1;
end
end
ifn1==1
forj=1:
9
ifT（i,j）==0&i~=flag9（:
1）&j~=flag9（:
2）&iden（i,j,9,T）==0
T（i,j）=9;
flag9=judge9（T）;
end
end
end
forj=1:
9
ifT（j,i）==0&j~=flag9（:
1）&i~=flag9（:
2）&iden（j,i,9,T）==0
n2=n2+1;
end
end
ifn2==1
forj=1:
9
ifT（j,i）==0&j~=flag9（:
1）&i~=flag9（:
2）&iden（j,i,9,T）==0
T（j,i）=9;
flag9=judge9（T）;
end
end
end
ifn1==1|n2==1
i=0;
end
i=i+1;
end
TT=T;
functionpp=iden（x,y,num,T）
f=0;
fork=0:
2
form=0:
2
ifx>=1+3*k&x<=3*（k+1）&y>=1+3*m&y<=3*（m+1）
fori=1:
3
forj=1:
3
ifT（i+3*k,j+3*m）==num
f=1;
end
end
end
end
end
end
pp=f;
functionflag1=judge1（A）
T=A;
k=1;
fori=1:
9
forj=1:
9
ifT（i,j）==1
flag1（k,:
）=[i,j];
k=k+1;
end
end
end
functionflag2=judge2（A）
T=A;
k=1;
fori=1:
9
forj=1:
9
ifT（i,j）==2
flag2（k,:
）=[i,j];
k=k+1;
end
end
end
functionflag3=judge3（A）
T=A;
k=1;
fori=1:
9
forj=1:
9
ifT（i,j）==3
flag3（k,:
）=[i,j];
k=k+1;
end
end
end
functionflag4=judge4（A）
T=A;
k=1;
fori=1:
9
forj=1:
9
ifT（i,j）==4
flag4（k,:
）=[i,j];
k=k+1;
end
end
end
functionflag5=judge5（A）
T=A;
k=1;
fori=1:
9
forj=1:
9
ifT（i,j）==5
flag5（k,:
）=[i,j];
k=k+1;
end
end
end
functionflag6=judge6（A）
T=A;
k=1;
fori=1:
9
forj=1:
9
ifT（i,j）==6
flag6（k,:
）=[i,j];
k=k+1;
end
end
end
functionflag7=judge7（A）
T=A;
k=1;
fori=1:
9
forj=1:
9
ifT（i,j）==7
flag7（k,:
）=[i,j];
k=k+1;
end
end
end
functionflag8=judge8（A）
T=A;
k=1;
fori=1:
9
forj=1:
9
ifT（i,j）==8
flag8（k,:
）=[i,j];
k=k+1;
end
end
end
functionflag9=judge9（A）
T=A;
k=1;
fori=1:
9
forj=1:
9
ifT（i,j）==9
flag9（k,:
）=[i,j];
k=k+1;
end
end
end
functionTT=shudu（A）
T=A;
f=1;n=0;
whilef==1
T=fill1（T）;
T=fill2（T）;
T=fill3（T）;
T=fill4（T）;
T=fill5（T）;
T=fill6（T）;
T=fill7（T）;
T=fill8（T）;
T=fill9（T）;
t1=size（judge1（T））;t2=size（judge2（T））;t3=size（judge3（T））;
t4=size（judge4（T））;t5=size（judge5（T））;t6=size（judge6（T））;
t7=size（judge7（T））;t8=size（judge8（T））;t9=size（judge9（T））;
ift1
（1）==9&t2
（1）==9&t3
（1）==9&t4
（1）==9&t5
（1）==9&t6
（1）==9&t7
（1）==9&t8
（1）==9&t9
（1）==9|n==100
f=0;
end
n=n+1;
end
TT=T;
functionX=sudoku（X）
%SUDOKU SolveSudokuusingrecursivebacktracking.1_8G0g（r;[0w1k1D
% sudoku（X）,expectsa9-by-9arrayX.:
~0R/y4o$G6k
%Fillinall“singletons”.
%Cisacellarrayofcandidatevectorsforeachcell.
%sisthefirstcell,ifany,withonecandidate.,[0\（D8[&E1r）S
%eisthefirstcell,ifany,withnocandidates.:
b8c,E*_3c7R3P3x
[C,s,e]=candidates（X）;%] Q!
v:
g$E$j,E+R
while~isempty（s）&&isempty（e）,z*{5^"Z;Z&X,M,P
X（s）=C{s};!
N;G9K7a#[6r
[C,s,e]=candidates（X）;1T3G9{）Z6J4V&e#]$Y;a:
[#Y2Y
end
%Returnforimpossiblepuzzles.#}2I0I）Z2M&@;v,E1~
if~isempty（e）
return'];j%K（b:
Y$I-k$r
end
%Recursivebacktracking.
ifany（X（:
）==0）
Y=X;%F5Q!
P&H#j/Q6K-]*a）~6t-c
z=find（X（:
）==0,1）; %Thefirstunfilledcell.
forr=[C{z}] %Iterateovercandidates.
X=Y;
X（z）=r; %Insertatentativevalue.!
W4b9~-P%f（b7q9c+r0s4|.a）L
X=sudoku（X）; %Recursivecall.1w:
h$W5C!
F%c
ifall（X（:
）>0） %Foundasolution.&}*h7S!
L:
M9m6R）N
return5~$~3u1q5E5y5^3l
end,T$z8T1N%b）E;~:
e4N
end
end:
Y）I%M$J D）x（X'k6[
%------------------------------m$Y%[2h$I7l&J%H8l-V7l
function[C,s,e]=candidates（X）
C=cell（9,9）;!
g+O*l2e7g#k6N
tri=@（k）3*ceil（k/3-1）+（1:
3）;
forj=1:
9
fori=1:
9"u"T1_1a;w#["M）u"^3k!
B1O
ifX（i,j）==09L）P4t1x&M2S3o1j）h
z=1:
9;5Q7X }）|/R$q
z（nonzeros（X（i,:
）））=0;
z（nonzeros（X（:
j）））=0;J9k+]'{:
f#b%| z（nonzeros（X（tri（i）,tri（j））））=0;
C{i,j}=nonzeros（z）’;
end
end
end-Y"Q.}.[#M
L=cellfun（@length,C）; %Numberofcandidates.
s=find（X==0&L==1,1）;!
G'~"A!
I8p（Y*g3P4K
e=find（X==0&L==0,1）;%S-C&q）D9H#n5\6{
end%candidates%p2_/r*u,o4E
end%sudoku
升级会员 