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