写点什么

N 皇后问题

用户头像
孙苏勇
关注
发布于: 2020 年 05 月 30 日
N皇后问题

现在大厂在招聘时对算法的要求越来越高,而且面试时不光要听思路,还要能手写出完整的实现,而有一些题目并不容易,纯靠背题显然是不现实的,最近就听一朋友讲要求手写 8 皇后,那这一篇就扩展一下,写写有关 N 皇后问题的一个容易理解的思路及算法实现。


我们定义要求如下,给定一个n*n方格的棋盘,每一行放一个皇后,要求满足任一皇后所在的列及斜边上都不能有其他皇后存在,然后将所有解法打印出来,要求打印出n*n的字符矩阵,皇后的位置用“Q”表示,空格用“.”表示。拿 4 皇后来说,其中一个解如下图,需要满足的要求是行、列、斜边上都不能有其他皇后存在。


图:4 皇后举例


理解了题目要求后,现在分析题目的解法。要求给出所有可能的解,需要从第一行开始,逐行、逐列求解满足要求的行与列的序号,记录下符合的解,最后按格式输出。而每一次的判断都需要依赖之前合法的皇后放置结果,第i+1行所有列执行判断后,需要回到第i行,继续第i行下一列的判断,一个完整的解为当已经判断到最后一行,而此时最后一行的第 j 列符合要求,则此时的记录中为一个合法的解。直到所有行所有列的情况都判断完成,求解结束。所以这个问题适合用深度优先遍历的方式来解,从首行首列开始,优先向深度方向即向下一行搜索,下一行则遍历各列,找到第一个符合要求的列后即再向下一行也就是深度方向搜索……

用伪代码表示过程大致如下:

dfs (row) {  if (row == n) {    printOneSolver()    return;  }    for (col in n) {    if (valid(row, col) {      addToValidConditions(row, col)      dfs(row + 1)      removeFromValidConditions(row, col)    }  }}//说明:这里的row和col表明是与行列有关,真正的参数由行列引申而来。
复制代码


上述伪码描述了大致的过程,便于整体上理解思路,接下来介绍如何判断合法性。先说行的判断,因为每行只能放置一个皇后,又是以行为深度向下遍历,所以一个合法的解其实只需要有 n 个列值信息就可以表示,比如其中一个合法解的列值为[1, 3, 0, 2](0 表示第一列),这个解表示皇后放在第 1 行第 2 列,第 2 行第 4 列,第 3 行第 1 列,第 4 行第 3 列,因此行信息是不需要单独列出的。这个时候得出一个关键数据,就是用一个有序的数据结构来表示列,序号即为所在行,而该序号下的值为所在列,这个结构我们称为cols


行不需要单独判断,而列有了如上数据结构表示,那就剩下斜边的判断了,画个图来说明一下斜边的判断如何做。

图:用坐标系分析斜边计算方式


以左上角为坐标原点,向下表示行,向右表示列,从图上可以看到两个斜边其实是斜率为 1 和-1 的两条直线,而在不同的皇后位置的斜边表示都是x+y=ax-y=b的形式,ab其实也就是截距,xy就是行、列值,因此我们可以借助两个数据结构分别表示目前已经被占用的斜边,x+y的形式我们称为xySum,而x-y的形式,我们就称为xyDiff


到目前我们得出合法的判断条件就是当前列不在cols中且行列之和不在xySum中且行列之差不在xyDiff中。这里需要注意一点,当合法时要将条件放入这几个结构,进行 dfs,而 dfs 结束后,要还原为之前的状态,以便进行下一列的判断,这在伪代码中也有说明。


最后说下结果的打印,按要求的方式打印时我们仍以其中一个解为例来说明,[1, 3, 0, 2],对于该解其打印结果应为:

.Q.....QQ.....Q.
复制代码


这里给出列序号如何拼接该行的输出,如当前列值为 1,则表示皇后在第 2 列(列号从 0 开始),那么在皇后之前就有 1 个“.”,然后是“Q”,再然后是 n-列序号-1 个“.”,用公式表示如下,col代表列序号:


".".repeat(col) + "Q" + ".".repeat(n - col - 1)
复制代码


为了输出后对于我们观察更直观,我们在字符后多加个空格,会更方便观察,所以改为如下公式:

". ".repeat(col) + "Q " + ". ".repeat(n - col - 1)//输出相应如下. Q . .. . . QQ . . .. . Q .
复制代码


最后给出完整实现:

public void solveNQueens(int n) {    dfs(n, new ArrayList<>(), new HashSet<>(), new HashSet<>());}
/** * @param n 棋盘大小,也是皇后的数量 * @param cols 存放当前合法的列序号,其size的大小表示当前已经遍历的行数 * 而其值正好是要进行遍历的下一行 * @param xySum 行列之和,用Set存放 * @param xyDiff 行列之差,用Set存放 */private void dfs(int n, List<Integer> cols, Set<Integer> xySum, Set<Integer> xyDiff) { //当cols.size为n时,表明每一行都可以合法放置一个皇后,得到一个合法解 if (cols.size() >= n) { printOneSolver(cols); return; } int row = cols.size(); for (int col = 0; col < n; col++) { if (!cols.contains(col) && !xySum.contains(row + col) && !xyDiff.contains(row - col)) { cols.add(col); xySum.add(row + col); xyDiff.add(row - col); dfs(n, cols, xySum, xyDiff); cols.remove(Integer.valueOf(col)); xySum.remove(Integer.valueOf(row + col)); xyDiff.remove(Integer.valueOf(row - col)); } }}
private void printOneSolver(List<Integer> cols) { for (int i = 0; i < cols.size(); i++) { System.out.println(". ".repeat(cols.get(i)) + "Q " + ". ".repeat(cols.size() - cols.get(i) - 1)); } System.out.println();}
复制代码


以 4 皇后为例,输出如下:

. Q . . . . . Q Q . . . . . Q . 
. . Q . Q . . . . . . Q . Q . .
复制代码


思路是这样,如果更换数据结构和判断的具体写法,效率上可能会高一点。之前也有看过说 N 皇后问题用位运算解决会更高效,位运算的解法完成之后将作为相关主题补充在文章末尾。


相关主题:

N皇后问题之位运算解法

两边夹的应用三

两边夹的应用二

两边夹的应用



发布于: 2020 年 05 月 30 日阅读数: 833
用户头像

孙苏勇

关注

不读书,思想就会停止。 2018.04.05 加入

公众号“像什么",记录想记录的。

评论 (6 条评论)

发布
用户头像
这个思路是我见过最容易理解的
2020 年 06 月 13 日 22:08
回复
不敢当。解法思路是常见的,只是加入一点自己解时的理解方式。
2020 年 06 月 13 日 23:08
回复
用户头像
思路很清晰,讲解的很明白,受益!另想问下文中的图是用什么画的呢?
2020 年 06 月 02 日 15:30
回复
draw.io
2020 年 06 月 02 日 15:36
回复
用户头像
感谢分享教程,期待更多好内容,这篇首页推荐一下。
2020 年 05 月 31 日 10:52
回复
谢谢
2020 年 05 月 31 日 13:21
回复
没有更多了
N皇后问题