## 8 Queens Puzzle

♛♛♛♛♛♛♛♛

Here’s one of my favourite recipes, by Raymond Hettinger, lightly adapted for Python 3.

```
from itertools import permutations
n = width_of_chessboard = 8
sqs = range(n)
Qs = (Q for Q in permutations(sqs)
if n == len({Q[i]+i for i in sqs})
== len({Q[i]-i for i in sqs}))
```

We start by assigning `sqs`

to the range 0 through 7.

```
>>> sqs = range(8)
>>> list(sqs)
[0, 1, 2, 3, 4, 5, 6, 7]
```

The range has 8 indices. If each index represents a column on a standard 8x8 chessboard and the value at that index represents a row on the same chessboard, then our range represents 8 positions on the board. Using the built-in enumerate function to generate these `(index, value)`

pairs we see that `sqs`

encodes the diagonal `(0, 0)`

to `(7, 7)`

:

```
>>> list(enumerate(sqs))
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (7, 7)]
```

Next, permute the values — the rows.

```
>>> from itertools import permutations
>>> rooks = permutations(sqs)
>>> next(rooks)
(0, 1, 2, 3, 4, 5, 6, 7)
>>> next(rooks)
(0, 1, 2, 3, 4, 5, 7, 6)
>>> next(rooks)
(0, 1, 2, 3, 4, 6, 5, 7)
>>> list(rooks)[34567]
(6, 7, 0, 1, 3, 4, 5, 2)
```

Itertools.permutations generates values lazily. The snippet above shows the first two results, then skips forward 34568 places. `Permutations(sqs)`

generates all possible arrangements of 8 pieces on a chessboard such that each row has exactly one piece on it and so does each column. That is, it generates all possible ways of placing 8 rooks on a chessboard so that no pair attacks each other.

In the final program, we filter these rook positions to generate solutions to the more challenging — and more interesting — eight Queens puzzle.

Consider our starting point, the diagonal `(0, 0)`

to `(7, 7)`

```
>>> diagonal = range(8)
>>> {r-c for c,r in enumerate(diagonal)}
{0}
>>> {r+c for c,r in enumerate(diagonal)}
{0, 2, 4, 6, 8, 10, 12, 14}
```

Here, a set comprehension collects the distinct values taken by the difference between the row and column along this diagonal, which in this case gives `{0}`

. That is, if we placed 8 bishops along this ↗ diagonal they would all attack each other along this diagonal. The sum of the row and column takes 8 distinct values, however, meaning no pair attacks along a ↖ diagonal.

Comparison operators chain in Python, so the expression:

```
n == len({Q[i]+i for i in sqs}) == len({Q[i]-i for i in sqs})
```

is `True`

if both sets have 8 elements, that is, if the squares in `Q`

are on distinct ↖ and ↗ diagonals; or, equivalently no pair of bishops placed on the squares in `Q`

would attack each other. Since we already know `Q`

positions 8 rooks so that no pair attacks each other, and a chess Queen combines the moves of a rook and a bishop, we can see that `Qs`

generates every possible way of placing 8 Queens on a chessboard so that no pair attacks each other: which is to say, we’ve solved the 8 Queens puzzle.

```
Qs = (Q for Q in permutations(sqs)
if n == len({Q[i]+i for i in sqs})
== len({Q[i]-i for i in sqs}))
```

This is beautiful code and there’s one final twist.

`Qs`

is a generator expression primed to permute squares into neighbourly rooks filtered by amicable bishops yielding unthreatening Queens. Until asked, however, it does nothing.

♕♕♕♕♕♕♕♕