'''
Created Feburary 27th, 2019
States: 4 queens in 4 columns (256 states)
Goal test: no attacking queens
Evaluation:h(n) = number of attacks
'''
import random

def calcHueristic(position, queensList):
    #Calculate the number of a queens attacked from a particular position
    qList = list(queensList)
    count = 0
    for q in qList: #Remove the queen in the same column as the position (This is the one that was moved)
        if q[1] == position[1]: qList.remove(q)
    for q in qList:
        if q[0] == position[0]: count += 1 #Columns
        if q[1] == position[1]: count += 1 #Rows
        if q[0] - q[1] == position[0] - position[1]:count += 1 #Downwards Diagonal
        if q[0] + q[1] == position[0] + position[1]:count += 1 #Upwards Diagonal
    return count

def checkSolution(qList):
    for q in qList:
        if calcHueristic(q,qList) != 0: return False
    return True

def chooseQueen(queensList):
    #Choose a queen from queensList to move with the highest hueristic
    qList = list(queensList)
    highHnList = []
    highHueristic = -99999999999
    for q in qList:
        currHn = calcHueristic(q,qList)
        if  currHn > highHueristic:
            highHnList = []
            highHnList.append(q)
            highHueristic = currHn
        elif currHn == highHueristic:
            highHnList.append(q)
    return random.choice(highHnList)

def choosePosInColumn(yPos, numRows, qList):
    #Select position in the column to move it with the lowest hueristic
    qList = list(qList)
    lowHnList = []
    lowHueristic = 99999999999
    for x in range(0,numRows): #No minus 1!!!
        currHn = calcHueristic((x,yPos),qList)
        if  currHn < lowHueristic:
            lowHnList = []
            lowHnList.append((x,yPos))
            lowHueristic = currHn
        elif currHn == lowHueristic:
            lowHnList.append((x,yPos))
    return random.choice(lowHnList)

def main():
    ###Note: Hueristic refers to the number of other queens a queen attacks###
    numRows = numColumns = 4

    queensList = []
    #Produce 1 queen per column
    for i in range(0,numRows):
        queensList.append((random.randint(0,numRows-1), i))
    print("Initial List: ", queensList)

    count = 0
    while (not checkSolution(queensList)):
        #Choose a new queen to move with the highest hueristic
        queen = chooseQueen(queensList)
        #Select position in the column to move it with the lowest hueristic
        newPosition = choosePosInColumn(queen[1],numRows,queensList)
        #Change position of the queen in the same column
        for index,q in enumerate(queensList):
            if q[1] == newPosition[1]:
                queensList[index] = newPosition
        count+=1
        print("Move:",count,"",queensList)

main()