16 exercise 27 queens problem the n queens problem is the problem of p

Question

16
Exercise 27 (Queens Problem). The n-Queens Problem is the problem of placing n queens on
an nxn chessboard so that no two queens can attack each other. A solution of the problem
when n-6 is shown on the left of Figure 1.2. In this exercise we specify the requirements of a
solution for the n-Queens Problem as a propositional wif , with one such wff for every n 4.
(There are no solutions for n-2 and 3.) For convenience, we use a set of doubly-indexed
propositional variables, instead of P, where the indices range over the positive integers:
Q={LJE(L2}}-
The desired wif, in this exercise is in WFF(Q). We set the variable to truth value trae
(resp. false) if there is (resp. there is not) a queen placed in position (i, j) of the board, where we
take the first index i (resp. the second index j) to range over the vertical axis downward (resp.
CHAPTER 1. PROPOSITIONAL LOGIC
the horizontal axis rightward); that is, i is a row number and j is a column mmber. There are
four parts in this exercise:
1. Write the wife and justify how it accomplishes its task.
Hint: Write as a conjunction
(a)
(b)
(e)
(d)
Aqide Age, where
is satisfied if there is exactly one queen in each row,
is satisfied if there is exactly one queen in each column,
is satisfied if there is at most one queen in each diagonal,
is satisfied if there is at most one queen in each antidiagonal.
Further Hist: Given any two distinct positions (is, ji) and (ia, ja) along a diagonal, it is
always the case that is −j 12-ja. And if the two positions are along an antidiagonal,
then it is always the case that i, +₁=₂+/
2. Imagine now an infinite chessboard, which occupies the entire south-east quadrant of the
Cartesian plane. The coordinates along the vertical and horizontal axes are, respectively, i
(increasing downward) and j (increasing rightward), both ranging over the positive integers
(1,2,...). In an attempt to repeat the argument in Example 20 and Exercise 21, someone
once defined the set of wis {n>4), and wrote the following (in outline here):
The set I is finitely satisfiable and, therefore, satisfiable by Compactness. Hence,
there exists a solution of the Infinite Queens Problem, which satisfies conditions
{(a), (b), (c), (d)) for all
4.
3. Your task is to define an infinite set
that:
What is wrong with the preceding argument? The answer is subtle and you need to be
careful.
(₁|k> 1} of distinct propositional weff's such
(a) For every > 1 there is n1 such that satisfaction of wff 8, implies satisfaction of
wif, defined in part 1 of this exercise, ie, satisfaction of 6, defines a solution of the
x-Queens Problem.
(b) For all >k> 1, if satisfaction of welf's By and define solutions of the n'-Queens
Problem and Queens Problem, respectively, then n²>n.
(e) Every finite subset ofis satisfiable.
Hint: For part (a), make 8 define a particular n-Queens Problem, ie, is satisfied by
exactly one truth assigment of the variables occurring in 6. For (b) and (c), read and
understand the subsection entitled "A second solution of the infinite Queens Problem" in
Appendix G.
4. Let be the infinite set of weff's defined in the preceding part. Use Compactness for PL to
give a rigorous argument that the Infinite Queens Problem has indeed a solution.
0