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

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

Python, 110 lines
 ``` 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. Not Your 16 years, 6 months ago

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 16 years, 6 months ago

(...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 16 years, 6 months ago

broken comment function? see code here: http://www.rafb.net/paste/results/lmHVzI64.html Niki Estner 16 years, 6 months ago

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) 16 years, 6 months ago

Comparison? It would be interesting if someone could compare these various solutions w.r.t time and space complexity. Stephen Chappell 16 years, 6 months ago

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 16 years, 6 months ago

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 16 years, 4 months ago

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. Created by Shalabh Chaturvedi on Sat, 4 Feb 2006 (PSF)