問題タブ [constraint-satisfaction]

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

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

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

9x9 グリッドの場合:

(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!)?

ウィキペディアでは、次のように書かれています ( Min-conflicts algorithm ):

しかし、それはどういう意味ですか？

たとえば、N クイーン問題に対して次の行列があるとします。

ここに 3 つの競合がありますよね？

クイーンを位置 1,1 から位置 2,3 に移動すると、CONFLICTS 関数の値はどうなるでしょうか。

CONFLICTS は 2 を返す必要がありますか、それとも 4 を返す必要がありますか? つまり、この特定のクイーンの競合のみをカウントするか、ボード上のすべての競合をグローバルにカウントする必要があります。

ウィキペディアも言っている

CONFLICTS 関数は、割り当ての残りの状態がわかっている場合に、特定のオブジェクトが違反した制約の数をカウントします。

しかし、これは正しくありません。

プロローグで、次のようなすべての可能な計算を総当たりにすることができるかどうか疑問に思っていました:

私の問題は次のとおりです。Prolog を学習しているときに、NxN Sudoku ソルバーを作成したいと考えていました。このソルバーは次のような入力を取得します

それらのいくつかは変数である可能性があります。ソルバーはその数独を解かなければなりません。問題はかなり小さいです:

すべての列に個別の番号があるかどうか、これがチェックの始まりです。YfromfirstElementsOfには、指定された行の最初の要素のみが含まれている必要があります。例では:

悲しいことに、append のおかげで、常に別の空のスペースがYリストに追加されます。それは与えます：

Question1: それを取り除く方法はあり_1320ますか?

質問 2: これも正しいですか? それを使用して入力の 2 番目と 3 番目の要素を取得する方法はありますか?

背景: 自然言語を制約充足問題を表す知識ベースに変換することに成功した人がいるかどうか知りたいです。ステートメントの解決証明を実行している間に矛盾が存在するかどうかを確認するために、人のステートメントに対するプリフォーム制約の充足が必要です。これは、法廷や選挙の討論中に使用できます。

したがって、私の理想主義的なストーリーの一貫性アルゴリズムをレイアウトするには、次のようにします。

ステートメントを使用可能な句に変換するにはどうすればよいですか?

例えば：