rainhas modificadas

Question

Para a formulação de N rainhas modificadas.

Ao contrário do problema original das Rainhas, há apenas uma regra - todas as N rainhas devem ser colocadas primeiro em linha .

O objetivo é selecionar o menor inteiro $p$ de tal modo que $p^2 \geq N$.

Estou pensando nesta expressão booleana para x_i_j , que representa$i$-ésima linha e $j$-ésima coluna:

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

A expressão está representada corretamente? Ou haverá 'ou' em vez de '&'. Qualquer pista / ajuda será apreciada.

Answer 1

Sua expressão não parece estar correta, a maneira como você a escreveu será avaliada como booleana verdadeira apenas se houver rainha em todas as posições no $p \times p$borda. O que você quer em vez disso é identificar a localização da última rainha para que$N$ rainhas são colocadas, diga que estará em posição $i,j$ (nós devemos ter $(i-1)p+j=N$) Então nós queremos tudo$x_{a,b}$ com $a \leq i$ ou $a=i$ e $b \leq j$para avaliar como verdadeiro. O resto das posições não terá rainha, então$x_{a,b}$deve avaliar como falso lá. Se você escrever em uma pequena matriz, você quer

\ 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 & \ & true \\ \ vdots \\ i-1 & true & true & \ dots & true & true & \ dots & true \\ 2 & true & true & \ dots & true & true & \ & true \\ \ vdots \\ i-1 & true & true & \ dots & true & i. 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}

Portanto, agora basta conectá-los com lógico e, usar negação lógica onde a variável precisa ser avaliada como falsa, e você deve obter algo assim:

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