How do I understand nested summations? 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.
 A: 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.
