python解决八皇后算法，python皇后算法,python解决经典算法

python解决八皇后算法，python皇后算法,python解决经典算法

python解决经典算法八皇后问题,在棋盘上放置8个皇后，而不让她们之间互相攻击。

import sys, itertoolsfrom sets import SetNUM_QUEENS = 8MAX = 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 boarddef 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 tablefor 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] += coveredfor col in range(NUM_QUEENS):    covered = [col + zerorow for zerorow in range(0, MAX, NUM_QUEENS)]    for pos in covered:        intersecting_table[pos] += coveredfor 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] += coveredfor 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] += covereduniversal_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    returnrl = [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 notattacked by it. This allows us to loop through all possible combinationspretty 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 squareattacked by the red is blacked out. All other squares are transparent (oravailable). Hold the first plate in front of you. Place a second plate behindit so that you can see the red square through the first one. For this you haveto find one where the red (position of queen) does not lie in the attack pathsof the first queen (blacked out squares). Also you now have fewer transparentsquares left (intersection of transparent squares of two plates). Repeat untilyou have 8 plates - this is one solution.

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