做网站无需备案,甘肃省水利工程建设网站,代做网站地图,cms网站后台管理系统八皇后问题是一个以国际象棋为背景的问题#xff1a;如何能够在 88 的国际象棋棋盘上放置八个皇后#xff0c;使得任何一个皇后都无法直接吃掉其他的皇后#xff1f;为了达到此目的#xff0c;任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的…八皇后问题是一个以国际象棋为背景的问题如何能够在 8×8 的国际象棋棋盘上放置八个皇后使得任何一个皇后都无法直接吃掉其他的皇后为了达到此目的任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题这时棋盘的大小变为n1×n1而皇后个数也变成n2。而且仅当 n2 ≥ 1 或 n1 ≥ 4 时问题有解。
皇后问题是非常著名的问题作为一个棋盘类问题毫无疑问用暴力搜索的方法来做是一定可以得到正确答案的但在有限的运行时间内我们很难写出速度可以忍受的搜索部分棋盘问题的最优解不是搜索而是动态规划某些棋盘问题也很适合作为状态压缩思想的解释例题。
进一步说皇后问题可以用人工智能相关算法和遗传算法求解可以用多线程技术缩短运行时间。本文不做讨论。
本文不展开讲状态压缩以后再说 一般思路 N*N的二维数组在每一个位置进行尝试在当前位置上判断是否满足放置皇后的条件这一点的行、列、对角线上没有皇后。 优化1 既然知道多个皇后不能在同一行我们何必要在同一行的不同位置放多个来尝试呢
我们生成一维数组recordrecord[i]表示第i行的皇后放在了第几列。对于每一行确定当前record值即可因为每行只能且必须放一个皇后放了一个就无需继续尝试。那么对于当前的record[i]查看record[0...i-1]的值是否有j record[k]同列、|record[k] - j| | k-i |同一斜线的情况。由于我们的策略无需检查行每行只放一个。
public class NQueens {public static int num1(int n) {if (n 1) {return 0;}int[] record new int[n];return process1(0, record, n);}public static int process1(int i, int[] record, int n) {if (i n) {return 1;}int res 0;for (int j 0; j n; j) {if (isValid(record, i, j)) {record[i] j;res process1(i 1, record, n);}}//对于当前行依次尝试每列return res;}
//判断当前位置是否可以放置public static boolean isValid(int[] record, int i, int j) {for (int k 0; k i; k) {if (j record[k] || Math.abs(record[k] - j) Math.abs(i - k)) {return false;}}return true;}public static void main(String[] args) {int n 8;System.out.println(num1(n));}
}优化2 分析棋子对后续过程的影响范围本行、本列、左右斜线。 黑色棋子影响区域为红色
本行影响不提根据优化一已经避免
本列影响一直影响D列直到第一行在D放棋子的所有情况结束。 左斜线每向下一行实际上对当前行的影响区域就向左移动
比如
尝试第二行时黑色棋子影响的是我们的第三列
尝试第三行时黑色棋子影响的是我们的第二列
尝试第四行时黑色棋子影响的是我们的第一列
尝试第五行及以后几行黑色棋子对我们并无影响。 右斜线则相反
随着行序号增加影响的列序号也增加直到影响的列序号大于8就不再影响。 我们对于之前棋子影响的区域可以用二进制数字来表示比如:
每一位用01代表是否影响。
比如上图对于第一行就是00010000
尝试第二行时数字变为00100000
第三行01000000
第四行10000000 对于右斜线的数字同理
第一行00010000之后向右移00001000000001000000001000000001直到全0不影响。 同理我们对于多行数据也同样可以记录了
比如在第一行我们放在了第四列 第二行放在了G列这时左斜线记录为00100000第一个棋子的影响00000010当前棋子的影响00100010。
到第三行数字继续左移01000100然后继续加上我们的选择如此反复。 这样我们对于当前位置的判断其实可以通过左斜线变量、右斜线变量、列变量按位或运算求出每一位中三个数有一个是1就不能再放。
具体看代码
注怎么排版就炸了呢。。。贴一张图吧 public class NQueens {public static int num2(int n) {// 因为本方法中位运算的载体是int型变量所以该方法只能算1~32皇后问题// 如果想计算更多的皇后问题需使用包含更多位的变量if (n 1 || n 32) {return 0;}int upperLim n 32 ? -1 : (1 n) - 1;//upperLim的作用为棋盘大小比如8皇后为00000000 00000000 00000000 11111111//32皇后为11111111 11111111 11111111 11111111return process2(upperLim, 0, 0, 0);}public static int process2(int upperLim, int colLim, int leftDiaLim,int rightDiaLim) {if (colLim upperLim) {return 1;}int pos 0; //pos所有的合法位置int mostRightOne 0; //所有合法位置的最右位置//所有记录按位或之后取反并与全1按位与得出所有合法位置pos upperLim (~(colLim | leftDiaLim | rightDiaLim));int res 0;//计数while (pos ! 0) {mostRightOne pos (~pos 1);//取最右的合法位置pos pos - mostRightOne; //去掉本位置并尝试res process2(upperLim, //全局colLim | mostRightOne, //列记录//之前列本位置(leftDiaLim | mostRightOne) 1, //左斜线记录//左斜线变量本位置左移 (rightDiaLim | mostRightOne) 1); //右斜线记录//右斜线变量本位置右移高位补零}return res;}public static void main(String[] args) {int n 8;System.out.println(num2(n));}
}完整测试代码
32皇后结果/时间
暴力搜时间就太长了懒得测。。。 public class NQueens {public static int num1(int n) {if (n 1) {return 0;}int[] record new int[n];return process1(0, record, n);}public static int process1(int i, int[] record, int n) {if (i n) {return 1;}int res 0;for (int j 0; j n; j) {if (isValid(record, i, j)) {record[i] j;res process1(i 1, record, n);}}return res;}public static boolean isValid(int[] record, int i, int j) {for (int k 0; k i; k) {if (j record[k] || Math.abs(record[k] - j) Math.abs(i - k)) {return false;}}return true;}public static int num2(int n) {if (n 1 || n 32) {return 0;}int upperLim n 32 ? -1 : (1 n) - 1;return process2(upperLim, 0, 0, 0);}public static int process2(int upperLim, int colLim, int leftDiaLim,int rightDiaLim) {if (colLim upperLim) {return 1;}int pos 0;int mostRightOne 0;pos upperLim (~(colLim | leftDiaLim | rightDiaLim));int res 0;while (pos ! 0) {mostRightOne pos (~pos 1);pos pos - mostRightOne;res process2(upperLim, colLim | mostRightOne,(leftDiaLim | mostRightOne) 1,(rightDiaLim | mostRightOne) 1);}return res;}public static void main(String[] args) {int n 32;long start System.currentTimeMillis();System.out.println(num2(n));long end System.currentTimeMillis();System.out.println(cost time: (end - start) ms);start System.currentTimeMillis();System.out.println(num1(n));end System.currentTimeMillis();System.out.println(cost time: (end - start) ms);}
}
