c++ - 这个算法解决数独的时间复杂度是多少？

Question

Sudoku Solver
Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.
You may assume that there will be only one unique solution.

---

Personally I think,
time complexity = O((n^2)!), n is the number of rows(cols) of the board.

---

C++

class Solution {
public:
    void solveSudoku(vector<vector<char> > &board) {
        // Input validation.
        if (board.size() == 0 ||
            board.size() != board[0].size() ||
            board.size() % 3 != 0) return;

        helper(board);
    }

    bool helper(vector<vector<char>>& board) {
        // Base case.
        // ... ...

        for (int row = 0; row < board.size(); row ++) {
            for (int col = 0; col < board[0].size(); col ++) {
                if (board[row][col] != '.') continue;

                for (char num = '1'; num <= '9'; num ++) {
                    if (isValid(board, num, row, col)) {
                        // Have a try.
                        board[row][col] = num;

                        // Do recursion.
                        if (helper(board)) return true;;

                        // Roll back.
                        board[row][col] = '.';
                    }
                }
                // Can not find a suitable number[1-9].
                return false;
            }
        }

        return true;
    }

    bool isValid(const vector<vector<char>>& board, char num, int row, int col) {
        // Check row.
        for (int tmp_col = 0; tmp_col < board[0].size(); tmp_col ++) {
            if (board[row][tmp_col] == num) return false;
        }

        // Check col.
        for (int tmp_row = 0; tmp_row < board.size(); tmp_row ++) {
            if (board[tmp_row][col] == num) return false;
        }

        // Check sub square.
        int start_row = (row / 3) * 3;
        int start_col = (col / 3) * 3;
        for (int row = start_row; row < start_row + 3; row ++) {
            for (int col = start_col; col < start_col + 3; col ++) {
                if (board[row][col] == num) return false;
            }
        }

        return true;
    }
};

Answer 1

您假设 O((n^2)!) 的原因是什么？由于这是一个带有回溯的经典递归，我认为它是 O(n^n)，但没有深入分析问题。尝试制作一个每次递归调用函数时递增的计数器。然后看看在算法结束时它是否更接近 387 420 489(我的猜测)或 579 712 600 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 00 0 0 0 0 0 0 000 00 0 0 0 0 000 000 000 000 000 000 000 000 000 000(您的猜测)。

如果你想要更复杂的解释，我很乐意给出一个。

编辑:在思考详细解释时，我注意到我对数字的理解是错误的，它们实际上应该高得多。

许多递归搜索可以建模为树。在数独游戏中，每次尝试一个新领域时，您都有 9 种可能性。最多，您必须将解决方案放入所有 81 个字段中。此时可以帮忙画出来，以便看到，得到的搜索空间是一棵树，深度为81，每层的每个节点的分支因子为9，每个叶子都是一个可能的解决方案。给定这些数字，搜索空间为 9^81。

由于您在尝试 81 次后不检查解决方案是否正确，但在每次尝试后，实际搜索空间要小得多。我真的不知道如何把它变成数字，作为粗略估计，每次你设置 n 次尝试时，分支因子可能会变小 1。但是给定任何带有 k 个预设数字的数独游戏，您可以 100% 肯定地说，您最多需要 n^(n²-k) 次尝试。

这有道理吗？