问题描述

这道题是 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$ 个皇后的位置。

可以再使用三个一维数组,分别记录:

  1. 某一列是否放置了皇后
  2. 某一个正对角线是否放置了皇后。位于同一个正对角线的位置,其行列下标的差值 row-col 是相同的。由于差值可能是负数,所以我们令数组大小为 $2n$,令 row-col+n 为某个正对角线的下标
  3. 某一个反对角线是否放置了皇后。位于同一个反对角线的位置,其行列下标的和 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
		}
	}
}

使用迭代实现回溯

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

迭代步骤:

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

代码如下:

另一种写法
// 迭代法
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
}

结语

本文发表在我的博客 https://imageslr.com/。我也会分享更多的题解,一起交流,共同进步!