51. N 皇后

class Solution {
    private static final char Q = 'Q';
    private static final char P = '.';
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                board[i][j] = P;
            }
        }
        return this.solve(board, 0);
    }
    /**
     * 解决第i个（行）皇后的放置情况
     * @param board
     * @param i
     * @return
     */
    private List<List<String>> solve(char[][] board, int i){
        List<List<String>> resList = new ArrayList<>();
        int n = board.length;
        if (i < n) {
            //皇后还没有放置完，遍历尝试放置r行的n个位置
            for (int j = 0; j < n; j++) {
                if (this.isValid(board, i, j)) {
                    //该位置有效,放置皇后后，继续解决下一个皇后
                    board[i][j] = Q;
                    resList.addAll(this.solve(board, i + 1));
                    //为了寻找本行的其他种情况，需要将防止的皇后恢复
                    board[i][j] = P;
                }
            }
        }else{
            //皇后放置完了，将board的数据转换成题目要求形式
//            print(board);
            resList.add(this.convert(board));
        }
        return resList;
    }
    /**
     * 判断board[i][j]的位置是否可以放置皇后
     * @param board
     * @param i
     * @param j
     * @return
     */
    private boolean isValid(char[][] board, int i, int j) {
        //遍历0-i行的数据(i-n行数据因为还没放置皇后都是空不需要遍历)
        int k,t;
        for (k=0;k<i;k++){
            //横竖情况
            if(board[i][k]==Q || board[k][j]==Q){
                break;
            }
            //两个斜线情况
            t = j + (k - i);
            if (t >= 0 && t < board.length && board[k][t]==Q) {
                break;
            }
            t = j-(k-i);
            if (t >= 0 && t < board.length && board[k][t]==Q) {
                break;
            }
        }
        return k==i;
    }
    /**
     * 棋盘转换成题目需要的格式
     * @param board
     * @return
     */
    private List<String> convert(char[][] board) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < board.length; i++) {
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < board.length; j++) {
                sb.append(board[i][j]);
            }
            res.add(sb.toString());
        }
        return res;
    }
    /**
     * 打印棋盘
     * @param board
     */
    private void print(char[][] board) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board.length; j++) {
                System.out.print(board[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("--------------------------");
    }
}