big-o - ブルート フォース バックトラッキングを使用した数独の Big-O とは何ですか?

Question

単純な力ずくでバックトラックする数独解決アルゴリズムの Big-O とは何だろうと思っていました。

数独には 4 つの制約があります。

1. セル - 1 つのセルに最大 1 つの数値を含めることができます
2. 地域 - 地域の数字はすべて異なる必要があります
3. 行 - 同じ行の数字はすべて異なる必要があります
4. 列 - 同じ列の数字はすべて異なる必要があります

9x9 グリッドの場合:

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

(n)(n-1)(n-2)(n-3)(n-4)(n-5)(n-6)なので、行、列、および領域の制約はすべてO(n!)だと思います(n-7)(n-8) 各行、列、および領域がいっぱいになると。

しかし、一意の 9x9 数独ソリューションが存在するためには、少なくとも 17 の特定のソリューションが存在する必要があるため、今はわかりません。順列の数は O(n^(n^2 - k)) で、ここで k = 17 は純粋なブルート フォースの場合ですが、これには制約の充足は含まれません。これは、指数 O(c^n) または階乗 O であると確信しています。 (n!) 少なくとも。

もう一度質問は、数独の Big-O とは何ですか? O(log n!)?