Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- '''
- 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()
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement