[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){
        //up
        for(int i=0;i<row;i++){
            if(map[i][col]=='Q'){
                return false;
            }
        }
        //left
        for(int i=0;i<col;i++){
            if(map[row][i]=='Q'){
                return false;
            }
        }
        //primary diagonal line
        for(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--){
            if(map[i][j]=='Q'){
                return false;
            }
        }
        //vice diagonal line
        for(int i=row-1,j=col+1;i>=0 && j<n;i--,j++){
            if(map[i][j]=='Q'){
                return false;
            }
        }
        return true;
    }
}