Это не самая быстрая реализация схемы, но она довольно лаконична. Я придумал это самостоятельно, но сомневаюсь, что это уникально. Он находится в схеме PLT, поэтому некоторые имена функций необходимо изменить, чтобы запустить его в R6RS. Список решений и каждое решение построены с минусами, поэтому они поменялись местами. Реверс и карты в конце переупорядочивают все и добавляют строки к решениям для приятного вывода. Большинство языков имеют функцию сгиба, см .:
http://en.wikipedia.org/wiki/Fold_%28higher-order_function%29
#lang scheme/base
(define (N-Queens N)
(define (attacks? delta-row column solution)
(and (not (null? solution))
(or (= delta-row (abs (- column (car solution))))
(attacks? (add1 delta-row) column (cdr solution)))))
(define (next-queen safe-columns solution solutions)
(if (null? safe-columns)
(cons solution solutions)
(let move-queen ((columns safe-columns) (new-solutions solutions))
(if (null? columns) new-solutions
(move-queen
(cdr columns)
(if (attacks? 1 (car columns) solution) new-solutions
(next-queen (remq (car columns) safe-columns)
(cons (car columns) solution)
new-solutions)))))))
(unless (exact-positive-integer? N)
(raise-type-error 'N-Queens "exact-positive-integer" N))
(let ((rows (build-list N (λ (row) (add1 row)))))
(reverse (map (λ (columns) (map cons rows (reverse columns)))
(next-queen (build-list N (λ (i) (add1 i))) null null)))))
Если вы думаете о проблеме, список действительно является естественной структурой данных для этой проблемы. Поскольку в каждой строке может быть размещен только один ферзь, все, что нужно сделать, - это передать список безопасных или неиспользуемых столбцов итератору для следующей строки. Это делается с помощью вызова remq в предложении cond, которое выполняет возвратный вызов next-queen.
Функция foldl может быть переписана как именованное let:
(define (next-queen safe-columns solution solutions)
(if (null? safe-columns)
(cons solution solutions)
(let move-queen ((columns safe-columns) (new-solutions solutions))
(if (null? columns) new-solutions
(move-queen
Это значительно быстрее, поскольку позволяет избежать затрат на проверку аргументов, встроенных в foldl. Я натолкнулся на идею использования неявных строк, глядя на эталонный тест PLT Scheme N-Queens. Начиная с дельта-строки, равной единице, и увеличивая ее при проверке решения, довольно удобно. По какой-то причине abs является дорогим в схеме PLT, поэтому существует более быстрая форма для атак?
В PLT-схеме вы должны использовать изменяемый тип списка для самой быстрой реализации. Тест, учитывающий количество решений без их возврата, может быть записан без создания каких-либо консолидированных ячеек, кроме исходного списка столбцов. Это позволяет избежать сбора мусора до N = 17, когда в gc было потрачено 618 миллисекунд, в то время как программа потратила 1 час 51 минуту на поиск 95 815 104 решений.