## 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)
(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.

♕♕♕♕♕♕♕♕