51. N 皇后

题目：https://leetcode-cn.com/problems/n-queens/

代码：

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("--------------------------");
    }

}

N皇后是一个很经典的题目，我这里使用的是递归的形式来暴力检索所有的情况。

首先我定义了一个board的二维数组做棋盘，并初始化棋盘。根据题目要求，任何两个皇后都不能处于同一条横行、纵行或斜线上，所以我新增了一个判断在i，j点放置皇后是否有效的方法isValid，这个方法是核心，比较难的点在于如何判断左斜线和右斜线的情况。

因为任何两个皇后都不能处于同一条横行上，且有n个皇后，棋盘大小为n*n，那么显而易见就是每一行都必须有一个皇后，所以我通过行来递归，即solve方法只遍历一行的n种放置情况，找到有效的放置点之后，再继续递归下一行。这里有个需要注意的点是，在递归调用之后，需要将本次放置的皇后的点恢复，即拿掉皇后。因为本行还有其他种放置皇后的情况待检索。

递归结束的判断条件是i==n，即皇后已经都放置完了，这个时候因为题目要求，所以我们需要将已经查找到的有效的方案转换成题目需要的数据形式，见convert方法。