n

-Queens problem. The

objective is to place

n

queens on a

n

n

chess board: no two queens are allowed to be in

the same row, column, or a diagonal.

You can represent a board configuration with a simple

n

-element sequence

Q

n

=

{

q

0

q

1

q

n

1

}

;

q

i

corresponds to the column position of

i

th queen in row

i

. For example,

{

0 2 1 3

}

would

correspond to the 4 queens in positions (0

,

0) (row 0, column 0), (1

,

2) (row 1, column 2),

(2

,

1) (row 2, column 1), and (3

,

3) (row 3, column 3). Note that in our representation we

do not use row indexes: the

i

th queen is placed in the

i

th row and its column index is

q

i

.

To check whether a sequence

Q

n

solves the

n

-Queens problem you need to make sure that

1. Two queens do not share a column, i.e.

q

i

6

=

q

j

, for

i

6

=

j

, and

2. Two queens do not share a diagonal, i.e.

|

q

i

q

j

|6

=

|

i

j

|

, when

i

6

=

j

.

There are multiple ways to solve this problem. The simplest one would be to generate all

possible configurations and check if they solve the problem. Note that there