読者です 読者をやめる 読者になる 読者になる

N-Queen(1)

common lisp algorithm

N-Queen問題を、いくつかの方法で解いてみる。

とりあえず、一番簡単・簡潔だと思うのは、次のコード。
参照: nlet-acc

;; row番目に新たなqueenを置けるかチェック
(defun check (row queens &optional (r 1))
  (or (null queens) 
      (and (/= (car queens) row (+ row r) (- row r)) 
	   (check row (cdr queens) (1+ r)))))

(defun n-queen (n)
  (nlet-acc self (queens (col n))
    (if (zerop col)
        (accumulate queens) 
      (dotimes (row n)
        (when (check row queens)
          (self (cons row queens) (1- col)))))))