如何用数学方法解决八皇后问题? - 知乎
source link: https://www.zhihu.com/question/263696894/answer/273055085
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
如何用数学方法解决八皇后问题?
真的没有公式吗?
Emmmm,这个么.......
要说公式,真要找的话有是有..但是并非所有公式都有实用价值...
n×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 时
an=an−3−3an−2+3an−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
9皇后就有上千阶了
我们可以分析一下特征根.
从主特征看出 k 个皇后最后解的个数就是 O(n^{2k})
然后方程特征根的分布也很有趣
“如何用数学方法解决八皇后问题?”其实八皇后使用代码解决,皇后不能出现在同一条中斜线上,可以使用数学公式-斜率公式的
1、八皇后问题
- 任意两个皇后都不能处于同一行、同一列、同一斜线上,请问有多少种摆法?
■ 解法:回溯+剪枝
☆ 巧妙的地方:
1、类比二叉树,二叉树是以 节点
为单位,比如前序遍历,是一个节点又一个节点的往下遍历;同样,八皇后是以 行
为单位,第几行放第几个皇后。
2、**充分利用了数据结构一维数组,索引表示皇后的行,元素的值表示皇后所在位置
**,即第几行(第几个皇后)在第几个列位置
3、斜线判断是否存在皇后,利用了 数学的斜率公式
,斜率45度=1=(y坐标的差值)/(x坐标的差值)
int[] cols;//表示皇后的位置,索引是行号,元素值是皇后所在的具体位置
int ways;//一共有多少种摆法
void placeQueens(int n) {
if(n < 1) return;
cols = new int[n];
place(0);//从第一个皇后开始摆
System.out.println(n + "皇后一共有 " + ways + "种摆法");
}
/**
* 从第几行开始摆皇后(摆第几个皇后-以行为单位)
*/
private void place(int row) {
if(row == cols.length) {//成功放完所有的皇后
ways++;//找到一种方法
show();//打印所有皇后的情况
return;
}
--------------------------------------------------- 核心代码开始 ---------------------------------------------------
for(int col = 0; col < cols.length; col++) {//遍历所有的列
if(isValid(row, col)) {//该位置可以放皇后
cols[row] = col;//第row行的col列放上一个皇后
place(row + 1);//处理下一个皇后,下一行开始摆皇后
}
}
}
/**
* 判断当前位置是否可以放皇后,第几row第几col是否可以放皇后
*/
private boolean isValid(int row, int col) {
for(int i = 0; i < row; i++) {//遍历在当前位置(新的一行)之前摆放过的皇后
//判断当前位置是否和之前的皇后处于同一列--col相同
if(col == cols[i]) return false;
//判断当前位置是否和之前的皇后处于同一斜线--斜线相同
if(row - i == Math.abs(col - cols[i])) return false;//利用数学45度的斜率公式 (y坐标差)/(x坐标差)=1
}
--------------------------------------------------- 核心代码结束 ---------------------------------------------------
return true;
}
如果本文对你有帮助的话记得给一乐点个赞哦,感谢!
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK