Guest User

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[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