変更された女王

Question

修正されたNクイーンの定式化用。

元のクイーンの問題とは異なり、ルールは1つだけです。つまり、N個のクイーンすべてを最初に行方向に配置する必要があります。

目標は、最小の整数を選択することです $p$ そのような $p^2 \geq N$。

私はのために、この論理式を考えていますx_i_j表し、$i$-行と $j$-番目の列：

x_1_1 & x_1_2 & ...x_1_p &
x_2_1 & x_2_2 & ...x_2_p &
... &
... &
x_p_1 & x_p_2 & ...x_p_p

式は正しく表現されていますか？または、「＆」の代わりに「または」が表示されます。手がかり/助けがあれば幸いです。

Answer 1

あなたの表現は正しくないようです、あなたがそれを書いた方法は、上のすべての位置に女王がいる場合にのみブール値trueと評価されます $p \times p$ボード。代わりに必要なのは、最後の女王の場所を特定して、$N$ クイーンが配置され、配置されると言います $i,j$ （私たちは持っている必要があります $(i-1)p+j=N$）。それなら私たちはすべてが欲しい$x_{a,b}$ と $a \leq i$ または $a=i$ そして $b \leq j$trueと評価します。残りのポジションにはクイーンがいないので、$x_{a,b}$そこでfalseと評価する必要があります。あなたがそれを小さなマトリックスで書くなら、あなたは欲しい

\ begin {array} {c | cc}＆1＆2＆\ dots＆j＆j + 1＆\ dots＆p \\ \ hline 1＆true＆true＆\ dots＆true＆true＆\ dots＆true \\ 2＆true＆true＆\ dots＆true＆true＆\ dots＆true \\ \ vdots \\ i-1＆true＆true＆\ dots＆true＆true＆\ sドット＆true＆false＆\ドット＆false \\ i + 1＆false＆false＆\ドット＆false＆false＆\ドット＆false \\ \ vdots \\ p＆false＆false＆\ドット＆false＆false＆\ dots＆false \ end {array}

したがって、これらを論理とに接続し、変数がfalseと評価される必要がある場合は論理否定を使用すると、次のようになります。

$$ x_{1,1} \land x_{1,2} \land \dots \land x_{1,p}\\ \land x_{2,1} \land x_{2,2} \land \dots \land x_{2,p}\\ \vdots\\ \land x_{i,1} \land x_{i,2} \land \dots \land x_{i,j} \land \lnot x_{i,j+1} \land \dots \land \lnot x_{i,p}\\ \vdots\\ \land \lnot x_{p,1} \land \lnot x_{p,2} \land \dots \land \lnot x_{p,p}. $$