|
读书时,饭间看青年报,上面每期都有9*9的九宫阵.心血来潮,编写了matlab程序,将之求解完毕.
输入数据为9*9的数组.
思路是,首先根据规则,确定每个方格中可能值,首先确定唯一可能值,进行试探时,也选取可能性小的那个方格进行处理.走不通时,退栈,更新数值,重新试探.
程序源代码如下:(很多有些记不清楚了)
function [JGTNData]=JGZ()
clear;
JGZ=zeros(9,9);
AllData(1:9)=3;
JGTData=zeros(9,9,11);
for i=1:9
for j=1:9
for k=1:9
JGTData(i,j,k)=k;
end
JGTData(i,j,10)=9;
JGTData(i,j,11)=0;
end
end
% Inputdata=[1,1,6;1,2,9;1,4,2;1,8,3;2,1,7;2,3,5;2,4,8;2,8,2;3,2,3;3,3,2;3,4,5;3,8,8;4,1,2;4,3,4;4,9,5;5,2,6;5,5,9;5,9,3;6,6,2;6,8,7;7,1,5;7,2,4;7,5,7;8,3,9;8,5,2;8,9,1;9,4,9;9,7,8] ;
%Inputdata=[1,1,8;1,4,1;1,5,4;1,7,7;2,1,7;2,6,8;2,8,1;2,9,6;3,4,6;3,5,9;3,8,8;3,9,3;4,2,5;4,5,2;5,1,3;6,3,8;6,6,4;6,8,6;6,9,5;7,3,5;7,9,2;8,1,4;9,2,2;9,4,9;9,5,1;9,7,8];
%Inputdata=[1,3,6;1,5,2;1,7,7;1,8,8;2,2,1;2,4,9;2,6,7;2,9,6;3,6,6;3,7,3;4,2,9;4,4,8;5,3,4;5,5,6;5,8,2;6,1,2;6,6,1;6,7,8;6,8,9;7,3,3;7,8,5;8,2,4;8,4,2;8,9,8;9,1,1;9,4,6;9,6,5;9,7,4];
% Inputdata=[1,1,6;1,4,8;2,1,5;2,8,2;3,6,5;3,7,1;4,1,3;4,6,2;4,8,8;4,9,7;5,3,2;5,4,7;5,7,3;5,9,9;6,2,4;6,5,3;6,9,6;7,1,7;7,4,4;7,5,9;7,7,6;8,2,6;8,5,5;8,6,8;8,8,7;9,3,5;9,5,1;9,9,4];
Inputdata=[1,1,6;1,4,8;2,1,5;2,8,2;3,6,5;3,7,1;4,1,3;4,6,2;4,8,8;4,9,7;5,3,2;5,4,7;5,7,3;5,9,9;6,2,4;6,5,3;6,9,6;7,1,7;7,4,4;7,5,9;7,7,6;8,2,6;8,5,5;8,6,8;8,8,7;9,3,5;9,5,1;9,9,4];
xsize=size(Inputdata);
for i=1:xsize(1)
tempi=Inputdata(i,1);
tempj=Inputdata(i,2);
JGZ(tempi,tempj)=Inputdata(i,3);
AllData(JGZ(tempi,tempj))=AllData(JGZ(tempi,tempj))-1;
JGTData(tempi,tempj,1:9)=0;
JGTData(tempi,tempj,JGZ(tempi,tempj))=JGZ(tempi,tempj);
JGTData(tempi,tempj,10)=1;
JGTData(tempi,tempj,11)=JGZ(tempi,tempj);
end
JGZ;
JGTData;
[JGZ1,JGTData1]=PDDJGT(JGZ,JGTData);
JGZ=JGZ1;
JGTData=JGTData1;
%%%%%%%%%%判断是否有可以确定的数
for i=1:9
for j=1:9
if JGTData(i,j,10)==1 & JGTData(i,j,11)==0%可以确定
JGZ(i,j)=max(JGTData(i,j,1:9));
JGTData(i,j,11)=JGZ(i,j);
end
end
end
JGZ;
JGTData(:,:,10);
%%%%%%%%
JGTPD=zeros(9,9);
while max(max(JGTPD~=JGTData(:,:,10)))
JGTPD=JGTData(:,:,10);
%%%%%%%%%%%第二次
[JGZ1,JGTData1]=PDDJGT(JGZ,JGTData);
JGZ=JGZ1;
JGTData=JGTData1;
%%%%%%%%%%判断是否有可以确定的数
for i=1:9
for j=1:9
if JGTData(i,j,10)==1 & JGTData(i,j,11)==0%可以确定
if max(JGTData(i,j,1:9))>0 %有错
JGZ(i,j)=max(JGTData(i,j,1:9));
JGTData(i,j,11)=JGZ(i,j);
end
end
end
end
JGZ;
JGTData(:,:,10);
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%加入一个试探值
NTData=1;
ForT=0;
TFT=0;%有无错
%xsize=find(JGTPD==2);
%xsize=xsize(1);
%while xsize
while NTData>=1 & ForT==0
NTData=1;
JGTN=1;
JGTNData(JGTN,:,:)=zeros(9,9);
while max(max(JGTPD~=ones(9,9))) & TFT==0
while max(max(JGTPD~=ones(9,9))) & TFT==0
xsize=find(JGTPD==2);
if xsize~=[]
xsize=xsize(1);
tempi=mod(xsize,9);
if tempi==0
tempi=9;
tempj=floor(xsize/9);
else
tempj=floor(xsize/9)+1;
end
tempsize=find(JGTData(tempi,tempj,1:9)>0);
TData(NTData,1:4)=[tempi,tempj,(JGTData(tempi,tempj,tempsize(1))),(JGTData(tempi,tempj,tempsize(2)))];%加入值同时保留另外一个值
TAData(NTData,1:9,1:9,1:11)=JGTData;
TAJGZ(NTData,1:9,1:9)=JGZ;
JGZ(tempi,tempj)=TData(NTData,3);
JGTData(tempi,tempj,1:9)=0;
JGTData(tempi,tempj,JGZ(tempi,tempj))=JGZ(tempi,tempj);
JGTData(tempi,tempj,10)=1;
JGTData(tempi,tempj,11)=JGZ(tempi,tempj);
NTData=NTData+1;
TFT=0;
%%%%%%%%%%%%%重新判断
JGTPD=zeros(9,9);
while max(max(JGTPD~=JGTData(:,:,10)))
JGTPD=JGTData(:,:,10);
%%%%%%%%%%%第二次
[JGZ1,JGTData1]=PDDJGT(JGZ,JGTData);
JGZ=JGZ1;
JGTData=JGTData1;
%%%%%%%%%%判断是否有可以确定的数
for i=1:9
for j=1:9
if JGTData(i,j,10)==1 & JGTData(i,j,11)==0%可以确定
if max(JGTData(i,j,1:9))>0 %有错
JGZ(i,j)=max(JGTData(i,j,1:9));
JGTData(i,j,11)=JGZ(i,j);
else
TFT=1;%有错
end
end
end
end
JGZ;
JGTData(:,:,10);
end%%%while
if min(min(JGTPD))==0
TFT=1;
end
else%%%%%%%%%%%无法填写
TFT=1;%有错
end
end%%%%%while
if TFT==1 %%因为有错退出
if NTData>0
NTData=NTData-1;
tempi=TData(NTData,1);
tempj=TData(NTData,2);
for i=1:9
for j=1:9
JGTData(i,j,1:11)=TAData(NTData,i,j,1:11);
JGZ(i,j)=TAJGZ(NTData,i,j);
end
end
% JGTData=TAData(NTData,1:9,1:9,1:11);
JGZ(tempi,tempj)=TData(NTData,4);
JGTData(tempi,tempj,1:9)=0;
JGTData(tempi,tempj,JGZ(tempi,tempj))=JGZ(tempi,tempj);
JGTData(tempi,tempj,10)=1;
JGTData(tempi,tempj,11)=JGZ(tempi,tempj);
JGTPD=JGTData(:,:,10);
TFT=0;
else
JGTPD=ones(9,9);
end%%if
end%%%if
end%%%while
JGTNData(JGTN,:,:)=JGZ;
JGTN=JGTN+1;
if TFT==1 %%因为有错退出
if NTData>1
NTData=NTData-1;
tempi=TData(NTData,1);
tempj=TData(NTData,2);
for i=1:9
for j=1:9
JGTData(i,j,1:11)=TAData(NTData,i,j,1:11);
JGZ(i,j)=TAJGZ(NTData,i,j);
end
end
% JGTData=TAData(NTData,1:9,1:9,1:11);
JGZ(tempi,tempj)=TData(NTData,4);
JGTData(tempi,tempj,1:9)=0;
JGTData(tempi,tempj,JGZ(tempi,tempj))=JGZ(tempi,tempj);
JGTData(tempi,tempj,10)=1;
JGTData(tempi,tempj,11)=JGZ(tempi,tempj);
JGTPD=JGTData(:,:,10);
TFT=0;
else
JGTPD=ones(9,9);
ForT=1;
end%%if
end%%%if
JGTPD=zeros(9,9);
NTData;
JGZ;
end%%while NData==0
function [JGZ2,JGTData2]=PDDJGT(JGZ1,JGTData1)
%%%%%%%%%%%%%%%%%%%%%判断横
for i=1:9
for j=1:9
if JGZ1(i,j)>0 %有数据,清除其他中这个数据
for k=1:9%横
if j~=k
if JGTData1(i,k,JGZ1(i,j))>0
JGTData1(i,k,JGZ1(i,j))=0;
JGTData1(i,k,10)=JGTData1(i,k,10)-1;
end
end
end
for k=1:9%列
if i~=k
if JGTData1(k,j,JGZ1(i,j))>0
JGTData1(k,j,JGZ1(i,j))=0;
JGTData1(k,j,10)=JGTData1(k,j,10)-1;
end
end
end
%%%%%%%%%%%%%%%%%%%%小格
for i1=(ceil(i/3)-1)*3+1:(ceil(i/3)-1)*3+3
for j1=(ceil(j/3)-1)*3+1:(ceil(j/3)-1)*3+3
if i1~=i & j1~=j
if JGTData1(i1,j1,JGZ1(i,j))>0
JGTData1(i1,j1,JGZ1(i,j))=0;
JGTData1(i1,j1,10)=JGTData1(i1,j1,10)-1;
end
end
end
end
end
end
end
JGTData2=JGTData1;
JGZ2=JGZ1;
end
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-10-20 04:49
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社