• API
• FAQ
• Tools
• Archive
SHARE
TWEET # Untitled a guest Oct 14th, 2019 80 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top