ms_shnits

Расстановка ферзей. Поиск "в глубину" и "в ширину"

Oct 24th, 2020 (edited)
2,007
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #python 3.6.9
  2.  
  3. from copy import deepcopy
  4.  
  5. # обрабатываем законченную расстанвку ферзей
  6. def printResult(field):
  7.    
  8.     # проверяем, что ферзей нужное количество
  9.     queensCount = 0
  10.     for r in field:
  11.         for c in r:
  12.             if c == 2:
  13.                 queensCount += 1
  14.     if queensCount != len(field): return 0
  15.    
  16.     # печатаем
  17.     print("\n".join(" ".join("X" if field[r][c] == 2 else "-" for c in range(len(field[r]))) for r in range(len(field))))
  18.     print("\n")
  19.    
  20.     return 1
  21.    
  22.  
  23. # ставим ферзя в строку row
  24. def placeQueen (field, row):
  25.    
  26.     #если поле завершено, выходим
  27.     if row >= len(field):
  28.         printResult(field)
  29.         return None
  30.    
  31.     result = []
  32.     for col in range(len(field[row])):
  33.         if field[row][col]:
  34.             continue
  35.         f = [
  36.              [field[r][c] if field[r][c]
  37.               else 2 if (row==r) and (col==c)
  38.               else 1 if (row==r) or (col==c) or (abs(r-row)==abs(c-col))
  39.               else 0
  40.               for c in range(len(field[r]))]
  41.              for r in range(len(field))
  42.             ]
  43.         result += [(f, row+1)]
  44.    
  45.     return result
  46.  
  47.  
  48. # НАЧАЛЬНЫЕ ДАННЫЕ
  49. # размер поля
  50. N = 8
  51.  
  52. # НАЧАЛО ПРОГРАММЫ
  53.  
  54. field = [[0 for c in range(N)] for r in range(N)]
  55.  
  56. # поиск "в глубину"
  57. stack = [(field, 0)]
  58.  
  59. steps = 0
  60. stackDepth = 0
  61.  
  62. while stack != []:
  63.  
  64.     steps += 1
  65.    
  66.     # вытаскиваем очередной элемент из стека
  67.     item, stack = stack[0], stack[1:]
  68.    
  69.     # генерируем на его основе новые элементы
  70.     newItems = placeQueen(*item)
  71.    
  72.     # помещаем их в начало стека
  73.     if newItems:
  74.         stack = newItems + stack
  75.    
  76.     if stackDepth < len(stack):
  77.         stackDepth = len(stack)
  78.    
  79. print("Поиск в глубину завершен. Обработано элементов:", steps, "Максимальная глубина стека: ", stackDepth)
  80.  
  81.  
  82. # поиск "в ширину"
  83. queue = [(field, 0)]
  84.  
  85. steps = 0
  86. queueLength = 0
  87.  
  88. while queue != []:
  89.  
  90.     steps += 1
  91.    
  92.     # вытаскиваем очередной элемент из очереди
  93.     item, queue = queue[0], queue[1:]
  94.    
  95.     # генерируем на его основе новые элементы
  96.     newItems = placeQueen(*item)
  97.    
  98.     # помещаем их в конец очереди
  99.     if newItems:
  100.         queue = queue + newItems
  101.  
  102.     if queueLength < len(queue):
  103.         queueLength = len(queue)
  104.        
  105. print("Поиск в ширину завершен. Обработано элементов:", steps, "Максимальная глубина очереди: ", queueLength)
  106.  
  107. # КОНЕЦ ПРОГРАММЫ
RAW Paste Data