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

Question

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

数独有 4 个约束：

1. 单元格 - 一个单元格最多可以包含一个数字
2. region - 区域中的数字必须完全不同
3. row - 同一行上的数字必须完全不同
4. column - 同一列上的数字必须完全不同

给定 9x9 网格：

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

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

但是鉴于必须至少有 17 个给定的解决方案才能存在唯一的 9x9 数独解决方案，所以我现在不确定。排列的数量是 O(n^(n^2 - k)) 其中 k = 17 对于纯蛮力但这不包括约束满足，我确定它是指数 O(c^n) 或阶乘 O （n！）至少。

所以问题又是什么是数独的 Big-O 使用蛮力回溯和约束满足，为什么？O(log n!)?

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))

脚步。