n皇后问题 |
您所在的位置：网站首页 › 用回溯法求解哈密顿回路问题例题及答案 › n皇后问题 |
n皇后问题
|
大家好，又见面了，我是你们的朋友全栈君。 n皇后问题-回溯法求解1.算法描述在n×n格的国际象棋上摆放n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。  img1n皇后是由八皇后问题演变而来的。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。 2.算法分析随着计算机的普及和发展，以前人们无法解决的问题，计算机可以简单计算出来。而且思路十分清晰，那就是暴力求解，遍历所有情况，然后计算出解的个数。 2.1 回溯法按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法 2.2 回溯法思路用数组模拟棋盘，从第一行开始，依次选择位置， 如果当前位置满足条件，则向下选位置， 如果不满足条件，那么当前位置后移一位。  img2 img3最后一个不满足，回溯到上一行， 选下个位置，继续试探。 其实并不需要一个n*n的数组，我们只需要一个n长度的数组来存位置。 表示方式： arr[i] = k; 表示： 第i行的第k个位置放一个皇后。这样一个arr[n]的数组就可以表示一个可行解， 由于回溯，我们就可以求所有解。 2.3 n皇后回溯求解因为八皇后不能在同行，同列， 同斜线。 每一行放一个皇后，就解决了不在同行的问题。在第i行的时候，遍历n列，试探位置。和之前所有行放的位置进行比较。比较列：当前列col 不等于 之前 所有列。 即col != arr[i].比较斜线， 因为不再同一斜率为1或者-1的斜线。(row – i) / (col – arr[i]) != 1 或 -1 可以取巧用绝对值函数: abs(row-i) != abs(col-arr[i])我们可以提取比较方法： public boolean comp(int row, int col){ //当前行和列 for (int i = 0; i < row; i++) //比较之前row -1 列。 { if(col == arr[i] || abs(row-i) != abs(col-arr[i])) //如果在同一列，同一斜线 return false; } return true; }比较函数写完后， 就只剩下回溯过程， 我们采用递归的方式回溯，比较好理解。 //当前层 row for (int i = 0; i < n; i++){ if(comp(row, i)){ arr[row] = i; //同样方式遍历下一层。 row + 1 } }2.4 时间复杂度最坏的情况： 每一行有n种情况，有n行， 所以时间复杂度为O(n^n)。 但是由于回溯法会提前判断并抛弃一些情况，使得时间复杂度并没有想象中那么高。但是说是O(n!)也不太对，具体怎么算，暂时也不太清楚。（之前想当然了，此处有修正，多谢评论中的提醒。） 2.5 空间复杂度因为只用了arr[n]的数组，也就是O(n). 3.代码实现public class NQueen { private int n; private long count; private int[] arr; // private int nn; public NQueen(int n){ this.n = n; // nn = (1 |
【本文地址】
今日新闻 |
推荐新闻 |