from nqueens import *

class HillClimbing:
    def __init__(self):
        self.progressLimit = 10
        self.restartLimit = 5
    def bestSuccessor(self, successors):
        bestIndex = 0
        bestScore = successors[0].eval()
        for i in range(1, len(successors)):
            currentScore = successors[i].eval()
            if currentScore > bestScore:
                bestIndex = i
                bestScore = currentScore
        return successors[bestIndex]
    def search(self, initialState):
        stepsWithoutProgress = 0
        restarts = 0
        currentState = initialState
        while True:
            if currentState.goalFound():
                print "Goal found"
                return currentState
            nextState = self.bestSuccessor(currentState.successors())
            nextValue = nextState.eval()
            currentValue = currentState.eval()
            print "Current score:", currentValue, "Next score:", nextValue
            if nextValue < currentValue:
                return currentState
            if nextValue == currentValue:
                stepsWithoutProgress += 1
            else:
                stepsWithoutProgress = 0
            if stepsWithoutProgress > self.progressLimit:
                restarts += 1
                if restarts > self.restartLimit:
                    print "Goal not achieved"
                    return currentState
                else:
                    nextState = NQueens(n=len(currentState.board))
                print "\nHill climbing restarted..."
            currentState = nextState


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