51. N皇后

绝地灬酷狼 2021-11-02 00:08 327阅读 0赞

# 51. N皇后 #

## 题目描述 ##

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

![8-queens.png][]

上图为 8 皇后问题的一种解法。

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

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

示例:

输入: 4  
输出: \[  
\[".Q..", // 解法 1  
"...Q",  
"Q...",  
"..Q."\],

\["..Q.", // 解法 2  
"Q...",  
"...Q",  
".Q.."\]  
\]  
解释: 4 皇后问题存在两个不同的解法。

## 贴出代码 ##

class Solution { private List<List<String>> solutions; private char[][] nQueens; private boolean[] colUsed; private boolean[] diagonals45Used; private boolean[] diagonals135Used; private int n; public List<List<String>> solveNQueens(int n) { solutions = new ArrayList<>(); nQueens = new char[n][n]; for (int i = 0; i < n; i ++){ Arrays.fill(nQueens[i],'.'); } colUsed = new boolean[n]; diagonals45Used = new boolean[2 * n - 1]; diagonals135Used = new boolean[2 * n - 1]; this.n = n; dfs(0); return solutions; } private void dfs(int row){ if (row == n){ List<String> list = new ArrayList<>(); for (char[] chars : nQueens){ list.add(new String(chars)); } solutions.add(list); return; } for (int col = 0; col < n; col++){ int diagonals45Idx = row + col; int diagonals135Idx = n - 1 - (row -col); if (colUsed[col] || diagonals45Used[diagonals45Idx] || diagonals135Used[diagonals135Idx]){ continue; } nQueens[row][col] = 'Q'; colUsed[col] = diagonals45Used[diagonals45Idx] = diagonals135Used[diagonals135Idx] = true; dfs(row + 1); colUsed[col] = diagonals45Used[diagonals45Idx] = diagonals135Used[diagonals135Idx] = false; nQueens[row][col] = '.'; } } }

转载于:https://www.cnblogs.com/Tu9oh0st/p/11044094.html

[8-queens.png]: /images/20211101/92c27ad2d7f94987a599639b325e47f3.png

发表评论取消回复

表情：

评论列表（有 0 条评论，327人围观）

还没有评论，来说两句吧...

相关阅读

相关 51. N 皇后

51. N 皇后按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇

以你之姓@/ 2024年03月30日 13:55/ 0 赞/ 49 阅读

相关 51. N皇后

51. N皇后题干描述解题思路回溯三部曲 1. 递归函数参数 2. 递归终止条件

女爷i/ 2023年10月16日 14:44/ 0 赞/ 34 阅读

相关 leetcode 51 N皇后

前言题目：[51. N 皇后][51. N] 参考题解：[N皇后-代码随想录][N_-] -------------------- 提交代码题目要求：任何

我就是我/ 2022年09月14日 09:27/ 0 赞/ 166 阅读

相关 LeetCode 51. N皇后

题目重述 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给你一个整数 n ，返回所有不同的 n 皇后问题的解决方

╰+攻爆jí腚メ/ 2022年09月03日 00:18/ 0 赞/ 193 阅读

相关 LeetCode51 N皇后

LeetCod 51 N皇后 -------------------- 首先，先看一下题目： n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，

拼搏现实的明天。/ 2022年05月12日 05:16/ 0 赞/ 198 阅读

相关 51. N皇后 I

题目描述 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。给定一个整数 n，返回所有不同的 n 皇后问题

雨点打透心脏的1/2处/ 2022年04月23日 08:26/ 0 赞/ 171 阅读

相关 leetcode:51. N皇后

题目: n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。上图为 8 皇后问题的一种解法。给定一个整数 n，返回所有

绝地灬酷狼/ 2022年04月06日 15:50/ 0 赞/ 211 阅读

相关 Leetcode51N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。思路：刚开始的思路是，用一个二维int数组来保存，后来发现很繁琐，其次就

偏执的太偏执、/ 2021年12月19日 01:37/ 0 赞/ 227 阅读

相关 Q51 N皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 ![img][] 上图为 8 皇后问题的一种解法。给定一个整数 n，返

拼搏现实的明天。/ 2021年12月15日 05:51/ 0 赞/ 241 阅读

相关 51. N皇后

51. N皇后题目描述 n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 ![8-queens.png][]

绝地灬酷狼/ 2021年11月02日 00:08/ 0 赞/ 328 阅读