This question is an extension of Is there a name for this particular notation and what does it look like expanded?
I am reading Discrete Mathematics 8th Edition by Rosen. Here we are using satisfiability of compound propositions to solve the $n$-queens problem, which is placing $n$ queens on an $n \times n$ chessboard so that no queen can attack another queen (no two queens are in the same row, column, or diagonal to one another).
To model this problem, we have $n^2$ variables $p(i, j)$ for $i=1,2, \ldots, n$ and $j=1,2, \ldots, n$. $p(i,j)$ is true when there is a queen in the $i$th row and $j$th column and false otherwise.
The solution to the $n$-queens problem is given as the assignments of truth values to our variables that make
$Q=Q_{1} \wedge Q_{2} \wedge Q_{3} \wedge Q_{4} \wedge Q_{5}$ true.
$$
Q_{1}=\bigwedge_{i=1}^{n} \bigvee_{j=1}^{n} p(i, j)
$$
$$
Q_{2}=\bigwedge_{i=1}^{n} \bigwedge_{j=1}^{n-1} \bigwedge_{k=j+1}^{n}(\neg p(i, j) \vee \neg p(k, j))
$$
$$
Q_{3}=\bigwedge_{j=1}^{n} \bigwedge_{i=1}^{n-1} \bigwedge_{k=i+1}^{n}(\neg p(i, j) \vee \neg p(k, j))
$$
$$
Q_{4}=\bigwedge_{i=2}^{n} \bigwedge_{j=1}^{n-1} \bigwedge_{k=1}^{\min (i-1, n-j)}(\neg p(i, j) \vee \neg p(i-k, k+j))
$$
$$
Q_{5}=\bigwedge_{i=1}^{n-1} \bigwedge_{j=1}^{n-1} \bigwedge_{k=1}^{\min (n-i, n-j)}(\neg p(i, j) \vee \neg p(i+k, j+k))
$$
Where…
$Q_1$ asserts every row contains at least one queen
$Q_2$ asserts that there is at most one queen in each row
$Q_3$ asserts no column contains more than one queen
$Q_4$ $Q_5$ and asserts no diagonal contains two queens
$Q_1$ can be expanded to
$$
\begin{aligned}
Q_1 = \bigwedge_{i=1}^4{\bigvee_{j=1}^n{p(i,j)}} & = \bigwedge_{i=1}^4{\bigl[ p(i,1) \vee p(i,2) \vee p(i,3) \vee p(i,4)\bigr]} \\
& = \bigl[ p(1,1) \vee p(1,2) \vee p(1,3) \vee p(1,4)\bigr] \\
& ~\quad \wedge \bigl[ p(2,1) \vee p(2,2) \vee p(2,3) \vee p(2,4)\bigr] \\
& ~\quad \wedge \bigl[ p(3,1) \vee p(3,2) \vee p(3,3) \vee p(3,4)\bigr] \\
& ~\quad \wedge \bigl[ p(4,1) \vee p(4,2) \vee p(4,3) \vee p(4,4)\bigr].
\end{aligned}
$$
and I can easily enough visualize / make sense of how this asserts each row contains at least one queen.
However, the other propositions are deeply nested.. how am I to make sense of these? It seems like way too much information to keep in ones head.
Best Answer
If you are curious, the Wikipedia article Eight queens puzzle mentions many aspects of the problem that go much beyond solving the original puzzle.
The key idea in solving the puzzle using Boolean logic variables is the identification of all of the constraints needed to be satisfied for a valid placement solution. The first constraint $\,Q_1\,$ is a conjunction of disjunctions which require for every row that there is at least one queen in that row.
All of the other constraints are of the form that we forbid queen placements on certain pairs of $\,(i,j)\,$ locations. That is, we forbid a queen at $\,(i,j)\,$ and a queen at $\,(k,l)\,$ for certain pairs of locations. This is written as $\,\neg p(i,j) \vee \neg p(k,l)\,$ which is the negation of $\,p(i,j) \wedge p(k,l).\,$
The constraint $\,Q_2\,$ is to forbid placing two queens in the same row. That is we forbid $\,p(i,j) \wedge p(i,k)\,$ for any $\,i,j,k\,$ although we only require $\,j<k.\,$ Similarly, $\,Q_3\,$ is to forbid placing two queens in the same column. This condition is $\,p(i,j) \wedge p(k,j)\,$ and we only require $\,i<k.\,$ The constraints $\,Q_4\,$ and $\,Q_5\,$ are to forbid placing two queens in the same forward diagonal and the same backward diagonal respectively.
In order to visualize how these constraints are written in the $\,p(i,j) \wedge p(k,l) ,$ form, I suggest that you try some explicit $\,i,j,k\,$ numbers and see how they relate spatially on a chessboard grid.