modified queens

63 Views Asked by At

For the formulation of a modified N queens.

Unlike the original Queens problem, there is just one rule-all N queens must be placed row-wise first.

The goal is to select the smallest integer $p$ such that $p^2 \geq N$.

I am thinking this boolean expression for x_i_j, which represents $i$-th row and $j$-th column:

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

Is the expression correctly represented? Or there will be 'or' instead of '&'. Any clue/help will be appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

Your expression does not seem to be correct, the way you wrote it will evaluate to boolean true only if there is queen on every position on the $p \times p$ board. What you want instead is to identify a location of last queen so that $N$ queens are placed, say it will be on position $i,j$ (we must have $(i-1)p+j=N$). Then we want all $x_{a,b}$ with $a \leq i$ or $a=i$ and $b \leq j$ to evaluate to true. The rest of the positions will have no queen, so $x_{a,b}$ should evaluate to false there. If you write it in a little matrix, you want

\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\\ i&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}

So now just connect these with logical and, use logical negation where the variable needs to evaluate to false, and you should get something like this:

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