[Leetcode 51][Hard]-n皇后问题-回溯
目录
一、题目描述
二、整体思路
三、代码
一、题目描述
原题地址
二、整体思路
这种可以算是组合问题的变种，在回溯函数中我们要保存当前已放置皇后的所有位置，同时递归调用时要进行寻找下一个皇后的放置位置。那么我们可以逐行遍历棋盘并作为递归调用的条件。然后在回溯函数内，遍历当前行的所有位置，同时判断此位置是否可以放置皇后。递归终止的条件时行数=棋盘行数，将此时的棋盘状态存入结果数组。
难点在于如何判断当前位置是否可以放置皇后，可以从上方、主对角线、副对角线去看有没有已经放置皇后，若有则该位置不可以放置皇后，若无则可。左方不用看的原因是一行只会放一个皇后，每遍历到新的一行时该行一定是未放置皇后的。
三、代码
class Solution {List<List<String>> res=new ArrayList<>();public List<List<String>> solveNQueens(int n) {char[][] chess=new char[n][n];for(int i=0;i<n;i++){for(int j=0;j<n;j++){chess[i][j]='.';}}backtrace(chess,0,n);return res;}void backtrace(char[][] map,int row,int n){if(row==n){res.add(convert(map));return;}for(int i=0;i<n;i++){if(isvalid(map,row,i,n)){map[row][i]='Q';backtrace(map,row+1,n);map[row][i]='.';}}}List<String> convert(char[][] map){//char[][]→List<Stirng>List<String> templist=new ArrayList<>();for(int i=0;i<map.length;i++){StringBuilder tempstr=new StringBuilder();for(int j=0;j<map[i].length;j++){tempstr.append(map[i][j]);}String tempstr2=tempstr.toString();templist.add(tempstr2);}return templist;}boolean isvalid(char[][] map,int row,int col,int n){//upfor(int i=0;i<row;i++){if(map[i][col]=='Q'){return false;}}//leftfor(int i=0;i<col;i++){if(map[row][i]=='Q'){return false;}}//primary diagonal linefor(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--){if(map[i][j]=='Q'){return false;}}//vice diagonal linefor(int i=row-1,j=col+1;i>=0 && j<n;i--,j++){if(map[i][j]=='Q'){return false;}}return true;}
}