51.N皇后

参考链接

51. N 皇后 - 力扣（LeetCode）

代码随想录

在看了 Carl 哥的解题思路后，自己尝试着编码

class Solution {
    List<String> tmp;
    List<List<String>> res;
    char[][] chars;

    public List<List<String>> solveNQueens(int n) {
        tmp = new ArrayList<>();
        res = new ArrayList<>();
        chars = new char[n][n];
        //初始化棋盘
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                chars[i][j] = '.';
            }
        }
        //第一行遍历
        for (int i = 0; i < n; i++) {
            chars[0][i] = 'Q';
            tmp.add(String.valueOf(chars[0]));
            //下一行
            nextRow(0 + 1, n);
            //回溯
            tmp.remove(0);
            chars[0][i] = '.';
        }
        return res;
    }

    public void nextRow(int row, int n) {
        if (row == n) {
            //注意千万不要写成 res.add(tmp);，这样写一旦tmp更改，res也跟着更改
            res.add(new ArrayList<String>(tmp));
            return;
        }
        for (int i = 0; i < n; i++) {
            boolean flag = true;
            //检查列
            for (int j = row; j >= 0; j--) {
                if (flag && chars[j][i] == 'Q') {
                    flag = false;
                    break;
                }
            }
            //检查45度
            for (int j = row, k = i; j >= 0 && k >= 0; j--, k--) {
                if (flag && chars[j][k] == 'Q') {
                    flag = false;
                    break;
                }
            }
            //检查135度
            for (int j = row, k = i; j >= 0 && k < n; j--, k++) {
                if (flag && chars[j][k] == 'Q') {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                chars[row][i] = 'Q';
                tmp.add(String.valueOf(chars[row]));
                nextRow(row + 1, n);
                chars[row][i] = '.';
                tmp.remove(row);
            }
        }
    }
}

在几轮 Debug 后，终于通过了...

不过代码的效率不高，在 nextRow 函数中判断 同一列、45度、135度 是否有 ‘Q’ 出现时的效率不高

Carl 哥 的代码分离了行的遍历 与 合法性判断，这样确实感觉比较省时，不用在例如同一列出现‘Q’ 且 flag 为 false 时，继续判断45度和135度

除此之外，Carl 哥 还将第一行的遍历 与 其他行 的遍历合并在一个函数里面了，而自己则是分离出来了，代码质量有待提高...

代码随想录 - Carl 的 C++ 题解 / 录友的 Java 题解