はわわーっ

はわわわわっ

Haskell で n-queens problem

やってみた。

とりあえず、最初に書いてみたのがこれ。全パターンを抜き出してからフィルターするやつ。

import Control.Monad (replicateM)

queens :: Int -> [[Int]]
queens n = [qs | qs <- replicateM n [1..n], test qs]
  where
    test qs = not (hasSameElem qs || hasSameElem diag || hasSameElem diag')
      where
        hasSameElem [] = False
        hasSameElem (q:qt) = q `elem` qt || hasSameElem qt
        diag  = zipWith (+) [1..] qs
        diag' = zipWith (-) [1..] qs

予想はしてたけど、ものすごく遅い。

次に書いてみたのがこれ。

queens :: Int -> [[Int]]
queens n = queensAux n
  where
    queensAux 0 = [[]]
    queensAux i = [q:qs | q <- [1..n], qs <- queensAux (i-1), test q qs]
      where
        test q qs = not (q `elem` qs || isSameDiag q qs)
        isSameDiag q qs = any (\(x, y) -> abs (q - y) == x) $ zip [1..] qs

これも遅い。

で、最終的にこうなった。

queens :: Int -> [[Int]]
queens n = queensAux n
  where
    queensAux 0 = [[]]
    queensAux i = [q:qs | qs <- queensAux (i-1),
                          q  <- filter (test qs) [1..n]]
    test qs q = not (q `elem` qs) &&
                (all (\(x, y) -> abs (q - y) /= x) $ zip [1..] qs)

これだと上のやつより速い。

参考