0
$\begingroup$

The context is the well-known n-Queens problem and on the textbook, the following compound proposition is given:

Let $p(i,j)$ be a proposition that is $True$ iff there's a queen in the $i$th row and $j$th column, where $i = 1...n$ and $j = 1...n$.

  • to check all row contains at least one queen: $Q_1 = \land_{i=1}^n\lor_{j=1}^np(i,j)$
  • to check at most one queen per row: $Q_2 = \land_{i=1}^n\land_{j=1}^{n-1}\land_{k=j+1}^n(\lnot p(i,j)\lor\lnot p(i,k))$
    • in the textbook it has typo of using $p(k,j)$ instead of $p(i, k)$ in some spots.
  • to check at most one queen per column: $Q_3 = \land_{j=1}^n\land_{i=1}^{n-1}\land_{k=i+1}^n(\lnot p(i,j)\lor\lnot p(k,j))$
  • to assert at most one queen on the diagonals:
    • $Q_4 = \land_{i=2}^n\land_{j=1}^{n-1}\land_{k=1}^{min(i-1,n-j)}(\lnot p(i,j)\lor\lnot p(i-k,k+j))$
    • $Q_5 = \land_{i=1}^{n-1}\land_{j=1}^{n-1}\land_{k=1}^{min(n-i,n-j)}(\lnot p(i,j)\lor\lnot p(i+k,j+k))$

So, to find valid results we need: $Q = Q_1 \land Q_2 \land Q_3 \land Q_4 \land Q_5$

I'm not understanding how the Q4 and Q5 were exactly derived, whether it be the indices or the innermost conjunction, at all. The textbook didn't explain it much either. Really need someone to help break down for me. Kindly please help me here.

Here are the relevant screenshots from the textbook (in order):

https://i.sstatic.net/Jp93uQw2.png

https://i.sstatic.net/51VSVeIH.png

https://i.sstatic.net/DafzwI64.png

Also, in the textbook where it says "Note that squares (i,j) and (i', j') are on the same diagonal if either i + i' = j + j' or i - i' = j - j' [where or is exclusive here]" it should really say i + j = i' + j'

$\endgroup$
8
  • $\begingroup$ I'm curious where the confusion actually lies. Is it the inclusion of the "min" on $Q_4, Q_5$ that is the problem? $\endgroup$ Commented May 19 at 2:32
  • $\begingroup$ @BrianMoehring Just really everything about it, that included. Not really understanding where the innermost conjunction is coming from, where the indices are coming from, and the min stuff. $\endgroup$
    – Bob Marley
    Commented May 19 at 2:34
  • $\begingroup$ @BrianMoehring Kindly could you please help break it down for me? $\endgroup$
    – Bob Marley
    Commented May 19 at 4:08
  • $\begingroup$ @RolandF Thanks for the answer, but I think there's some typos in you're answer (red "\and") $\endgroup$
    – Bob Marley
    Commented May 19 at 4:33
  • $\begingroup$ Rotating coordinates in Q2,Q3 (i,j) to diagonal (k,l)=(i+j,i-j) in the conditon is trivial.Let the boundaries for all $\land$ in the form $$\land _{1\leq i\leq 8\land 1\leq j\leq 8}\ \neg Q\left(i'+i,j'+j\right) \dots $$ $\endgroup$
    – Roland F
    Commented May 19 at 4:46

1 Answer 1

1
$\begingroup$

A square chess board has coordinates $$\left\{i,j\right\}: \bigwedge_{i,j}\left( \ 1\le i\le 8, \quad 1\le j \le 8 \ \right) $$

Transform to diagonal coordinates in an infinite lattice

$$\left\{w=i+j,z=i-j\right\}: \bigwedge_{(i,j)\in \mathbb Z^2}\left( \ 1\le i\le 8, \quad 1\le j \le 8 \ \right) $$

$$\left\{ w,z \right\}: \bigwedge_{(w,z)\in \mathbb Z^2}\left( \ 1\le \frac{1}{2} (w+z)\le 8, \quad 1\le \frac{1}{2} (w-z) \le 8 \ \right) $$

$$\left\{ w,z \right\}: \bigwedge_{(w,z)\in \mathbb Z^2}\left( \ 2\le (w+z)\le 16, \quad 2\le (w-z) \le 16 \ \right) $$

$$\left\{ w,z \right\}: \bigwedge_{(w,z)\in \mathbb Z^2}\left( \ 2-z\le w\le 16-z, \quad 2+z\le w \le 16 + z \ \right) $$

A plot in Mathematica

   RegionPlot[
    And[2 - w <= z <= 16 - w, 2 + w <= z <= 16 + w], 
    {w, -8, 8}, {z, 0,16}]

Diamond Coordinates

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .