LeetCode 51. N-Queens

Problem

LeetCode 51. N-Queens

1. 题目简述

给出一个整形数n，找出”n皇后问题“的所有解。每一行，每一列以及每个皇后所在的对角线不能包含其他皇后。例如：

Example:

Input: 4
Output: [
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

2. 算法思路

相关问题：

1. LeetCode 52. N-Queens II

极其经典的”八皇后问题“，用回溯法。跟数独问题基本上是一样的，但是要稍微简单些。

回溯法

这里问题其实是在于，如何判断当前行所放的皇后是否合理，这里我的做法是直接将二维的棋盘表示了出来，然后用board[i - x][j - x]表示左上到右下的对角线，用board[i - x][j + x]表示右上到左下的对角线（注意边界）。

但是其实还有另外一种更为节省空间的做法（其实必要性不大），用bool型数组来表示每一行、每一列、每一个对角线是否已经共存在了一个皇后。如果已知n，那么每一组（左上到右下算一组，左下到右上算一组）对角线的个数也是已知的，2n - 1，然后用[i, j]做一个映射即可。

class Solution {
    public List<List<String>> solveNQueens(int n) {
        // 也就是说每一行，每一列，每一个斜线上都不能有任意两个皇后。每一行和每一列都还算好判断，斜线上要怎么判断呢？可以用[i][j]来做映射。但是这里我打算采用一个二维数组来做计算，写起来方便。

        int[][] board = new int[n][n];
        List<List<String>> res = new ArrayList();

        backtrack(0, n, board, res);

        return res;
    }

    private void backtrack(int line, int n, int[][] board, List<List<String>> res) {
        // 判断一下是否已经填完了最后一层，如果是，则向结果集中添加一个solution
        if (line == n) {
            List<String> solution = new ArrayList();
            for (int i = 0; i < n; i++) {
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    sb.append(board[i][j] == 0 ? "." : "Q");
                }
                solution.add(sb.toString());
            }
            res.add(solution);
            return;
        }

        // 如果没有填完最后一层，则填line这一层，从0到n-1逐个尝试，每次尝试出一个valid的就继续向下一层出发。
        for (int i = 0; i < n; i++) {
            board[line][i] = 1;
            if (checkValid(board, line, i)) {
                backtrack(line + 1, n, board, res);
            }
            board[line][i] = 0;
        }

        return;
    }

    private boolean checkValid(int[][] board, int line, int pos) {
        // 检查第line行，pos位置放queen是否合法（同一行无须检查）
        int n = board.length;

        // 检查同一列
        for (int i = 0; i < line; i++) {
            if (board[i][pos] == 1) {
                return false;
            }
        }

        // 检查左上到右下的对角线，注意只用检查line线以上的即可
        for (int i = line - 1, j = pos - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        // 检查左下到右上的对角线，注意只用检查line线以上的即可
        for (int i = line - 1, j = pos + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 1) {
                return false;
            }
        }

        return true;
    }
}