51. N-Queens

51. N-Queensopen in new window

🔴 🔖 数组 回溯 🔗 LeetCodeopen in new window

题目

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

Constraints:

1 <= n <= 9

题目大意

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

解题思路

可以采用递归和回溯来解决，通过检查每一行、每一列和每一对角线上是否存在其他皇后，来保证 N 皇后的问题得到解。最后，将符合条件的结果进行格式化，返回最终的答案。

使用一个一维数组 queens 来表示每一行皇后所在的列位置。其中 queens[i] 表示第 i 行的皇后所在的列。
使用回溯法，逐行放置皇后。在每一行，尝试将皇后放在该行的每一列，检查在当前位置 (row, col) 放置皇后是否满足不互相攻击的条件：
- queens[i] === col：检查同一列上是否有其他皇后；
- queens[i] - i === col - row：通过检查横坐标减去纵坐标的差是否相等，检查在左上至右下的对角线上是否有其他皇后；
- queens[i] + i === col + row：通过检查横坐标加上纵坐标的和是否相等，检查在左下至右上的对角线上是否有其他皇后；
- 如果以上三个条件都不满足，说明当前位置是安全的，找到了一个合适的位置。
如果找到一个合适的位置，将该位置的列坐标存入 queens 数组中，并递归调用下一行的放置皇后操作。
如果在某一行无法找到合适的位置，则需要回溯，即回到上一行，尝试在上一行的其他列放置皇后，继续递归搜索。
当成功放置 N 个皇后时，将当前 queens 数组的拷贝加入结果数组中。
最后，将符合条件的结果进行格式化，返回最终的答案。

代码

/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function (n) {
	let res = [];
	let queens = new Array(n).fill(-1);

	const valid = (row, col) => {
		for (let i = 0; i < row; i++) {
			if (
				// 检查同一列上是否有其他皇后
				queens[i] == col ||
				// 检查在左上至右下的对角线上是否有其他皇后
				queens[i] - i == col - row ||
				// 检查在左下至右上的对角线上是否有其他皇后
				queens[i] + i == col + row
			) {
				return false;
			}
		}
		return true;
	};

	const backtrack = (row) => {
		if (row == n) {
			// 找到一个成功解
			res.push([...queens]);
			return;
		}

		for (let col = 0; col < n; col++) {
			if (valid(row, col)) {
				// 在当前位置放置皇后
				queens[row] = col;
				// 继续尝试下一行
				backtrack(row + 1);
				// 回溯，清空当前行状态
				queens[row] = -1;
			}
		}
	};

	backtrack(0);
	return res.map((arr) =>
		arr.map((col) => '.'.repeat(col) + 'Q' + '.'.repeat(n - col - 1))
	);
};

51. N-Queens

# 51. N-Queensopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

51. N-Queensopen in new window

题目

题目大意

解题思路

代码

相关题目