 # Untitled

a guest
Oct 14th, 2019
92
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. '''
2. Created Feburary 27th, 2019
3. States: 4 queens in 4 columns (256 states)
4. Goal test: no attacking queens
5. Evaluation:h(n) = number of attacks
6. '''
7. import random
8.
9. def calcHueristic(position, queensList):
10. #Calculate the number of a queens attacked from a particular position
11. qList = list(queensList)
12. count = 0
13. for q in qList: #Remove the queen in the same column as the position (This is the one that was moved)
14. if q == position: qList.remove(q)
15. for q in qList:
16. if q == position: count += 1 #Columns
17. if q == position: count += 1 #Rows
18. if q - q == position - position:count += 1 #Downwards Diagonal
19. if q + q == position + position:count += 1 #Upwards Diagonal
20. return count
21.
22. def checkSolution(qList):
23. for q in qList:
24. if calcHueristic(q,qList) != 0: return False
25. return True
26.
27. def chooseQueen(queensList):
28. #Choose a queen from queensList to move with the highest hueristic
29. qList = list(queensList)
30. highHnList = []
31. highHueristic = -99999999999
32. for q in qList:
33. currHn = calcHueristic(q,qList)
34. if currHn > highHueristic:
35. highHnList = []
36. highHnList.append(q)
37. highHueristic = currHn
38. elif currHn == highHueristic:
39. highHnList.append(q)
40. return random.choice(highHnList)
41.
42. def choosePosInColumn(yPos, numRows, qList):
43. #Select position in the column to move it with the lowest hueristic
44. qList = list(qList)
45. lowHnList = []
46. lowHueristic = 99999999999
47. for x in range(0,numRows): #No minus 1!!!
48. currHn = calcHueristic((x,yPos),qList)
49. if currHn < lowHueristic:
50. lowHnList = []
51. lowHnList.append((x,yPos))
52. lowHueristic = currHn
53. elif currHn == lowHueristic:
54. lowHnList.append((x,yPos))
55. return random.choice(lowHnList)
56.
57. def main():
58. ###Note: Hueristic refers to the number of other queens a queen attacks###
59. numRows = numColumns = 4
60.
61. queensList = []
62. #Produce 1 queen per column
63. for i in range(0,numRows):
64. queensList.append((random.randint(0,numRows-1), i))
65. print("Initial List: ", queensList)
66.
67. count = 0
68. while (not checkSolution(queensList)):
69. #Choose a new queen to move with the highest hueristic
70. queen = chooseQueen(queensList)
71. #Select position in the column to move it with the lowest hueristic
72. newPosition = choosePosInColumn(queen,numRows,queensList)
73. #Change position of the queen in the same column
74. for index,q in enumerate(queensList):
75. if q == newPosition:
76. queensList[index] = newPosition
77. count+=1
78. print("Move:",count,"",queensList)
79.
80. main()
RAW Paste Data