import random
import sys

"""
Author: Benjamin Kovach

Representation: Permutation of the set {0..N-1}. Each element indicates the row
    of the queen at index i (i corresponds to the queen's column). 
Parenthood Selection: Tournament selection twice with three combatants.
Mutation: Swap two elements of an individual's vector
Crossover: Order crossover
Survival Selection: Replace the N/3 worst individuals with N/3 new ones

Example run at bottom.
"""

# order crossover
def crossover(i1, i2):
    n = len(i1)
    r1 = random.randrange(n-1)
    r2 = random.randrange(r1, n)
    child1 = [None] * n
    child2 = [None] * n
    child1[r1:r2] = i1[r1:r2]
    child2[r1:r2] = i2[r1:r2]
    rest1 = filter(lambda e: e not in i1[r1:r2], i2)
    rest2 = filter(lambda e: e not in i2[r1:r2], i1)
    for i in xrange(len(rest1)):
        child1[(r2 + i) % n] = rest1[i]
    for i in xrange(len(rest2)):
        child2[(r2 + i) % n] = rest2[i]  
    return child1, child2

# tourament selection
def select(xs, n=3):
    selection = []
    for i in xrange(0, n):