SICPにもある問題。Scheme(Gauche)で解くとこんな感じか。
(use srfi-1)
(define (safe-pieces? x1 y1 x2 y2)
(not (or (= y1 y2) (= (+ x1 y1) (+ x2 y2)) (= (- x1 y1) (- x2 y2)))))
(define (safe? pieces new-row)
(every (cute safe-pieces? (length pieces) new-row <> <>)
(iota (length pieces)) pieces))
(define (queens m)
(if (= m 0) '(())
(append-map
(lambda (pieces)
(filter-map (lambda (n) (and (safe? pieces n) `(,@pieces ,n))) (iota 8 1)))
(queens (- m 1)))))filter-mapをfilterにしててかなり混乱してしまった。修行が足りん。
ちなみにHaskellで書くとこうだそうだ。というか、これをパクっただけ。
safe p n = and [ not(check (i,j) (m,n)) | (i,j) <- zip[1..length p] p]
where m = length p + 1
check (i,j) (m,n) = (j == n) || (i + j == m + n) || (i - j == m - n)
queens 0 = [[]]
queens (m+1) = [p ++ [n] | p <- queens m, n <- [1..8], safe p n]すごく短い。List Comprehensionの力かな*1。
SchemeでもEager Comprehensionsというのがあるにはあるけど読みにくくなったので今回は普通の手段で対応した。
*1:それだけじゃないけど
