如何用数学方法解决八皇后问题?

该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。计算机发明后,有多种计算机语言可以解决此问题。
关注者
232
被浏览
46,846

没有


真的没有公式吗?

Emmmm,这个么.......

要说公式,真要找的话有是有..但是并非所有公式都有实用价值...

n\times n 的棋盘上放 k 个皇后有如下递推公式:

inversef[j_]:=(m=2;While[j>Fibonacci[m],m=m+1];m);
denom[k_]:=(x-1)^(2k+1)*Product[Cyclotomic[j,x]^(2*(k-inversef[j]+1)),{j,2,Fibonacci[k]}];
dt[k_]:=Sum[Coefficient[Expand[denom[k]],x,i]*Subscript[a,n-i],{i,0,Exponent[denom[k],x]}]

比如 k=1

a_n=a_{n-3}-3 a_{n-2}+3 a_{n-1}

代入初值条件解得:

q_1(n)=n^2

然后 k=2 时, a_n=a_{n-5}-5 a_{n-4}+10 a_{n-3}-10 a_{n-2}+5 a_{n-1}

解得 q_2(n)=\frac{n^4}{2}-\frac{5 n^3}{3}+\frac{3 n^2}{2}-\frac{n}{3}

一切看起来很美好啊....


然而方程的阶数是指数增长的

很不幸我们到现在只解到 k=6

而且压根不是通过这个方法解递推方程得到的.

这个递推方程高达81阶

通项公式复杂无比, 肯定用了计算机辅助,虽然论文里没写代码...

k=8 递推公式是:

嗯...477阶递推...

这就是你知道存在O(1)级公式算法但是你找不出来的绝佳典范

话说多柱汉诺塔也这样, 存在公式但你找不出来

哈哈哈哈


Update:

这个递推的项数居然有公式能算...

q^e(k)=\sum _{j=1}^{k-1} \left(\sum _{i=F_{k-j}+1}^{F_{-j+k+1}} 2 j \phi (i)\right)+2 k+1\sim \frac{3 \left(\sqrt{5}+1\right)}{5 \pi ^2}(1+\phi)^k

A178717 - OEIS

9皇后就有上千阶了

我们可以分析一下特征根.

从主特征看出 k 个皇后最后解的个数就是 O(n^{2k})

然后方程特征根的分布也很有趣