什么是大O的数独使用蛮力回溯？

Question

我想知道一个简单的蛮力回溯数独算法的大O是什么。

Sudoku有4个限制：

1. 单元格-一个单元格可以包含一个数字最大值。
2. 区域-区域中的数字必须不同。
3. 同一行的行号必须是不同的。
4. 同一列的列号必须是不同的。

考虑到9x9网格：

3|___|___________
_|_ _|_ _ _ _ _ _
_|___|_ _ _ _ _ _
_|_ _ _ _ _ _ _ _
_|_ _ _ _ _ _ _ _
_|_ _ _ _ _ _ _ _
_|_ _ _ _ _ _ _ _
_|_ _ _ _ _ _ _ _
_|_ _ _ _ _ _ _ _

我认为行、列和区域约束都是O(n!)(N) (n)(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)(n-7)(n-8)

但是，考虑到一个唯一的9x9 Sudoku解决方案必须有至少17个给定的解决方案才能存在，我现在还不确定。排列数为O(n^(n^2-k))，其中k= 17，但这不包括约束满足，我确信它不是指数O(c^n)，就是阶乘O(n!)至少。

因此，问题再次是，什么是大O的sudoku使用蛮力回溯和约束满意，以及为什么？不(原木！)？

Answer 1

虽然这个答案可能有点挑剔，但复杂性是O(1)；因为数独是在一个固定大小的9*9单元的网格上播放的，每个单元都完全承认9不同的状态之一，即使用蛮力方法延长给定的部分分配所需的恒定时间，即分配{1,...,9}中的一个值。否则，就必须澄清问题中所提到的n究竟是什么。

尽管如此，如果n应该是板大小，即存在n*n，m是每个单元的可能状态数，b1是区域数，b2是区域大小(即每个b1区域都有b2*b2单元)，则运行时复杂性可以通过以下推理粗略估计。板上有m^(n*n)状态；检查董事会的状态是否合法，对于sudou规则，需要执行(n^2)*b1*(b2^2)操作，即检查每行、列和块中每个单元格状态的唯一性。总之，一项可行的任务是可以确定的。

O(m^{n*n}*(n^2)*b1*(b2^2))

步骤。