Leetcode-51. N 皇后

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

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

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

示例 1：
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：[["Q"]]

解题思路
N皇后问题的摆放原则：同行同列，左上，右上不能有重复
解题思路还是回溯算法的框架
但是我们需要核实是否有效，参照labuladong算法小抄，用二维char数组表示一个可行解，便于后续修改答案和合法性检验，最后可行解有效则转换为List存入结果中

class Solution {

    List<List<String>> res=new LinkedList<>();
    public List<List<String>> solveNQueens(int n) {
        //List<String> board=new ArrayList<>();--改为使用char数组
        char[][] board = new char[n][n];
        for (char[] i : board){
            Arrays.fill(i,'.');
        }
        backtrack(board,0);
        return res;
    }
    //row表示row之前的行已放置好皇后
    public void backtrack(char[][] board,int row){
        if(row==board.length){
            res.add(charToList(board));
            return;
        }
        int n=board[row].length;
        for(int col=0;col<n;col++){
            if(!isVaild(board,row,col))//如果该位置不合法，则不能放置
                continue;
            //选择
            board[row][col]='Q';
            //回溯
            backtrack(board,row+1);
            //撤销
            board[row][col]='.';
        }
    }
    //将board转换为List<String>
    public List<String> charToList(char[][] board){
        List<String> result=new LinkedList<>();
        for (char[] i : board){
            String tmp=String.valueOf(i);
            result.add(tmp);
        }
        return result;
    }
    /* 是否可以在 board[row][col] 放置皇后？ */
    public boolean isVaild(char[][] board,int row,int col){
        int n = board.length;
        // 检查列是否有皇后互相冲突
        for (int i = 0; i < n; i++) {
            if (board[i][col] == 'Q')
                return false;
        }
        // 检查右上方是否有皇后互相冲突
        for (int i = row - 1, j = col + 1; 
                i >= 0 && j < n; i--, j++) {
            if (board[i][j]== 'Q')
                return false;
        }
        // 检查左上方是否有皇后互相冲突
        for (int i = row - 1, j = col - 1;
                i >= 0 && j >= 0; i--, j--) {
            if (board[i][j]== 'Q')
                return false;
        }
        return true;
    }
}