51. N-Queens

这题是dfs套路，按照常理想的话我们需要一个存储坐标的数据结构，但这题只要一个一维数组就够了，因为n皇后的横坐标正好是0~n-1，而且每个slot只会有一个皇后。那表，（row，col(row)）就代表Queen的坐标。
对于4皇后，前两次递归的样子是这样的：
首先，找到了row == 2的时候，发现每一个slot都不符合条件，咋办呢，不能继续DFS下去了，
结果集是(0,0) (1,2) (2,3) ____
col [] = {0,2,3,0} 第四个0是初始化的
这时候按理说应该结束上次DFS，然后去掉上次加进来的那个数字，
1000
0010
0001
0000

如果是这样的二维数组，就要把(2,3)的那个皇后拿走，置0，这样才能在第3行重新放一个皇后，但一维数组只有一个坑啊，回到row-1，再下来的时候，col[2]自然会被覆盖。所以不用remove操作。

下面的代码看上去很长，其实dfs函数的部分只有底下的递归是核心，上面的if是用来打印结果的。
这题就是典型的for循环里面进行递归的问题。在dfs条件不满足的时候

    public List<List<String>> solveNQueens(int n) {

        List<List<String>> res = new ArrayList<>();
        if (n <= 0)
            return res;

        dfs(res, 0, n, new int[n]);
        return res;
    }

    //columnVal横坐标表示Q所在行，纵坐标表示Q所在列
    public void dfs(List<List<String>> result, int row, int n, int[] col) {
        if (row == n) {
            //col = [1,4,0,3];
            List<String> cell = new ArrayList<>();
            for (int i = 0; i < row; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < row; j++) {
                    if (col[i] == j) {
                        sb.append("Q");
                    } else {
                        sb.append(".");
                    }
                }
                cell.add(sb.toString());
            }
            result.add(new ArrayList<String>(cell));
            return;
        }
        for (int i = 0; i < n; i++) {
            col[row] = i;
            if (checkValid(row, col)) {
                dfs(result, row + 1, n, col);
            }
        }

    }

    public boolean checkValid(int row, int[] col) {
        for (int i = 0; i < row; i++) {
            if (col[i] == col[row] || Math.abs(i - row) == Math.abs(col[i] - col[row]))//同一列 || 斜线
            {
                return false;
            }
        }
        return true;
    }