Welcome, guest | Sign In | My Account | Store | Cart

What six lines of Python can do

Python, 8 lines
1
2
3
4
5
6
7
8
from itertools import permutations

n = 8
cols = range(n)
for vec in permutations(cols):
    if (n == len(set(vec[i]+i for i in cols))
          == len(set(vec[i]-i for i in cols))):
        print vec

Solver for the eight queens puzzle:
http://en.wikipedia.org/wiki/Eight_queens_puzzle

Computes all 92 solutions for eight queens. By setting n to different values, other sized puzzles can be solved.

The output is presented in vector form (each number represents the column position of a queen on consecutive rows). The vector can be pretty printed with this function:

def board(vec):
    '''Translate column positions to an equivalent chess board.

    >>> board([0, 4, 7, 5, 2, 6, 1, 3])
    Q-------
    ----Q---
    -------Q
    -----Q--
    --Q-----
    ------Q-
    -Q------
    ---Q----

    '''

    for col in vec:
        s = ['-'] * len(vec)
        s[col] = 'Q'
        print ''.join(s)
    print

With the solution represented as a vector with one queen in each row, we don't have to check to see if two queens are on the same row. By using a permutation generator, we know that no value in the vector is repeated, so we don't have to check to see if two queens are on the same column. Since rook moves don't need to be checked, we only need to check bishop moves.

The technique for checking the diagonals is to add or subtract the column number from each entry, so any two entries on the same diagonal will have the same value (in other words, the sum or difference is unique for each diagnonal). Now all we have to do is make sure that the diagonals for each of the eight queens are distinct. So, we put them in a set (which eliminates duplicates) and check that the set length is eight (no duplicates were removed).

Any permutation with non-overlapping diagonals is a solution. So, we print it and continue checking other permutations.

8 comments

Gabriel Genellina 12 years, 8 months ago  # | flag

awesome!

charles.merriam tollak 12 years, 7 months ago  # | flag

Very nice!

For those that like more concise output in python 3.0, I use:

print ("\n".join('.' * i + 'Q' + '.' * (n-i-1) for i in vec), end = "\n===\n")
Paddy McCarthy 12 years, 2 months ago  # | flag

I have submitted the above on Rosetta Code, on this page where it will be compared to solutions in other programming languages.

  • Paddy.
Narayana Chikkam 11 years, 4 months ago  # | flag

I have used the simple math to reduce the possibilities. However, my code is not optimal :) http://code.activestate.com/recipes/577325-eight-queens-with-out-permutations/

Stephen Chappell 10 years, 11 months ago  # | flag

You can solve the eight queens puzzle and print out the results in just four lines (adapted from the code above).

from itertools import permutations
for vector in permutations(reversed(range(8))):
    if len(set(vector[index] + index for index in range(8))) == len(set(vector[index] - index for index in range(8))) == 8:
        print('\n'.join('- ' * index + 'Q ' + '- ' * (7 - index) for index in vector), end='\n\n')
Stephen Chappell 9 years, 5 months ago  # | flag

It appears to be possible to solve the eight queens problem with just two lines:

from itertools import permutations as p
print(*('\n'.join(' -' * i + ' Q' + ' -' * (7 - i) for i in v) for v in p(range(8)) if len({v[i] + i for i in range(8)}) == 8 == len({v[i] - i for i in range(8)})), sep='\n\n')
Sumit Rangwala 9 years, 2 months ago  # | flag

The code is pure art. Another way of understanding it is that it takes projection of the queen locations along a coordinate system formed by rotating the x-y plane 45 degree in clockwise direction.

While beautiful, the code is inefficient. It will always loop n! times. A more elaborate (and less beautiful) code based on backtracking can avoid all permutations of remaining rows if the current, partial, placement of queens is invalid. This one is 20x faster on my machine for n=10 (derived from the code above)

def nqueens(r,n,p):
  s  = len(p)
  cols = range(s)
  valid = s == len(set(p[i] + i for i in cols)) == len(set(p[i] - i for i in cols))

  count = 0

  if valid:
    if r == n:
      return 1

    for c in set(range(n)) - set(p):
        count += nqueens(r + 1, n, p + [c])

  return count


def backtracknqueens(n):
    print n, nqueens(0,n,[])
Liang Junhua 9 years ago  # | flag

I like this code!

Created by Raymond Hettinger on Tue, 10 Feb 2009 (MIT)
Python recipes (4591)
Raymond Hettinger's recipes (97)
HongxuChen's Fav (39)

Required Modules

Other Information and Tasks