#!/usr/bin/env python

# USACH - nov 2012 - c.durr
# local search for the n-queen problem

import sys, random


# the n-queen instance
n = int(sys.argv[1])

Vars = range(n)
Vals = range(n)

#val[x] = position of queen in row x
val      = [None for x in Vars]

# conflicts

# place queen x at position u will occupy 3 lines
def lines(x,u):
    return [col(x,u), diag(x,u), antidiag(x,u)]

def      col(x,u): return u
def     diag(x,u): return n+x+u
def antidiag(x,u): return 4*n-2+x-u

# present[r] = how many times line r was occupied
present = [0] * (5*n-2)
total = 0                  # nb of conflicts = #{r : present[r]>1 }

# with how many queens will val[x]:=u be in conflict?
def conflicts(x,u):
    return sum([present[r] for r in lines(x,u)])

# choose random initial assignment
def init():
    for x in Vars:
        drop(x, random.randint(0,n-1))

# make a local pertubation to escape local minima
def perturbe():
    x = random.randint(0,n-1)
    pick(x)
    drop(x, random.randint(0,n-1))

# place a queen
def drop(x,u):
    global total
    val[x]=u
    for r in lines(x,u):
        present[r] +=1
        if present[r]>1:
            total += 1

# remove a queen
def pick(x):
    global total
    for r in lines(x,val[x]):
        if present[r]>1:
            total -= 1
        present[r] -=1
    val[x]=None

# choose random conflicting queen and place at best position
def move1():
    x = random.choice([x for x in Vars if conflicts(x,val[x])>0])
    cu, u = min([(conflicts(x,u), u)  for u in Vals if u!=val[x]])
    before = total
    pick(x)
    drop(x,u)
    return before>total

# choose queen movement that is best for total number of conflicts
def move2():
    best = ([],0,0)
    for x in Vars:
        c = conflicts(x, val[x])
        for u in Vals:
            if u!=val[x]:
                alt = (conflicts(x,u)-c, x,u)
                if alt<best:
                    best = alt
    (c,x,u) = best
    before = total
    pick(x)
    drop(x,u)
    return before>total

def localSearch():
    nbIteration = 0
    init()
    while total>0:
        nbIteration +=1
        if not move2():
            perturbe()
    return nbIteration

print localSearch()
# print val