reinas modificadas

Question

Para la formulación de N reinas modificadas.

A diferencia del problema original de las reinas, solo hay una regla: todas las N reinas deben colocarse primero en filas .

El objetivo es seleccionar el número entero más pequeño $p$ tal que $p^2 \geq N$.

Estoy pensando en esta expresión booleana para x_i_j , que representa$i$-th fila y $j$-a columna:

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

¿Está representada correctamente la expresión? O habrá 'o' en lugar de '&'. Cualquier pista / ayuda será apreciada.

Answer 1

Su expresión no parece ser correcta, la forma en que la escribió se evaluará como booleano verdadero solo si hay una reina en cada posición del $p \times p$tablero. Lo que quieres en cambio es identificar la ubicación de la última reina para que$N$ se colocan reinas, digamos que estará en posición $i,j$ (Debemos tener $(i-1)p+j=N$). Entonces queremos todo$x_{a,b}$ con $a \leq i$ o $a=i$ y $b \leq j$para evaluar como verdadero. El resto de posiciones no tendrán reina, así que$x_{a,b}$debería evaluar como falso allí. Si lo escribe en una pequeña matriz, quiere

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

Así que ahora solo conecte estos con lógica y, use la negación lógica donde la variable necesita evaluarse como falsa, y debería obtener algo como esto:

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