nQueens.py

import sys, time, random

def nQueens(n):
    board = [i for i in xrange(n)]
    optimal = 0
    current = n * (n - 1) / 2
    
    if n < 4:
        return board

    while current > optimal:
        j = random.randint(0, n - 1)

        attack = [0 for i in xrange(n)]
        for i in xrange(n):
            if i == j: continue
            d1 = board[i] + j - i
            d2 = board[i] + i - j
            if 0 <= d1 and d1 < n: 
                attack[d1] += 1
            if 0 <= d2 and d2 < n: 
                attack[d2] += 1
            attack[board[i]] += 1

        small = n
        moves = []
        for i in xrange(n):
            if attack[i] < small:
                moves = []
                small = attack[i]
            if attack[i] == small:
                moves.append(i)

        current += small - attack[board[j]]
        board[j] = random.choice(moves)

    return board

if __name__ == '__main__':
    n = int(sys.argv[1]) if len(sys.argv) >= 2 else 8
    verbose = False if len(sys.argv) >= 3 else True

    start = time.time()
    result = nQueens(n)
    end = time.time()
    
    if verbose: print result
    print "Time: %.4f seconds" % (end - start)