[Leetcode单排] N皇后 (N51 N52)

backtracking dfs search

字数统计: 755阅读时长: 3 min

 2019/07/28  Share

51. N-Queens

https://leetcode.com/problems/n-queens/

N皇后问题，这里是将花花的讲解翻成 Java 版，花花的讲解已足够简明易懂。

每个棋子在每一行每一列必须是唯一的，这倒还好，关键在于每个棋子的所在斜线和反斜线都不包含棋子。难点就在于如何确认斜线处是否有棋子。而在标准做法中，斜线和反斜线各需要一个布尔数组就可以做到，只要找到 x 及 y 下标关系即可。

从第 0 行开始，确定第 0 行 Q 所在位置，之后递归行数加 1，以此类推。

因为担心递归函数中包含变量太多，故将三个布尔数组作为了全局变量。

boolean[] cols;
boolean[] diag1;
boolean[] diag2;

public List<List<String>> solveNQueens(int n) {
    if (n <= 0) {
        return null;
    }
    cols = new boolean[n];
    // 左下-右上斜线 idx = x + y
    diag1 = new boolean[2 * n - 1];
    // 左上-右下斜线 idx = x - y + (n -1)
    diag2 = new boolean[2 * n - 1];

    List<List<String>> result = new ArrayList<>();
    List<String> initial = buildInitialList(n);
    handle(n, 0, initial, result);
    return result;
}

private void handle(int n, int row, List<String> cur, List<List<String>> result) {
    if (row == n) {
        result.add(new ArrayList<>(cur));
        return;
    }
    for (int j = 0; j < n; j++) {
        if (available(j, row, n)) {
            update(j, row, n, true, cur);
            handle(n, row + 1, cur, result);
            update(j, row, n, false, cur);
        }
    }
}

private boolean available(int x, int y, int n) {
    return !(cols[x] || diag1[x + y] || diag2[x - y + (n - 1)]);
}

private void update(int x, int y, int n, boolean state, List<String> cur) {
    cols[x] = state;
    diag1[x + y] = state;
    diag2[x - y + (n - 1)] = state;
    char[] rowArray = cur.get(y).toCharArray();
    rowArray[x] = state ? 'Q' : '.';
    cur.set(y, new String(rowArray));
}

private List<String> buildInitialList(int n) {
    List<String> res = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        StringBuilder sb = new StringBuilder();
        for (int j = 0; j < n; j++) {
            sb.append('.');
        }
        res.add(sb.toString());
    }
    return res;
}

52. N-Queens II

https://leetcode.com/problems/n-queens-ii/

52题和51题是一样的，只是这次是计算个数。这里是将 count 作为全局变量，其实可以将 handle 返回 count，亦或者 handle 在每次满足条件时返回 1，这几种做法皆可。（只要不是犯将 count 放到参数这种低级错误皆可）。

左程云的书里面还有一种使用位运算做加速的超自然做法，暂且备注一下。

int count = 0;

public int totalNQueens(int n) {
    if (n <= 0) {
        return 0;
    }
    handle(0, n, new boolean[n], new boolean[2 * n - 1], new boolean[2 * n - 1]);
    return count;
}

private void handle(int row, int n, boolean[] cols, boolean[] diag1, boolean[] diag2) {
    if (row == n) {
        ++count;
    }
    for (int j = 0; j < n; j++) {
        if (available(j, row, n, cols, diag1, diag2)) {
            modifyState(j, row, n, cols, diag1, diag2, true);
            handle(row + 1, n, cols, diag1, diag2);
            modifyState(j, row, n, cols, diag1, diag2, false);
        }
    }
}

private boolean available(int x, int y, int n, boolean[] cols, boolean[] diag1, boolean[] diag2) {
    return !(cols[x] || diag1[x + y] || diag2[x - y + (n - 1)]);
}

private void modifyState(int x, int y, int n, boolean[] cols, boolean[] diag1, boolean[] diag2, boolean state) {
    cols[x] = state;
    diag1[x + y] = state;
    diag2[x - y + (n - 1)] = state;
}

Next Post

[Leetcode单排] 数独 (N37)
Previous Post

[Leetcode单排] Subsets (N78 N90)

CATALOG

1. 51. N-Queens
2. 52. N-Queens II

