在国际象棋中,能否在空棋盘上摆放八个皇后,并使其中任意两个皇后不能在同一行或同
一列或同一对角线上。
编写完整的摆放八皇后问题的程序。要求:第一个皇后的起始位置由键盘输入,国际象棋
的棋盘为 8*8 的方格。
不想动脑子,给个整数规划法:
row=input('请输入第一个皇后所在行:');
col=input('请输入第一个皇后所在列:');
A=zeros(8);A(row,col)=1;
Aeq1=zeros(1,64);Aeq1(A==1)=1;
beq1=1;
% 每行列只有一个棋子
Aeq2=zeros(8,64);
Aeq3=zeros(8,64);
for i=1:8
Aeq2(i,(i-1)*8+1:i*8)=1;
Aeq3(i,i:8:64)=1;
end
beq2=ones(8,1);
beq3=ones(8,1);
% 每斜线只有一个棋子
[X,Y]=meshgrid(1:8);
A1=zeros(15,64);
A2=zeros(15,64);
for i=1:15
A1(i,(X+Y)==i+1)=1;
A2(i,(X-Y)==i-8)=1;
end
b1=ones(15,1);
b2=ones(15,1);
f=ones(1,64); % 不重要,随便设置
intcon=1:64; % 所有元素都要求为整数
lb=zeros(64,1); % 下限为0
ub=ones(64,1); % 上限为1
A=[A1;A2];
b=[b1;b2];
Aeq=[Aeq1;Aeq2;Aeq3];
beq=[beq1;beq2;beq3];
% 求解整数规划
X=intlinprog(f,intcon,A,b,Aeq,beq,lb,ub);
% 重新 构造数独矩阵
X=round(reshape(X,[8,8]))
请输入第一个皇后所在行:2
请输入第一个皇后所在列:3
X =
0 0 0 0 1 0 0 0
0 0 1 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0