Восьми ферзях


queens

Рисунок 2.8: решение восьми ферзях. В `восьми ферзях" спрашивает, как разместить восемь ферзей на шахматной доске так что никакая Королева в проверить из любого другие (т. е. никакие два ферзя не находятся в одном ряду, колонке, или диагонали). Один возможное решение показано на рис. 2.8. Один из способов решить головоломки, чтобы работать через борт и, положив королева в каждом столбце. Как только мы разместили к - 1 Квинсе, мы должны поместить его в месте, где она не уже проверил ни ферзей на доска. Можно сформулировать этот подход рекурсивно предположим, что мы имеем уже сформированная последовательность всех возможных способов разместить K - 1 в Королев первые k - 1 столбцов совета. Для каждого из этих способов, создать расширенный набор позиций путем размещения Королева в каждой строке столбца с номером K. Теперь эти фильтра, сохраняя только должности, для которых Королева в колонки KTH является безопасным в отношении другие королевы. Это производит последовательность всех способов расположить к Королев в первых k столбцов. Продолжая этот процесс, мы будем производить не только одним из решений, но все решения головоломка.

Мы реализуем это решение как процедура Квинса, который возвращает последовательность всех решений задачи размещения n ферзей на N× Н шахматную доску. Королев имеет внутреннюю процедура королевы-холодный, возвращающий последовательность всех способов размещения ферзей в первых 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))

В этой процедуре остального-Куинс вариант к - 1 Квинс в первом к - 1 столбцов, а новые-ряд предложенные строки, в которой можно разместить Королева для столбца КТН. Заполните программа по реализации представление для наборов совета позиции, в том числе порядок примыкать-позиция, к которой примыкает новая положение строки и столбца к набору позиции, и с пустыми совет, который представляет пустой набор позиций. Вы также должны написать процедуру безопасно?, определяющий для набора позиции, будь то королева в колонки KTH является безопасным в отношении другие. (Отметим, что нам нужно только проверить будет ли новая королева безопасный -- у другие дамы уже гарантировано безопасным по отношению друг к другу.)

Я нашел эту задачу особенно трудно. Я думаю, у меня есть рабочая ответа, но я уверен, что есть гораздо лучший способ. Мое текущее решение выглядит как эскимо палкой мост держится на изоленте, готова развалиться в любой момент. Я знаю, что это лажа, так что я должен заранее извиниться. Если вы не можете следовать ему, дайте мне знать, и я постараюсь переписать его немного, если это возможно. Сейчас, однако, мне нужно сделать перерыв! Как я могу улучшить мой код?

(define (enumerate-interval i j) (if (= i j) (list j) (cons i (enumerate-interval (+ i 1) j))))
(define (filter f seq) (if (null? seq) null (if (f (car seq)) (cons (car seq) (filter f (cdr seq))) (filter f (cdr seq)))))
(define (flatmap op seq)
  (foldr append null (map op seq)))

(define (queens board-size)
  (define (empty-board) 
    (map (lambda (row)
           (map (lambda (col) 0) 
                (enumerate-interval 1 board-size))) 
         (enumerate-interval 1 board-size)))
  (define (adjoin-position new-row k rest-of-queens)
    (cond ((and (= new-row 1)
                (= k 1)) (cons (cons 1 
                                     (cdar rest-of-queens)) 
                               (cdr rest-of-queens)))
          ((> k 1) (cons (car rest-of-queens)
                         (adjoin-position new-row 
                                          (- k 1) 
                                          (cdr rest-of-queens))))
          (else (let ((adjoined (adjoin-position (- new-row 1) 
                                                 k 
                                                 (cons (cdar rest-of-queens)                 
                                                       (cdr rest-of-queens)))))
                  (cons (cons (caar rest-of-queens) 
                              (car adjoined)) 
                        (cdr adjoined))))))
  (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))

(define col car)
(define row cdr)

(define (indexOf x seq)
  (define (rec i remains)
    (cond ((null? remains) (error "No x found in seq." x seq))
          ((= (car remains) x) i)
          (else (rec (+ i 1) (cdr remains)))))
  (rec 0 seq))

(define (nth n seq)
  (cond ((null? seq) (error "Sequence shorter than n" seq n))
        ((= n 1) (car seq))
        (else (nth (- n 1) (cdr seq)))))

(define (all-true seq) 
  (cond ((null? seq) true)
        ((car seq) (all-true (cdr seq)))
        (else false)))

(define (upto k rows) 
  (if (or (= k 0) 
          (null? rows)) 
      null
      (cons (car rows) (upto (- k 1) (cdr rows)))))

(define (safe? k positions)
  (let ((uptok-positions (upto (- k 1) positions))
        (kth-position (nth k positions)))  
    (define (col-row-coords pos)
      (define (process-row rownum rows)
        (define (process-col colnum row)
          (cond ((null? row) null)
                ((= (car row) 1) (cons rownum colnum))
                (else (process-col (+ colnum 1) (cdr row)))))
        (if (null? rows)
            null
            (cons (process-col 1 (car rows))
                  (process-row (+ rownum 1) (cdr rows)))))
      (process-row 1 pos))
    (let ((col-and-row (filter (lambda (x) (not (null? x))) (col-row-coords uptok-positions)))
          (k-coord (cons k (indexOf 1 kth-position))))
      (define (diagonal? p1 p2)
        (= (abs (- (col p1) (col p2)))
           (abs (- (row p1) (row p2)))))
      (all-true (map (lambda (pos) 
                  (and (not (= (col k-coord)
                               (col pos)))
                       (not (= (row k-coord)
                               (row pos)))
                       (not (diagonal? k-coord pos)))) col-and-row)))))

Редактировать: Спасибо за отзыв! У меня вот новая версия. Я бы признательны за любую обратную связь вы имеете.

(define (enumerate-interval i j) (if (> i j) null (cons i (enumerate-interval (+ i 1) j))))
(define (filter f seq) (if (null? seq) null (if (f (car seq)) (cons (car seq) (filter f (cdr seq))) (filter f (cdr seq)))))
(define (flatmap op seq)
  (foldr append null (map op seq)))

(define (queens board-size)
  (define (empty-board) '())
  (define (adjoin-position new-row k rest-of-queens) 
    (append  rest-of-queens (list (cons new-row k))))

  (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))

(define col car)
(define row cdr)

(define (threatens? q1 q2)
  (define (diagonal? q1 q2)
    (= (abs (- (col q1) (col q2)))
       (abs (- (row q1) (row q2)))))
  (or (= (col q1) (col q2))
      (= (row q1) (row q2))
      (diagonal? q1 q2)))

(define (nth n seq) (if (= n 1) (car seq) (nth (- n 1) (cdr seq))))
(define (except-nth n seq) 
  (cond ((null? seq) '())
        ((= n 1) (cdr seq))
        (else (cons (car seq) (except-nth (- n 1) (cdr seq))))))

(define (safe? k positions)
  (define (rec me threats)
    (or (null? threats)
        (and (not (threatens? me (car threats)))
             (rec me (cdr threats)))))
  (rec (nth k positions) 
    (except-nth k positions)))


1916
6
задан 14 апреля 2011 в 05:04 Источник Поделиться
Комментарии
3 ответа

Как мы ищем подмножество позиций, где каждая колонка занимает ровно один ферзь, мы можем представлять себя NxN доски установки в упрощенном виде - как список из n чисел, каждое в диапазоне от 1 до n, представляющих строки количество принятых Королева в 1-й ... N-й колонны. Пустой доске будет по-прежнему список emplty.

Затем мы можем использовать минусы в качестве соседствуют позиции, и проверить конкретное к-Королев должность с первой королевой установки и перебора оставшихся K-1 ферзей, проверяя, если дельта между позициями равен нулю или количество итераций. С таким подходом в безопасности? даже не потребуется явный к в качестве аргумента - это просто длина должность перешла к безопасности? и используется в виде неявной перебором (цхд позиции):

(define (queens board-size)
(define (queen-cols k)
(if (= k 0)
(list '())
(filter
(lambda (position) (safe? position))
(flatmap
(lambda (rest-of-queens)
(map (lambda (new-row)
(cons new-row rest-of-queens))
(enumerate-interval 1 board-size)))
(queen-cols (- k 1))))))
(define (safe? position)
(safe-iter? (car position) 1 (cdr position)))
(define (safe-iter? fst n rest-position)
(cond ((null? rest-position) true)
((= fst (car rest-position)) false)
((= (abs (- fst (car rest-position))) n) false)
(else (safe-iter? fst (+ n 1) (cdr rest-position)))))
(queen-cols board-size))

3
ответ дан 21 августа 2011 в 02:08 Источник Поделиться

Ну, пустой доски должны быть представлены на пустой список.

  (define (empty-board) '())

Вы можете представлять государственный совет как список пар, которые содержат координаты ферзей. Используя 0..7, как координаты, вы получаете

  (define (adjoin-position x y board) (cons (cons x y) board))

Итак, теперь вы должны иметь возможность проверить, если королева на строке K является безопасным по отношению к другим. Если вы воспользуетесь структура "Королев" процедуры, вы можете сделать это легче (потому что королева вы проверяете на Королева добавлен вчера в правление, так это в начале перечня должностей). Предполагая, что вы не берете на себя такой ярлык, вам нужно сделать две вещи: получить расположение королевы на строке K и затем выполнить арифметики. Вы можете использовать процедуру схема assv для этого, т. е.

  (define (get-queen row board) (assv row board))

Это возвращает пару, или #F, если ничего не найдено.

Вы можете написать процедуру, которая проверяет, если две дамы в (X, Y) и (А, Б) угрожают друг другу:

  (define (threatens? x y a b)
... ;; left as an exercise to the reader
)

После чего процедура (безопасный? доска строк) может быть легко реализован с помощью перебора королева позиций из списка совета (еще одно упражнение).

2
ответ дан 15 апреля 2011 в 04:04 Источник Поделиться

Я не знаю схему, что многое, что я смогу прочитать этот код, но у меня есть идея, как избежать считая повороты и отражения (если вы не реализовать себя)


  1. Место 1-го ферзя на А1 до А4

  2. Королева размещен на колонке H должна иметь число строк превышает число столбцов королевы.

  3. Королева размещен на 1 строку, должны иметь букву столбца больше, чем количество строк королевы.

Возможно, я что-то упускаю

0
ответ дан 14 апреля 2011 в 06:04 Источник Поделиться