This post originated from an RSS feed registered with Python Buzz by Thomas Guest. Original Post: 8 Queens Puzzle Feed Title: Word Aligned: Category Python Feed URL: http://feeds.feedburner.com/WordAlignedCategoryPython Feed Description: Dynamic languages in general. Python in particular. The adventures of a space sensitive programmer. Latest Python Buzz Posts Latest Python Buzz Posts by Thomas Guest Latest Posts From Word Aligned: Category Python

♛♛♛♛♛♛♛♛

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 = list(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 list formed from the range 0 through 7.

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

The list 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 list represents 8 positions on the board. Using the built-in enumerate function to generate these (index, value) pairs we see that sqs initially 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 list 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 = list(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.

♕♕♕♕♕♕♕♕