在国际象棋的棋盘上放置8个皇后,使得皇后之间相互没有干绕。
MATLAB的 arrayfun 实现
clear;clc;close all
N=8;
T=N-2;
rows=1:N; % 皇后所在行的位置
cols=perms(rows); % 皇后所在列的位置
S=size(cols,1);
M=zeros(N,N,S); % 存储所以情况的矩阵
linearInd = sub2ind(size(M), repmat(rows',1,S), cols', repmat(1:S,N,1));
M(linearInd) = 1;
dv=arrayfun(@(k)max([arrayfun(@(x)sum(diag(M(:,:,k),x)),-T:T),arrayfun(@(x)sum(diag(rot90(M(:,:,k)),x)),-T:T)]),1:S);
M(:,:,dv>1)=[];
结果如下
N=8
M=8*8*92
说明该问题有92个解
若
N=12
上述算法的空间达到 6.8976e+010 ,超出了MATLAB的空间能力范畴。所以用其他的算法得到的N皇后问题的解如下
皇后数 | 4 | 5 | 6 | 7 | 8
| 9 | 10 | 11 | 12 | 13 | 14 |
独立解 | 1
| 2 | 1 | 6 | 12 | 46 | 92 | 341 | 1787 | 9233 | 45752 |
全部解 | 2 | 10 | 4 | 40 | 92 | 352 | 724 | 2680 | 14200 | 73712 | 365596 |
我们可以对独立解数 和 棋盘的面积 两个参数的对应关系变化进行研究。