2009年10月20日火曜日

N Queen

CommonLispでN Queenを解く。きっと正しいと信じたい。

(defun check-nqueen (n lst)
(not
(or
(find n lst)
(loop
:named hoge
:for i from (1+ n)
:for j downfrom (1- n)
:for rest = lst then (cdr rest)
:for m = (car rest) then (car rest)
:finally (return-from hoge nil)
:while m
:do (when (or (= m i) (= m j))
(return-from hoge t))))))
(defun nqueen (n)
(let ((result nil))
(labels
((inner (i lst r)
(when (check-nqueen i lst)
(if (= r 1)
(push (cons i lst) result)
(loop
:with next = (cons i lst)
:for i from 1 to n
:do (inner i next (1- r)))))))
(loop
:for i from 1 to n
:do (inner i nil n)))
result))

0 件のコメント:

コメントを投稿