如何获得更好的 N Queens 验证器时间复杂度

Question

我们如何降低这个 NxN 皇后矩阵验证器解决方案的时间复杂度？当我检查矩阵的每一行、每一列和每条对角线时，我有这个解决方案。如果每一行和每一列都恰好有 1 个皇后，并且矩阵的皇后不超过 1 个，则输出为真。这个解决方案有效，但我认为这是蛮力。

   public static boolean solveMatrix(int[][] matrix) {

        int row, col;
        int rowCount = matrix.length;
        int columnCount = matrix[0].length;
        int counter = 0;

        // Checking if there is 1 queen per row
        for (int i = 0; i < 8; i++) {
            counter = 0;
            for (int j = 0; j < 8; j++) {

                if (matrix[i][j] == 1) {

                    counter++;
                }

            }
            if (counter != 1) {

                return false;
            }

        }
// Checking if there is 1 queen per column
        for (int i = 0; i < 8; i++) {
            counter = 0;
            for (int j = 0; j < 8; j++) {

                if (matrix[j][i] == 1) {

                    counter++;
                }

            }
            if (counter != 1) {

                return false;
            }

        }
        // Checking first side diagonals
        for (int k = 0; k < rowCount; k++) {
            counter = 0;
            for (row = k, col = 0; row >= 0 && col < columnCount; row--, col++) {
                if (matrix[row][col] == 1) {
                    counter++;
                }
            }
            if (counter > 1) {
                return false;
            }
        }
    // Checking first side diagonals
        for (int k = 1; k < columnCount; k++) {
            counter = 0;
            for (row = rowCount - 1, col = k; row >= 0 && col < columnCount; row--, col++) {
                if (matrix[row][col] == 1) {
                    counter++;
                }
            }
            if (counter > 1) {
                return false;
            }
        }
        // Checking second side diagonals
        for (int k = rowCount - 1; k >= 0; k--) {
            counter = 0;
            for (row = k, col = columnCount - 1; row >= 0 && col >= 0; row--, col--) {

                if (matrix[row][col] == 1) {
                    counter++;
                }

            }
            if (counter > 1) {
                return false;
            }
        }
// Checking second side diagonals
        for (int k = rowCount - 1; k >= 0; k--) {
            counter = 0;
            for (row = k, col = columnCount - 1; row >= 0 && col >= 0; row--, col--) {

                if (matrix[row][col] == 1) {
                    counter++;
                }

            }
            if (counter > 1) {
                return false;
            }
        }

        return true;

    }

Answer 1

您需要使用 4 个哈希图，一个用于列，一个用于行，一个用于从左到右的对角线，一个用于从右到左的对角线。

现在，只对行和列执行一个嵌套循环。当您找到女王时，请执行以下 4 个步骤：

检查在该行索引处行哈希图中是否有皇后。如果不是，请添加行索引。如果已经有一个，return false.
检查 col 哈希图中是否有一个 queen 在该 col 索引处。如果没有，请添加 col 索引。如果已经有一个，return false.
检查在从左到右的对角线处，从左到右的对角线散列图中是否有一个皇后并采取相应的行动。请注意，对于每个从左到右的对角线 rowIndex-columnIndex 始终相同。
检查在从右到左的对角线处，从右到左的对角线哈希图中是否有一个皇后并采取相应的行动。请注意，对于每个从右到左的对角线 rowIndex+columnIndex 始终相同。

如果你成功完成了上面的嵌套循环，则说明棋盘有效。 Return 正确。

此算法在 O(n^2) 中运行，其中 n 是方阵一侧的长度。

矩阵边长 n 具有线性 space 复杂度，因为我们最多使用 4 个哈希图，每个元素最多 n 个。

如何获得更好的 N Queens 验证器时间复杂度

How to get better time complexity of N queens validator

java

algorithm

n-queens