皇后问题

网友投稿 541 2022-05-28

八皇后问题是一个以国际象棋为背景的问题:如何能够在 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");

}

}

数据结构

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:Bash脚本教程之启动环境
下一篇:我用370行代码写了一个wxPython的任务托盘程序:实用的屏幕录像机
相关文章