eight queens

gistfile1.txt

def solve():
    board = [ [' ' for i in range(8) ] for j in range(8) ]
    start = [ 0 ] * 8
    row = 0
    nq = 0
    turn_on = False
    while row < 8:
        col = start[row]
        while col < 8:
            added = add_a_queen(board, row, col)
            if added:
                row += 1
                if row != 8:
                    break
                nq += 1
                print '----', nq
                setup_next(board, start)
            row -= 1
            col = save_board(board, row, start)
            added = False
        if col >= 8 and not added:
            row -= 1
            if row < 0:
                return
            start[row] = save_board(board, row, start)

def setup_next(board, start):
    print_board(board)
    for row in range(8):
        for col in range(8):
            if board[row][col] == 'Q':
                start[row] = col
                break

def save_board(board, last_row, start):
    save = [(q,col) for q in range(last_row) for col in range(8) if board[q][col] == 'Q']
    start_col = [col for col in range(8) if board[last_row][col] == 'Q']
    clear_board(board)
    for row, col in save:
        place_queen(board, row, col)
    for r in range(last_row+1,8):
        start[r] = 0
    return start_col[0]+1

def pause(board, prompt='Continue? '):
    print_board(board)
    if raw_input(prompt) == 'y':
        import pdb; pdb.set_trace()

def clear_board(board):
    for i in range(8):
        for j in range(8):
            board[i][j] = ' '

def add_a_queen(board, row, start_col):
    """ places a queen on the board at 1st available location
        and blacks out the impacted squares
    """
    for col in range(start_col, 8):
        if board[row][col] == ' ':
            place_queen(board, row, col)
            return True
    return False
 
def place_queen(board, row, col):
    assert(board[row][col] == ' ')
    board[row][col] = 'Q'
    for r in range(8):
        if r == col:
            continue
        board[row][r] = 'x'
    for r in range(8):
        if r == row:
            continue
        board[r][col] = 'x'
    for r in range(1, 8):
        diag_row = row + r
        diag_col = col + r
        if diag_row < 8 and diag_col < 8:
            assert(board[diag_row][diag_col] != 'Q')
            board[diag_row][diag_col] = 'x'
    for r in range(1, 8):
        diag_row = row - r
        diag_col = col + r
        if diag_row >= 0 and diag_col < 8:
            assert(board[diag_row][diag_col] != 'Q')
            board[diag_row][diag_col] = 'x'
    for r in range(1, 8):
        diag_row = row + r
        diag_col = col - r
        if diag_row < 8 and diag_col >= 0:
            assert(board[diag_row][diag_col] != 'Q')
            board[diag_row][diag_col] = 'x'
    for r in range(1, 8):
        diag_row = row - r
        diag_col = col - r
        if diag_row >= 0 and diag_col >= 0:
            assert(board[diag_row][diag_col] != 'Q')
            board[diag_row][diag_col] = 'x'
            
            
def print_board(board):
    for row in range(8):
        print row, 
        for col in range(8):
           print board[row][col],
        print
                
if __name__ == '__main__':
    solve()