【讨论】用0-1规划求解八皇后问题

qibbxxt

前段时间写过剔除法求解八皇后问题，可以求出所有解，今天用0-1规划写了一个程序，每次只能求出一个解

1. 
   
2. clear;clc;close all
   
3. N=8;
   
4. c=ones(N);
   
5. % 行求和
   
6. blkele=num2cell(c,2);
   
7. A1=blkdiag(blkele{:});
   
8. % 列求和
   
9. A2=repmat(eye(N),1,N);
   
10. Aeq=[A1;A2];
    
11. beq=ones(2*N,1);
    
12. % 斜线情况判断
    
13. M=N-2;
    
14. A=zeros(4*M+2,N*N);
    
15. d{1}=arrayfun(@(i)find(diag(diag(c,i),i)),-M:M,'UniformOutput',0);
    
16. d{2}=arrayfun(@(i)find(fliplr(diag(diag(c,i),i))),-M:M,'UniformOutput',0);
    
17. d0=cat(1,d{:});
    
18. linearIndex=arrayfun(@(x)sub2ind(size(A),x+zeros(1,length(d0{x})),...
    
19.     d0{x}'),1:numel(d0),'UniformOutput',0);
    
20. A(cell2mat(linearIndex))=1;
    
21. b=ones(4*M+2,1);
    
22. x=bintprog([],A,b,Aeq,beq);
    
23. Res=reshape(x,[],N);
    

复制代码

下面是我用lingo写的一个版本，还有待改进

1. 
   
2. model:
   
3. sets:
   
4. Node/1..8/:N;
   
5. link(Node,Node):x;
   
6. plus1/1..15/:;
   
7. minus1/1..6/:;
   
8. endsets
   
9. @for(Node(i):@sum(Node(j):x(i,j))=1);
   
10. @for(Node(j):@sum(Node(i):x(i,j))=1);
    
11. @for(plus1(k)|k#ge#3:@sum(link(i,j)|i+j#eq#k:x(i,j))<1);
    
12. @for(minus1(k):@sum(link(i,j)|i-j#eq#k:x(i,j))<1);
    
13. @for(minus1(k):@sum(link(i,j)|j-i#eq#k:x(i,j))<1);
    
14. @sum(Node(i):x(i,i))<1;
    
15. @for(link(i,j):@bin(x(i,j)));
    

复制代码