八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n1×n1，而皇后个数也变成n2。而且仅当 n2 ≥ 1 或 n1 ≥ 4 时问题有解。
皇后问题是非常著名的问题，作为一个棋盘类问题，毫无疑问，用暴力搜索的方法来做是一定可以得到正确答案的，但在有限的运行时间内，我们很难写出速度可以忍受的搜索，部分棋盘问题的最优解不是搜索，而是动态规划，某些棋盘问题也很适合作为状态压缩思想的解释例题。
进一步说，皇后问题可以用人工智能相关算法和遗传算法求解，可以用多线程技术缩短运行时间。本文不做讨论。
（本文不展开讲状态压缩，以后再说）
一般思路：
N*N的二维数组，在每一个位置进行尝试，在当前位置上判断是否满足放置皇后的条件（这一点的行、列、对角线上，没有皇后）。
优化1：
既然知道多个皇后不能在同一行，我们何必要在同一行的不同位置放多个来尝试呢？
我们生成一维数组record，record[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，之后向右移：00001000，00000100，00000010，00000001，直到全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 11111111
-
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;
//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");
-
}
-
}
转载：https://blog.csdn.net/hebtu666/article/details/84631083