class FilaDePrioridade:
    def __init__(self,fn):
        self.l = []
        self.fn = fn

    def add(self,item):
        self.l.append(item)

    def extend(self,item):
        self.l.extend(item)

    def pop(self):
        self.l.sort(key=lambda x: x.custo)
        return self.l.pop()

    def is_empty(self):
        return self.l == []

class No:
    def __init__(self, estado, custo=0, profundidade=0):
        self.estado = estado
        self.custo = custo
        self.profundidade = profundidade
        self.sucessores = []

    def sucessor(self):        
        n = len(self.estado)
        x = self.profundidade
        self.sucessores = []
        for i in range(x,n):
            for j in range(n):
                novo = dict(self.estado)
                novo[i] = j
                self.sucessores.append(No(novo, conflitos(novo), x+1))
        return self.sucessores

    def get_sucessores(self):
        return [x for x in self.sucessor() if conflitos(x.estado) == 0]
        

    def f(self):
        return self.custo + self.profundidade

def f(n):
    return n.profundidade + n.custo

def conflito(row1, col1, row2, col2):
    return (row1 == row2
            or col1 == col2 
            or row1-col1 == row2-col2  
            or row1+col1 == row2+col2) 

def conflitos(estado):
    n = len(estado)
    c = 0
    for i in xrange(n):
        for j in xrange(i+1,n):
            if estado[i] <> None and estado[j] <> None:
                c += conflito(estado[i], i, estado[j], j)
    return c


def e_meta(estado):
    if estado.custo == 0 and e_completo(estado.estado):
        return True
    return False

def e_completo(estado):
    for item in estado.values():
        if item == None: return False
    return True

def a_estrela(n):
    abertos = FilaDePrioridade(f)
    fechados = []
    abertos.add(No({}.fromkeys(range(n))))
    while not abertos.is_empty():
        no = abertos.pop()
        #print "no ",no.estado,"custo ", no.custo
        if e_meta(no): return no
        if no.estado not in fechados:
            fechados.append(no.estado)
            abertos.extend(no.get_sucessores())
    return None
    
if __name__ == '__main__':
    a_estrela(9)