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

Eight Queens using Generator (Python recipe) by Shalabh Chaturvedi
ActiveState Code (http://code.activestate.com/recipes/473832/)

A classic algorithmic problem - place 8 queens on a chess board so that none is attacked by another.

Python, 110 lines
Download
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
import sys, itertools
from sets import Set

NUM_QUEENS = 8

MAX = NUM_QUEENS * NUM_QUEENS

# Each position (i.e. square) on the chess board is assigned a number
# (0..63). non_intersecting_table maps each position A to a set
# containing all the positions that are *not* attacked by the position
# A.

intersecting_table = {}
non_intersecting_table = {}

# Utility functions for drawing chess board
def display(board):
    "Draw an ascii board showing positions of queens"
    assert len(board)==MAX
    it = iter(board)
    for row in xrange(NUM_QUEENS):
        for col in xrange(NUM_QUEENS):
            print it.next(),
        print '\n'

def make_board(l):
    "Construct a board (list of 64 items)"
    board = [x in l and '*' or '_' for x in range(MAX)]
    return board

# Construct the non-intersecting table

for pos in range(MAX):
    intersecting_table[pos] = []

for row in range(NUM_QUEENS):
    covered = range(row * NUM_QUEENS, (row+1) * NUM_QUEENS)
    for pos in covered:
        intersecting_table[pos] += covered

for col in range(NUM_QUEENS):
    covered = [col + zerorow for zerorow in range(0, MAX, NUM_QUEENS)]
    for pos in covered:
        intersecting_table[pos] += covered

for diag in range(NUM_QUEENS):
    l_dist = diag + 1
    r_dist = NUM_QUEENS - diag
    
    covered = [diag + (NUM_QUEENS-1) * x for x in range(l_dist)]
    for pos in covered:
        intersecting_table[pos] += covered

    covered = [diag + (NUM_QUEENS+1) * x for x in range(r_dist)]
    for pos in covered:
        intersecting_table[pos] += covered


for diag in range(MAX - NUM_QUEENS, MAX):
    l_dist = (diag % NUM_QUEENS) + 1
    r_dist = NUM_QUEENS - l_dist + 1

    covered = [diag - (NUM_QUEENS + 1) * x for x in range(l_dist)]
    for pos in covered:
        intersecting_table[pos] += covered

    covered = [diag - (NUM_QUEENS - 1) * x for x in range(r_dist)]
    for pos in covered:
        intersecting_table[pos] += covered

universal_set = Set(range(MAX))

for k in intersecting_table:
    non_intersecting_table[k] = universal_set - Set(intersecting_table[k])

# Once the non_intersecting_table is ready, the 8 queens problem is
# solved completely by the following method. Start by placing the
# first queen in position 0. Every time we place a queen, we compute
# the current non-intersecting positions by computing union of
# non-intersecting positions of all queens currently on the
# board. This allows us to place the next queen.

def get_positions(remaining=None, depth=0):
    m = depth * NUM_QUEENS + NUM_QUEENS

    if remaining is not None:
        rowzone = [x for x in remaining if x < m]
    else:
        rowzone = [x for x in range(NUM_QUEENS)]

    for x in rowzone:
        if depth==NUM_QUEENS-1:
            yield (x,)
        else:
            if remaining is None:
                n = non_intersecting_table[x]
            else:
                n = remaining & non_intersecting_table[x]

            for p in get_positions(n, depth + 1):
                yield (x,) + p
    return

rl = [x for x in get_positions()]

for i,p in enumerate(rl):
   print '=' * NUM_QUEENS * 2, "#%s" % (i+1)
   display(make_board(p))

print '%s solutions found for %s queens' % (i+1, NUM_QUEENS)

This is a version I wrote a while back that uses a 'non-intersecting' mapping. For each position on the board, we find all other positions are are not attacked by it. This allows us to loop through all possible combinations pretty fast.

Here is an analogy that might help. Imagine 64 glass chess board 'plates'. Each plate has a different square colored red (position of queen). Any square attacked by the red is blacked out. All other squares are transparent (or available). Hold the first plate in front of you. Place a second plate behind it so that you can see the red square through the first one. For this you have to find one where the red (position of queen) does not lie in the attack paths of the first queen (blacked out squares). Also you now have fewer transparent squares left (intersection of transparent squares of two plates). Repeat until you have 8 plates - this is one solution.

Once the non-intersecting set is built, the 8 queens problem is entirely solved in 20 lines.

Tags: algorithms

8 comments

Not Your 17 years, 10 months ago  # | flag

shorter version. The used method is propably not correct, because only the "best" board is recognized. But it works.

btw the preview function displays the posting twice

#!/usr/bin/python

coords = [ (n%8,n/8) for n in range(8*8)]                     # creates initial allowed coord list (0,1), (0,2) .. (7,7)

def queen_line( x1, y1, x2, y2 ):                             # checks if coords are on a "queen line"
  if (x1==x2) or (y1==y2) or (abs(x1-x2) == abs(y1-y2)):
    return True
  else:
    return False

def get_threat_board(x1, y1):                                 # returns a table with forbidden coords
  return [queen_line(x1, y1, x2, y2) for x2,y2 in coords]

def get_allowed_coords(current_coords, x, y):                 # does what it says ;)
  t_board = get_threat_board(x,y)
  return [ (x,y) for x,y in current_coords if not t_board[y*8+x] ]

def get_newqueen_best_coords(allowed_coords, queen_coords):   # returns a new coord list
  l_pcoords = []
  best_coords = None
  c_max_ac=0
  for x,y in allowed_coords:
    ac = get_allowed_coords(allowed_coords, x,y)
    if (len(ac) > c_max_ac):
      best_coords = ac
      c_max_ac = len(ac)
      qx=x
      qy=y
  return best_coords, queen_coords+[(qx, qy)]

def print_board(queen_coords):
  for x in range(8):
    for y in range(8):
      print [' ', 'Q'][(x,y) in queen_coords],
    print

if __name__=="__main__":
  allowed_coords=coords
  queen_coords=[]
  while len(queen_coords)The used method is propably not correct, because only the "best" board is recognized. But it works.

btw the preview function displays the posting twice
<pre>
#!/usr/bin/python

coords = [ (n%8,n/8) for n in range(8*8)]                     # creates initial allowed coord list (0,1), (0,2) .. (7,7)

def queen_line( x1, y1, x2, y2 ):                             # checks if coords are on a "queen line"
  if (x1==x2) or (y1==y2) or (abs(x1-x2) == abs(y1-y2)):
    return True
  else:
    return False

def get_threat_board(x1, y1):                                 # returns a table with forbidden coords
  return [queen_line(x1, y1, x2, y2) for x2,y2 in coords]

def get_allowed_coords(current_coords, x, y):                 # does what it says ;)
  t_board = get_threat_board(x,y)
  return [ (x,y) for x,y in current_coords if not t_board[y*8+x] ]

def get_newqueen_best_coords(allowed_coords, queen_coords):   # returns a new coord list
  l_pcoords = []
  best_coords = None
  c_max_ac=0
  for x,y in allowed_coords:
    ac = get_allowed_coords(allowed_coords, x,y)
    if (len(ac) > c_max_ac):
      best_coords = ac
      c_max_ac = len(ac)
      qx=x
      qy=y
  return best_coords, queen_coords+[(qx, qy)]

(comment continued...)

Not Your 17 years, 10 months ago  # | flag

(...continued from previous comment)

def print_board(queen_coords):
  for x in range(8):
    for y in range(8):
      print [' ', 'Q'][(x,y) in queen_coords],
    print

if __name__=="__main__":
  allowed_coords=coords
  queen_coords=[]
  while len(queen_coords)

</pre>

Not Your 17 years, 10 months ago  # | flag

broken comment function? see code here: http://www.rafb.net/paste/results/lmHVzI64.html

Niki Estner 17 years, 10 months ago  # | flag

All solutions. This version prints out all solutions (uses Python 2.4 sets):

N = 8

all_positions = set([(i,j) for i in range(N) for j in range(N)])

def reachablePositions(x,y):
    s  = set([(x,i) for i in range(N)]) # vertical
    s |= set([(i,y) for i in range(N)]) # horizontal
    s |= set([(x+i,y+i) for i in range(-N,N)]) # diagonal \
    s |= set([(x+i,y-i) for i in range(-N,N)]) # diagonal /
    return s

def place_queens(current_solution = [], allowed_positions = all_positions):
    if len(current_solution) == N: # only N queens to place - done
        yield current_solution
        return
    y = len(current_solution) # place queens line by line
    for x in range(N):
        if (x,y) in allowed_positions:
            for s in place_queens(current_solution+[(x,y)], allowed_positions - reachablePositions(x,y)):
                yield s

def printBoard(b):
    print '\n'.join([' '.join([('.', 'Q') [(x,y) in b] for x in range(N)]) for y in range(N)])

for i,b in enumerate(place_queens()):
    print "Solution", i, b
    printBoard(b)
    print
Shalabh Chaturvedi (author) 17 years, 10 months ago  # | flag

Comparison? It would be interesting if someone could compare these various solutions w.r.t time and space complexity.

Stephen Chappell 17 years, 10 months ago  # | flag

Here are some modifications for speed.

# Utility functions for drawing chess board
def display(board):
    "Draw an ascii board showing positions of queens"
    string = str()
    assert len(board)==MAX
    it = iter(board)
    for row in xrange(NUM_QUEENS):
        for col in xrange(NUM_QUEENS):
            string += it.next() + ' '
        string += '\n'
    return string

for i,p in enumerate(rl):
   print '=' * NUM_QUEENS * 2, "#%s\n%s" % (i+1, display(make_board(p)))
Andre Roberge 17 years, 10 months ago  # | flag

non-generator ... but well-known. Check http://en.wikipedia.org/wiki/8_queens_problem; it has a Python solution for the n-queen problem. I even adapted it for my "Python Learning Environment" (rur-ple) where one can visually place 8 "queens" (Robots!) with colored lines showing which squares are under attack by each queen. Even though the use of generator is "interesting", I don't think that solution to such well-known problems belong in this cookbook.

Connelly Barnes 17 years, 8 months ago  # | flag

Instructive. I'm not sure if 8-queens belongs in the Python Cookbook, but I do think the Python solutions to the problem are instructive. For example, I can't think of an elegant way to solve this problem in C++, but in Python I would say that using permutations and generators gives an intuitive and elegant (albeit slow) solution:

def permutations(L):
  if len(L) &lt;= 1:
    yield list(L)
  else:
    for i in range(len(L)):
      for p in permutations(L[:i]+L[i+1:]):
        yield [L[i]] + p

def queens(n):
  for L in permutations(range(n)):
    if (len(set(i+L[i] for i in range(n))) == n and
        len(set(i-L[i] for i in range(n))) == n):
      yield L

if __name__ == '__main__':
  for sol in queens(8):
    for col in sol:
      print '.'*col + 'Q' + '.'*(8-1-col)
    print

The code above can be shortened to 9 lines by using generator expressions in permutations() and queens(), and simply printing len(list(queens(8))). However, this reduces the clarity of the code.

Another idea is to modify permutations() to accept a "filter" function, so that if two queens share a diagonal, then we don't waste time recursing on this case.