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

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.

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

(comment continued...)(...continued from previous comment)</pre>

broken comment function?see code here: http://www.rafb.net/paste/results/lmHVzI64.htmlAll solutions.This version prints out all solutions (uses Python 2.4 sets):Comparison?It would be interesting if someone could compare these various solutions w.r.t time and space complexity.Here are some modifications for speed.

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.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: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.