модифицированные королевы

Question

Для постановки модифицированных N ферзей.

В отличие от исходной задачи ферзей, есть только одно правило - все 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$оценить как истина. В остальных позициях ферзя не будет, поэтому$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 -\ & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true & true & \ dots & true точки & true и false & \ dots & false \\ i + 1 & false & false & \ dots & false & false & \ dots & false \\ \ vdots \\ p & false & false & \ dots & false & false & \ dots & false \ end {array}

Итак, теперь просто соедините их с логическим и, используйте логическое отрицание, когда переменная должна оцениваться как ложь, и вы должны получить что-то вроде этого:

$$ 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}. $$