问题描述

面试题 08.12. 八皇后

设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。

注意：本题相对原题做了扩展

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 输入：4
 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 解释：4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

解题思路

这是一个典型的回溯问题，我们可以通过回溯法来解决。回溯法是一种通过不断试错来寻找问题解的算法。在回溯法中，逐步构造问题的解，通过尝试不同的部分解来寻找问题的解。当发现当前部分解不能得到问题的解时，我们就放弃当前部分解，回溯到上一个部分解，尝试其他的部分解。

在这个问题中，可以通过递归的方式来实现回溯法。具体来说就是从第一行开始，逐行放置皇后，每放置一个皇后，就检查当前的棋盘是否满足条件，如果满足条件，就继续放置下一个皇后，如果不满足条件，就回溯到上一个部分解，尝试其他的部分解。

代码实现

具体实现中，通过一个数组来记录每一行皇后的位置，数组的下标表示行号，数组的值表示列号。编写递归函数 placeQueens，默认从 0 行开始放置皇后，首先编写递归的退出条件是当前行号等于 n，表示所有的皇后都已经放置完毕，此时将当前的棋盘加入到结果集中。

在递归函数中，每次换到下一行时，都会遍历当前行的所有列，检查当前列是否满足条件，如果满足条件，就将当前列的位置放入到数组中，然后递归放置下一个皇后。

最后在递归函数中，需要编写一个函数 isValid 来检查当前棋盘是否满足条件。具体来说，我们需要检查当前皇后的位置是否和之前的皇后位置在同一列、同一对角线上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
var solutions [][]string
var positions []int

func solveNQueens(n int) [][]string {
	solutions = make([][]string, 0)
	positions = make([]int, n)
	placeQueens(0, n)
	return solutions
}

func placeQueens(row, n int) {
	if row == n {
		addSolution(n)
		return
	}

	for col := 0; col < n; col++ {
		if isValid(col, row) {
			positions[row] = col
			placeQueens(row+1, n)
		}
	}
}

func addSolution(n int) {
	board := make([]string, n)
	for i := 0; i < n; i++ {
		row := make([]byte, n)
		for j := 0; j < n; j++ {
			if j == positions[i] {
				row[j] = 'Q'
			} else {
				row[j] = '.'
			}
		}
		board[i] = string(row)
	}
	solutions = append(solutions, board)
}

func isValid(col, row int) bool {
    left_up := col - 1
	right_up := col + 1
	for i := row - 1; i >= 0; i-- {
		if positions[i] == col {
			return false
		}

		if left_up >= 0 && positions[i] == left_up {
			return false
		}

		if right_up < n && positions[i] == right_up {
			return false
		}

		left_up--
		right_up++
	}

	return true
}

这里指的注意的地方在于 isValid 函数，这个函数用来检查当前皇后的位置是否和之前的皇后位置在同一列、同一对角线上。一开始想的方案时从当前准备放置的位置开始，往上逐行检查是否和之前的皇后位置在同一列、同一对角线上，后面看了解析发现可以通过数学方法来判断是否在同一对角线上，这样的时间复杂度是 O(n)。这里的数学方法是通过判断两个皇后的坐标之差是否相等来判断是否在同一主对角线上，通过判断两个皇后的坐标之和是否相等来判断是否在同一副对角线上。

所以可以修改 isValid 函数如下：

1
2
3
4
5
6
7
8
func isValid(col, row int) bool {
	for i := 0; i < row; i++ {
		if positions[i] == col || positions[i]-i == col-row || positions[i]+i == col+row {
			return false
		}
	}
	return true
}