#!/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 alttotal def localSearch(): nbIteration = 0 init() while total>0: nbIteration +=1 if not move2(): perturbe() return nbIteration print localSearch() # print val