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[1] == position[1]: qList.remove(q)
  15.     for q in qList:
  16.         if q[0] == position[0]: count += 1 #Columns
  17.         if q[1] == position[1]: count += 1 #Rows
  18.         if q[0] - q[1] == position[0] - position[1]:count += 1 #Downwards Diagonal
  19.         if q[0] + q[1] == position[0] + position[1]: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[1],numRows,queensList)
  73.         #Change position of the queen in the same column
  74.         for index,q in enumerate(queensList):
  75.             if q[1] == newPosition[1]:
  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. OK, I Understand
 
Top