51 N QUEENS

不知道简书搞什么。。刚才编辑了一下这个文章(原本是3.4写的)，结果更新之后URL失效了，怎么也找不到了。。还好之前备份过RAR。简书这一点让人有点不太让人放心了，看来要经常备份才行。

这题是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操作。(我这里的理解可能有误。不需要remove的原因也许仅仅是因为 stack回到了上一个状态，那个状态下的数组col[row]还没有被插入)

下面的代码看似很长，其实dfs核心的部分很短，很大一部分是用来打印结果的。我们知道DFS的套路，我自己总结一下大概是这样的：

终止条件
构造结果
backtracking
恢复现场。

类似套路的题目有: LetterCombinationsOfAPhoneNumber、CombinationSum、Unique Binary Search Trees II 等等。

这题的终止条件里面顺便做了打印操作所以显得很长。这题不需要恢复现场现场（remove操作）。

    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;
    }
复制代码

相关文章：