BM59 题解 | #N皇后问题#

心路历程：

N皇后问题，一直是我心中大患，一直想逃避，一遇到n皇后的问题，就像逃避，头脑痛焦虑，不知道怎么办，这次总算是，拿下了，真棒，Good job！well done！

主要是有两个突破点：

1、不再依赖官网的简单版本算法，而是学习leetcode，真正的把N皇后的所有路径都记录下来了

2、理解了怎么扫描的原理，就是【当前列】+【左上角】+【右上角】，三个方向扫描就可以了。

3、最让我印象深刻的是，记录路径的函数，竟然可以减少成一个，不用attack了，而是只要一个queens二维数组就可以了。

解题思路：

1、定义二维char数组path，记录符合条件的方案。

2、使用递归dfs扫描符合条件的方案，

1）结束的判断是n==row，所有的行放置完Q了

2）递归回溯，是一行行递归，一列列扫描的。

3、判断方法，放置数组的方法，主要是从三个方向判断，如上图。

参考视频：算法与数据结构，回溯法求解八皇后，最经典的递归问题

import java.util.*;


public class Solution {
    List<List<String>> res = new ArrayList<>();

    public int Nqueen (int n) {
        char[][] path = new char[n][n]; //记录可行的方案路径.表示空格，Q表示放了皇后
        for(char[] chars: path) {
            Arrays.fill(chars, '.');
        }
        dfs(n, path,  0);
        return res.size();
    }

    // 递归回溯
    private void dfs(int n, char[][] path,int row) {
        if(n == row) {
            res.add(toArray(path));
            return;
        }

        for(int i=0; i<n; i++) {
            if(check(i, row, n, path)) {
                path[row][i] = 'Q';
                dfs(n, path, row+1);
                path[row][i] = '.';
            }
        }
    }

    private boolean check(int col, int row, int n, char[][] path) {
        // 判断当前列是否有Q
        for(int i=0; i<row; i++) {
            if(path[i][col] == 'Q'){
                return false;
            }
        }

        // 判断做左上角是否有Q
        for(int i=row-1, j=col-1; i>=0 && j>=0; i--,j--) {
            if(path[i][j] == 'Q') {
                return false;
            }
        }

        // 判断做右上角是否有Q， 很简单的，就是坐标递减，就跟之前的grid小岛算法，矩形最长路径一样的
        for(int i=row-1, j=col+1; i>=0 && j<n; i--,j++) {
            if(path[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }

    // 转array
    private List<String> toArray(char[][] path) {
        List<String> list = new ArrayList<>();
        for(char[] chars: path) {
            list.add(new String(chars));
        }
        return list;
    }
}