N皇后问题1 困难🌟🌟
问题描述
原文链接：51. N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的n 皇后问题的解决方案。
每一种解法包含一个不同的n皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]
提示：
1 <= n <= 9
代码实现
Java
class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] map = new char[n][n];
for(int i = 0;i < n; i++){
for(int j = 0; j < n; j++){
map[i][j] = '.';
}
}
backTrack(map, 0, n);
return res;
}
void backTrack(char[][] map, int row, int n){
// 结束条件
if(row == n){
res.add(help(map, n));
return;
}
// 递归+回溯
for(int col = 0; col < n; col++){
// 判断能否存放皇后
if(isValid(map, row, col, n)){
map[row][col] = 'Q';
backTrack(map, row+1, n);
map[row][col] = '.';
}
}
}
boolean isValid(char[][] map, int row, int col, int n){
// 判断列
for(int i = 0; i < row; i++){
if(map[i][col] == 'Q'){
return false;
}
}
// 判断右斜
for(int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--){
if(map[i][j] == 'Q'){
return false;
}
}
// 判断左斜
for(int i = row - 1, j = col + 1; i >=0 && j < n; i--, j++){
if(map[i][j] == 'Q'){
return false;
}
}
return true;
}
// 把二位字符数组转为List<String>
List<String> help(char[][] map, int n){
List<String> temp = new ArrayList<>();
for(int i = 0; i < n; i++){
StringBuilder build = new StringBuilder();
for(int j = 0; j < n; j++){
build.append(map[i][j]);
}
temp.add(build.toString());
}
return temp;
}
}
Python
class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
res = []
map = [['.' for _ in range(n)] for _ in range(n)]
self.backTrack(map, 0, n, res)
return res
def backTrack(self, map, row, n, res):
# 结束条件
if row == n:
res.append(self.help(map, n))
return
# 递归+回溯
for col in range(n):
# 判断能否存放皇后
if self.isValid(map, row, col, n):
map[row][col] = 'Q'
self.backTrack(map, row + 1, n, res)
map[row][col] = '.'
def isValid(self, map, row, col, n):
# 判断列
for i in range(row):
if map[i][col] == 'Q':
return False
# 判断右斜
for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
if map[i][j] == 'Q':
return False
# 判断左斜
for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
if map[i][j] == 'Q':
return False
return True
def help(self, map, n):
temp = []
for i in range(n):
build = ''.join(map[i])
temp.append(build)
return temp
C++
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
vector<vector<string>> res;
vector<vector<char>> map(n, vector<char>(n, '.'));
backTrack(map, 0, n, res);
return res;
}
void backTrack(vector<vector<char>>& map, int row, int n, vector<vector<string>>& res) {
// 结束条件
if (row == n) {
res.push_back(help(map, n));
return;
}
// 递归+回溯
for (int col = 0; col < n; col++) {
// 判断能否存放皇后
if (isValid(map, row, col, n)) {
map[row][col] = 'Q';
backTrack(map, row + 1, n, res);
map[row][col] = '.';
}
}
}
bool isValid(vector<vector<char>>& map, int row, int col, int n) {
// 判断列
for (int i = 0; i < row; i++) {
if (map[i][col] == 'Q') {
return false;
}
}
// 判断右斜
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (map[i][j] == 'Q') {
return false;
}
}
// 判断左斜
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (map[i][j] == 'Q') {
return false;
}
}
return true;
}
vector<string> help(vector<vector<char>>& map, int n) {
vector<string> temp;
for (int i = 0; i < n; i++) {
string build;
for (int j = 0; j < n; j++) {
build += map[i][j];
}
temp.push_back(build);
}
return temp;
}
};
Go
func solveNQueens(n int) [][]string {
res := [][]string{}
m := make([][]byte, n)
for i := 0; i < n; i++ {
m[i] = make([]byte, n)
for j := 0; j < n; j++ {
m[i][j] = '.'
}
}
backTrack(m, 0, n, &res)
return res
}
func backTrack(m [][]byte, row, n int, res *[][]string) {
// 结束条件
if row == n {
*res = append(*res, help(m, n))
return
}
// 递归+回溯
for col := 0; col < n; col++ {
// 判断能否存放皇后
if isValid(m, row, col, n) {
m[row][col] = 'Q'
backTrack(m, row+1, n, res)
m[row][col] = '.'
}
}
}
func isValid(m [][]byte, row, col, n int) bool {
// 判断列
for i := 0; i < row; i++ {
if m[i][col] == 'Q' {
return false
}
}
// 判断右斜
for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
if m[i][j] == 'Q' {
return false
}
}
// 判断左斜
for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
if m[i][j] == 'Q' {
return false
}
}
return true
}
func help(m [][]byte, n int) []string {
temp := []string{}
for i := 0; i < n; i++ {
temp = append(temp, string(m[i]))
}
return temp
}