reines modifiées

Question

Pour la formulation d'une N reines modifiée.

Contrairement au problème original des reines, il n'y a qu'une seule règle: toutes les N reines doivent être placées en premier par rang .

Le but est de sélectionner le plus petit entier $p$ tel que $p^2 \geq N$.

Je pense à cette expression booléenne pour x_i_j , qui représente$i$-ème rangée et $j$-ème colonne:

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

L'expression est-elle correctement représentée? Ou il y aura «ou» au lieu de «&». Tout indice / aide sera apprécié.

Answer 1

Votre expression ne semble pas correcte, la façon dont vous l'avez écrite ne sera évaluée à boolean true que s'il y a une reine à chaque position sur le $p \times p$planche. Ce que vous voulez à la place est d'identifier un emplacement de la dernière reine afin que$N$ les reines sont placées, disons qu'elles seront en position $i,j$ (nous devons avoir $(i-1)p+j=N$). Alors nous voulons tout$x_{a,b}$ avec $a \leq i$ ou $a=i$ et $b \leq j$pour évaluer à vrai. Le reste des positions n'aura pas de reine, donc$x_{a,b}$devrait évaluer faux là-bas. Si vous l'écrivez dans une petite matrice, vous voulez

\ 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 & true & true & true & true dots & true & false & \ dots & false \\ i + 1 & false & false & \ dots & false & false & \ dots & false \\ \ vdots \\ p & false & false & \ dots & false & false & \ dots & false \ end {array}

Alors maintenant, connectez-les simplement avec logique et, utilisez la négation logique où la variable doit être évaluée à false, et vous devriez obtenir quelque chose comme ceci:

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