Возврат и шахматы - PullRequest
Новая
       23

Возврат и шахматы

0 голосов
/ 19 апреля 2020

Есть шахматное поле N * N, где уже представлены некоторые черные фигуры. Найдите минимум белых королев, которые вам нужно поставить на поле, чтобы они могли побить все черные фигуры. Используя backtrack-алгоритм.

Во-первых, я помещаю все возможные королевы в позиции, где они могут побить хотя бы что-то. Как тогда я должен решить, перейдет ли королева к окончательному решению или нет?

1 Ответ

1 голос
/ 19 апреля 2020

В рекурсивном псевдокоде: 

minQueensNeeded = ∞
procedure placeQueens():
  if all black pieces are under attack:
    minQueensNeeded = min(minQueensNeeded, number of queens on the board)
  else:
    for each black piece B that is not under attack:
      for each square S from which B can be captured:
        place a queen at S
        placeQueens()
        remove the queen at S

Обратите внимание, что он будет посещать одну и ту же ситуацию более одного раза, потому что королевы могут быть расположены в произвольном порядке. Это не влияет на ответ, но не очень хорошо для производительности. Вы можете исправить это, только поместив новые королевы в квадраты, которые следуют за последней королевой в порядке чтения.

...