【LeetCode】51 N 皇后问题

优质

小牛编辑

122浏览

2023-12-01

问题描述

这道题是 LeetCode 51题。

将 $n$ 个皇后放置在 $n×n$ 的棋盘上，并且使皇后彼此之间不能相互攻击。即同一行、同一列、同一对角线只能有一个皇后。

思路简述

N 皇后问题是回溯法的一个经典案例。回溯法是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。当探索到某一步，发现原先选择并不优或达不到目标时，就退回一步重新选择。

回溯法通常采用递归实现。对本题而言，搜索过程可以简述为：在递归过程中，每次在一个合法位置放置一个皇后，然后进入下一层，放置下一个皇后。以此类推，直到 n 个皇后全部放置，输出一个解。

最低级的解法，不推荐

最直接的思路是使用一个大小为 $n^2$ 的二维数组作为棋盘，每次递归时，遍历棋盘的每个位置，判断能否放置一个皇后（即没有行冲突、列冲突和对角线冲突），如果可以，标记该位置 1，然后递归地放置下一个皇后。这是一种回溯的思路。

时间复杂度：$O(n^4)$。一共需要放置 $n$ 个皇后；放置每个皇后时，遍历棋盘的所有位置需要 $O(n^2)$；判断某个位置是否可以放置皇后，需要判断同一行、同一列、同一对角线是否已经有皇后，又需要 $O(n)$。
空间复杂度：$O(n^2)$，需要一个二维棋盘。

伪码如下：

func dfs(board [][]bool, current int, n int) {
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if board[i][j] 可以放置一个皇后 {
                board[i][j] = 1
                dfs(board, current+1, n) // 进入下一层
                board[i][j] = 0 // 重置（回溯）
            }
        }
    }
}

优雅的解法，推荐

我们可以使用一个长度为 $n$ 的一维数组，记录每一行的皇后所处的列下标。这样行冲突就不存在了，因为每一行只能记录一个皇后的位置。对于列冲突，只需遍历该数组，检查是否有与当前行相同的列下标即可。对角线冲突可以通过“两行之差的绝对值==两列之差的绝对值”来检测。

时间复杂度：$O(n^3)$。一共需要放置 $n$ 个皇后；放置每个皇后时，遍历某一行的每一列与判断某个位置是否可以放置皇后各需要 $O(n)$。
空间复杂度：$O(n)$，需要一个一维数组。

代码：

var res [][]string

func solveNQueens(n int) [][]string {
	res = nil
	pos := make([]int, n+1) // 每行的皇后放在第几列，下标从 1 开始
	dfs(pos, 1, n)
	return res
}

func dfs(pos []int, row, n int) {
	// 放置了 n 个皇后，保存结果
	if row > n {
		res = append(res, genBoard(pos, n))
		return
	}

	// 尝试放在每一列
	for col := 1; col <= n; col++ {
		valid := true
		// 判断其他行的皇后位置是否与当前行的位置冲突
		for i := 1; i <= n; i++ {
			if row == i || pos[i] == 0 { // 是当前行或者该行未放置皇后
				continue
			}
			if col == pos[i] { // 在同一列
				valid = false
				break
			}
			if abs(row-i) == abs(col-pos[i]) { // 在同一对角线
				valid = false
				break
			}
		}
		if valid {
			pos[row] = col
			dfs(pos, row+1, n)
			pos[row] = 0 // 重置当前行（回溯）
		}
	}
}

func genBoard(pos []int, n int) (result []string) {
	for i := 1; i <= n; i++ {
		col := pos[i]
		rowStr := ""
		for j := 1; j <= n; j++ {
			if j == col {
				rowStr += "Q"
			} else {
				rowStr += "."
			}
		}
		result = append(result, rowStr)
	}
	return
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

最优的解法，推荐

在上一种解法中，我们使用一维数组记录每一行的皇后所处的列下标，解决了行冲突的问题，将时间复杂度下降了一个数量级。但是在判断列冲突、对角线冲突的时候，依然需要遍历 $n$ 个皇后的位置。

可以再使用三个一维数组，分别记录：

某一列是否放置了皇后
某一个正对角线是否放置了皇后。位于同一个正对角线的位置，其行列下标的差值 row-col 是相同的。由于差值可能是负数，所以我们令数组大小为 $2n$，令 row-col+n 为某个正对角线的下标
某一个反对角线是否放置了皇后。位于同一个反对角线的位置，其行列下标的和 row+col 是相同的。令数组大小为 $2n$，令 row+col 为某个反对角线的下标

时间复杂度：$O(n^2)$。一共需要放置 $n$ 个皇后；放置每个皇后时，遍历某一行的每一列需要 $O(n)$；判断列冲突、对角线冲突只需要 $O(1)$。
空间复杂度：$O(n)$。

代码：

var res [][]string

func solveNQueens(n int) [][]string {
	res = nil
	// 行列下标均为 1~n
	pos := make([]int, n+1)            // 每行的皇后放在第几列，下标从 1 开始
	cols := make([]bool, n+1)          // 某一列是否放置了皇后
	diags := make([]bool, (n+1)*2)     // 某一个正对角线是否放置了皇后，下标：row-col+n
	backDiags := make([]bool, (n+1)*2) // 某一个反对角线是否放置了皇后，下标：row+col
	dfs(pos, cols, diags, backDiags, 1, n)
	return res
}

func dfs(pos []int, cols, diags, backDiags []bool, row, n int) {
	// 放置了 n 个皇后，保存结果
	if row > n {
		res = append(res, genBoard(pos, n))
		return
	}

	// 尝试放在每一列
	for col := 1; col <= n; col++ {
		if !cols[col] && !diags[row-col+n] && !backDiags[row+col] { // 同一列、同一个正对角线、反对角线都没有皇后
			pos[row] = col
			cols[col], diags[row-col+n], backDiags[row+col] = true, true, true
			dfs(pos, cols, diags, backDiags, row+1, n)
			pos[row] = 0 // 重置当前行（回溯）
			cols[col], diags[row-col+n], backDiags[row+col] = false, false, false
		}
	}
}

使用迭代实现回溯

递归通常效率较低，有时还会带来额外的空间开销。本题可以使用迭代实现回溯过程。

迭代步骤：

从第一行开始，探测该行的每一列是否可以放置皇后
如果可以，在该列放置一个皇后，进入下一行，继续从第一列开始探测
如果当前行是最后一行，则每找到一个可以放置皇后的位置，就将其加入到结果集中，然后继续探测当前行的下一列
如果已经探测完所有的列，就则清除当前行的皇后位置，然后回溯到上一行，把上一行的皇后位置后移一列，继续探测
如果当前行是第一行，说明已经找到了所有的解，程序终止

代码如下：

另一种写法

// 迭代法
func solveNQueens(n int) [][]string {
    res = nil
    pos := make([]int, n+1) // 每一行的皇后放在第几列。行和列都从 1 开始
    row, col := 1, 1
    for row >= 1 { // 不停迭代。当从第 1 行回溯到第 0 行时，row < 1，迭代结束
        // fmt.Println(row, col)
        for col <= n { // 对于当前行，遍历每一列
            if isValid(row, col, pos) { // 如果 col 可以放置皇后
                if row < n { // 如果当前行不是最后一行，则
                    pos[row] = col
                    row = row + 1 // 前进到下一行
                    col = 1 // 从第一列开始
                    break // 跳出
                } else { // 如果当前行是最后一行，保存结果
                    // 不需要前进到下一行
                    pos[row] = col // 为了打印结果，这里需要先赋值
                    res = append(res, genBoard(pos, n))
                    // pos[row] = 0 // 这一行只可能有一个解，所以这一行可以省略
                }
            }
            col++
        }
        if col > n { // 如果对于当前行，已经没有任何列可以放置皇后，则
            pos[row] = 0 // 切记归零
            row = row - 1 // 回溯到上一行
            col = pos[row]+1 // 从上一行的下一列继续开始遍历
        }
    }
    return res
}

var res [][]string

func solveNQueens(n int) [][]string {
	res = nil
	pos := make([]int, n+1) // 每行的皇后放在第几列，下标从 1 开始
	iterate(pos, n)
	return res
}

func iterate(pos []int, n int) {
	row, col := 1, 1
	for {
		// 步骤 1：探测该行的每一列是否可以放置皇后
		for col <= n {
			if valid(pos, row, col, n) {
				pos[row] = col
				row = row + 1 // 步骤 2：进入到下一行
				col = 1       // 步骤 2：重置到第一列
				break
			}
			col++
		}
		// 步骤 4：探测完当前行的所有列，回溯到上一行
		if col > n {
			if row == 1 {
				return // 步骤 6：当前行是第一行，说明无法回溯，已经找到了所有的解，程序终止
			}
			pos[row] = 0                   // 步骤 4：清除当前行的皇后位置
			row, col = row-1, pos[row-1]+1 // 步骤 4：回溯到上一行，从下一列开始探测
		}
		// 步骤 3：当前行是最后一行，保存结果，继续探测当前行的下一列
		if row > n {
			res = append(res, genBoard(pos, n))
			row, col = n, pos[n]+1
			// pos[row] = 0 // 这一行只可能有一个解，所以这一行可以省略
		}
	}
}

func valid(pos []int, row, col, n int) bool {
	valid := true
	// 判断其他行的皇后位置是否与当前行的位置冲突
	for i := 1; i <= n; i++ {
		if row == i || pos[i] == 0 { // 是当前行或者该行未放置皇后
			continue
		}
		if col == pos[i] { // 在同一列
			valid = false
			break
		}
		if abs(row-i) == abs(col-pos[i]) { // 在同一对角线
			valid = false
			break
		}
	}
	return valid
}