Diaries – 第 26 页 – Dust & Light

Matlab求解数独

2020年10月7日 by xuzp·0评论

前几年搞的小程序，不多说，上代码，走的深度优先，我自己不习惯写代码加注释，想到哪里写到哪里，自己看看就好。

数独输入为c矩阵，需要填空的地方为0

c=[0 0 5 3 0 0 0 0 0;
   8 0 0 0 0 0 0 2 0;
   0 7 0 0 1 0 5 0 0;
   4 0 0 0 0 5 3 0 0;
   0 1 0 0 7 0 0 0 6;
   0 0 3 2 0 0 0 8 0;
   0 6 0 5 0 0 0 0 9;
   0 0 4 0 0 0 0 3 0;
   0 0 0 0 0 9 7 0 0];
treenumx=[];
treenumy=[];
for i=1:9
  for j=1:9
    if c(i,j)>0
     tree(i,j).x=c(i,j);
    else
     un1=union(c(i,:),c(:,j));
     un1=union(un1,c(floor((i-1)/3)*3+1:floor((i-1)/3)*3+3,floor((j-1)/3)*3+1:floor((j-1)/3)*3+3));
     tree(i,j).x=setdiff([1:9],un1);
     treenumx=[treenumx i];
     treenumy=[treenumy j];
    end
  end
end
layout=1;
c2=c;
tab=ones(length(treenumx),1);
noden=zeros(length(treenumx),1);
for k=1:length(treenumx)
  noden(k)=length(tree(treenumx(k),treenumy(k)).x);
end
if sum(noden==0)>0
  error('Please check input')
end
while 1 
  i=treenumx(layout);
  j=treenumy(layout);
  squnear=c2(floor((i-1)/3)*3+1:floor((i-1)/3)*3+3,floor((j-1)/3)*3+1:floor((j-1)/3)*3+3);
  nodes=tree(treenumx(layout),treenumy(layout)).x(tab(layout));
  if nodes~=c(i,j) && (isempty(intersect(nodes,c2(i,:)))) && (isempty(intersect(nodes,c2(:,j)))) && (isempty(intersect(nodes,squnear)))
      c2(i,j)=nodes;
     
      layout=layout+1;
      if layout>length(treenumx)
          break
      end
  else
      if tab(layout)<noden(layout)
          tab(layout)=tab(layout)+1;
      else
          tab(layout)=1;
          c2(i,j)=0;
          layout=layout-1;
      end
  end 
%  display([num2str(layout) '-' num2str(tab(layout))]);
end
c2