from nqueens import *
from random import *
from math import *

class SimulatedAnnealing:
    def __init__(self):
        self.initialTemp = 10.0
        self.rate = 0.001
    def randomSuccessor(self, successors):
        return successors[randint(0,len(successors)-1)]
    def schedule(self, time):
        return self.initialTemp - (self.rate * time)
    def search(self, initialState):
        time = 1
        currentState = initialState
        while True:
            currentValue = currentState.eval()
            temp = self.schedule(time)
            if temp <= 0:
                return currentState
            if time%100 == 0:
                print "Time:", time, "Temp:", temp, "Current score:", \
                      currentValue
            nextState = self.randomSuccessor(currentState.successors())
            diff = nextState.eval() - currentValue
            if diff > 0 or random() < exp(diff/temp):
                currentState = nextState
            time += 1

if __name__ == '__main__':
    print SimulatedAnnealing().search(NQueens(n=6))