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