可视化图解算法58：N皇后问题

原创

用户11589437

发布于 2025-08-27 10:59:12

2150

文章被收录于专栏：数据结构与算法精讲数据结构与算法精讲

牛客网面试笔试 TOP 101 | LeetCode 52. N 皇后 II

描述

N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后，

要求：任何两个皇后不同行，不同列也不在同一条斜线上，

求给一个整数 n ，返回 n 皇后的摆法数。

数据范围: 1≤n≤9

要求：空间复杂度 O(1) ，时间复杂度 O(n!)

例如当输入4时，对应的返回值为2，

对应的两种四皇后摆位如下图所示：

示例1

输入：

1

返回值：

1

示例2

输入：

8

返回值：

92

2. 解题思路

N皇后的摆放问题可以通过回溯算法完成。结合回溯算法模板，对应的思路如下：

如果文字描述的不太清楚，你可以参考视频的详细讲解：B站@好易学数据结构

3. 编码实现

核心代码如下：

var count int

func totalNQueens(n int) int {
	board := make([][]bool, n)
	for i := 0; i < n; i++ {
		board[i] = make([]bool, n)
	}
	// 调用回溯函数，获取结果
	backtracking(board, 0)
	return count
}

func backtracking(board [][]bool, row int) {
	// 2.递归终止条件：分枝进入结尾，找到一种排列,加入到输出列表
	if row == len(board) {
		//2.1 存放结果（找到一个解）
		count++
		//2.2 返回
		return
	}

	//1.选择：在本层集合中遍历元素
	for col := 0; col < len(board); col++ {
		if isSafe(board, row, col) {
			//1.1 处理节点（放置皇后）
			board[row][col] = true
			// 1.2 递归（继续下一行）
			backtracking(board, row+1)
			//1.3 回溯，撤销选择（移除皇后）
			board[row][col] = false
		}
	}
}

// 皇后安全性检查（皇后们不能：同一行、同一列、左对角线、右对角线）
func isSafe(board [][]bool, row int, col int) bool {
	// 检查 同一行 是否有皇后互相攻击
	for j := 0; j < col; j++ {
		if board[row][j] {
			return false
		}
	}
	// 检查 同一列 是否有皇后互相攻击
	for i := 0; i < row; i++ {
		if board[i][col] {
			return false
		}
	}

	// 检查 左上对角线 是否有皇后互相攻击
	for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
		if board[i][j] {
			return false
		}
	}
	// 检查 右上对角线 是否有皇后互相攻击
	for i, j := row-1, col+1; i >= 0 && j < len(board); i, j = i-1, j+1 {
		if board[i][j] {
			return false
		}
	}
	// 如果上述检查都通过，则当前位置是安全的
	return true
}

具体完整代码你可以参考下面视频的详细讲解。