Задача о восьми ферзях

Рис. 2.8. Решение задачи о восьми ферзях.

В «задаче о восьми ферзях» спрашивается, как расставить на шахматной доске восемь ферзей так, чтобы ни один из них не бил другого (то есть никакие два ферзя не должны находиться на одной вертикали, горизонтали или диагонали). Одно из возможных решений показано на рисунке 2.8. Один из способов решать эту задачу состоит в том, чтобы идти поперек доски, устанавливая по ферзю в каждой вертикали. После того, как k − 1 ферзя мы уже разместили, нужно разместить k -го в таком месте, где он не бьет ни одного из тех, которые уже находятся на доске. Этот подход можно сформулировать рекурсивно: предположим, что мы уже породили последовательность из всех возможных способов разместить k − 1 ферзей на первых k − 1 вертикалях доски. Для каждого из этих способов мы порождаем расширенный набор позиций, добавляя ферзя на каждую горизонталь k -й вертикали. Затем эти позиции нужно отфильтровать, оставляя только те, где ферзь на k -й вертикали не бьется ни одним из остальных. Продолжая этот процесс, мы породим не просто одно решение, а все решения этой задачи.

Это решение мы реализуем в процедуре queens , которая возвращает последовательность решений задачи размещения n ферзей на доске n × n . В процедуре queens есть внутренняя процедура queen-cols , которая возвращает последовательность всех способов разместить ферзей на первых k вертикалях доски.

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position new-row k rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

В этой процедуре rest-of-queens есть способ размещения k − 1 ферзя на первых k − 1 вертикалях, а new-row — это горизонталь, на которую предлагается поместить ферзя с k -й вертикали. Завершите эту программу, реализовав представление множеств позиций ферзей на доске, включая процедуру adjoin-position , которая добавляет нового ферзя на определенных горизонтали и вертикали к заданному множеству позиций, и empty-board , которая представляет пустое множество позиций. Еще нужно написать процедуру safe? , которая для множества позиций определяет, находится ли ферзь с k -й вертикали в безопасности от остальных. (Заметим, что нам требуется проверять только то, находится ли в безопасности новый ферзь — для остальных ферзей безопасность друг от друга уже гарантирована.)

---