LeetCode100之N皇后(51)--Java

1.问题描述

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

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

难度等级

困难

题目链接

N皇后

2.解题思路

这道题是非常经典的N皇后问题，我们根据题目要求一步一步分析就能解决出来。

首先，我们需要一个n*n的棋盘，并将整个棋盘用 "." 初始化，还需要一个用来存储所有方案的List集合。

        //设置棋盘char[][] chessboard = new char[n][n];//初始化棋盘for(int i = 0;i < n;i++){for(int j = 0;j < n;j++){chessboard[i][j] = '.';}}//存储最终的答案List<List<String>> data = new ArrayList<>();

接着，其实就是一行一行的放，从0行到n-1行，在每一个位置放置皇后之后，检查能否放在这个位置而已，所以我们需要一个检查是否可以放在某个位置的方法。

这个检查的方法也很简单，根据题目给的描述，我们只需要遍历我们要检查的位置的同一行和用一列，还用左右两个斜方向上是否有皇后就好了，如果有皇后那就不能放。检查同一行和同一列没什么好说的，要注意的是检查左右两个斜方向的时候，我们只需要检查斜上方即可，因为我们是一行一行放的，下方的棋盘还没有皇后，只有上方的棋盘有皇后。

    //检查(row,col)位置能否放置皇后public boolean check(char[][] chessboard,int row,int col){//检查同一列和同一行是否有皇后for(int i = 0;i < chessboard.length;i++){//同一列已经有皇后了if(chessboard[i][col] == 'Q'){return false;}//同一行已经有皇后了if(chessboard[row][i] == 'Q'){return false;}}//检查左斜线是否有皇后for(int i = 0; i < chessboard.length;i++){//判断检查位置是否越界if(row - i < 0){break;}//检查左斜线,斜上方if(col + i < chessboard.length && chessboard[row - i][col + i] == 'Q'){return false;}//检查右斜线，斜上方if(col - i >= 0 && chessboard[row - i][col -i] == 'Q'){return false;}}return true;}

有了检查位置是否可以摆放皇后的方法之后，我们就可以用一个递归方法来获取所有可能的方案了。

首先，我们要来确定递归方法需要用到的参数，棋盘肯定是必不可少的，然后是我们当前方法要摆放第几行的皇后，还需要一个存储可行方案的List集合。

    public void backtrack(char[][] chessboard,int index,List<List<String>> data)

接着，我们就可以来确地递归的结束条件，如果index = n，说明我们已经摆完了N个皇后，当前棋盘上的方案是可行的，所以我们用一个循环将棋盘的每一行取出来存入一个方案List中，再将方案List存到存储所有可能方案的List中就可以返回了。

        //递归结束条件:如果index等于n，皇后已经全部放完if(index == chessboard.length){//添加当前方案List<String> path = new ArrayList<>();for(char[] chars:chessboard){path.add(String.valueOf(chars));}data.add(path);return;}

然后，我们就可以来确定单层的递归逻辑了。其实上面我们已经提到了，就是尝试第index行的每一个位置，检查是否可以摆放皇后。用一个for循环遍历当前行，调用我们上面已经写好的检查方法检查当前位置是否可以摆放皇后，如果可以的话，我们就把皇后摆上去，然后递归调用方法，获取在当前基础上的所有摆放方案，获取完成之后，要记得将当前位置的皇后移去，避免影响尝试其他位置的时候，检查出错。

        //遍历当前要放皇后的行(index),检查每一个位置是否能摆放皇后for(int i = 0; i < chessboard[0].length;i++){//可以摆放皇后if(check(chessboard,index,i)){//放入皇后chessboard[index][i] = 'Q';//递归获取以当前方案为基础的所有子方案backtrack(chessboard,index+1,data);//取出皇后，尝试摆放在其他位置的方案chessboard[index][i] = '.';}}

最后，在主方法中调用这个我们写好的递归函数并将结果返回就可以了。

3.代码展示

class Solution {public List<List<String>> solveNQueens(int n) {//设置棋盘char[][] chessboard = new char[n][n];//初始化棋盘for(int i = 0;i < n;i++){for(int j = 0;j < n;j++){chessboard[i][j] = '.';}}//存储最终的答案List<List<String>> data = new ArrayList<>();//递归获取所有可能backtrack(chessboard,0,data);//返回结果return data;}//递归获取所有的放置方案public void backtrack(char[][] chessboard,int index,List<List<String>> data){//递归结束条件:如果index等于n，皇后已经全部放完if(index == chessboard.length){//添加当前方案List<String> path = new ArrayList<>();for(char[] chars:chessboard){path.add(String.valueOf(chars));}data.add(path);return;}//遍历当前要放皇后的行(index),检查每一个位置是否能摆放皇后for(int i = 0; i < chessboard[0].length;i++){//可以摆放皇后if(check(chessboard,index,i)){//放入皇后chessboard[index][i] = 'Q';//递归获取以当前方案为基础的所有子方案backtrack(chessboard,index+1,data);//取出皇后，尝试摆放在其他位置的方案chessboard[index][i] = '.';}}}//检查(row,col)位置能否放置皇后public boolean check(char[][] chessboard,int row,int col){//检查同一列和同一行是否有皇后for(int i = 0;i < chessboard.length;i++){//同一列已经有皇后了if(chessboard[i][col] == 'Q'){return false;}//同一行已经有皇后了if(chessboard[row][i] == 'Q'){return false;}}//检查左斜线是否有皇后for(int i = 0; i < chessboard.length;i++){//判断检查位置是否越界if(row - i < 0){break;}//检查左斜线,斜上方if(col + i < chessboard.length && chessboard[row - i][col + i] == 'Q'){return false;}//检查右斜线，斜上方if(col - i >= 0 && chessboard[row - i][col -i] == 'Q'){return false;}}return true;}
}