n-Queen(2)

permutationsを使わずに、昨日書いたn-Queenを書き直してみた。

全列挙ではないので、少しだけ速度が改善された。
しかし、まだまだ改善の余地あり。

import Data.List

type Pos = Int
main = getLine >>= print.nQueen.read

nQueen :: Int -> [Pos]
nQueen n = backtrack n []

--駒が他のクイーンにとられない
notTaken ::[Pos] -> Bool
notTaken [_] = True
notTaken ls = notSlanting (zip ls [1..]) && notStraight ls

--斜め方向に被りがない
notSlanting :: [(Pos,Pos)] -> Bool
notSlanting [_] = True
notSlanting (l:ls)
 = all (==True) (map (f l) ls) && notSlanting ls
  where
    f a b = abs (fst a - fst b) /= abs(snd a - snd b)
--縦方向に被りがない
notStraight :: [Int] -> Bool
notStraight ls = length ls == (length.group.sort) ls

backtrack :: Int -> [Pos] -> [Pos]
backtrack n ls
 |length ls == n = ls
 |otherwise = take n.concat.map (backtrack n) $ list
  where
    list = filter notTaken $ map (:ls) [1..n]

backtrackと言う関数を作っているけれど、
正確にはバックトラックじゃない。
対象となる列で、
駒を置くことが許される組み合わせをリストにし、
その各要素に同様の処置を施している。

これで、昨晩よりは速度があがり、
n = 10
も、すぐに答えを導き出せる。
n = 20
では、時間は1,2分要した。
実行結果

$ ./nQueen
10
[7,4,2,9,5,10,8,6,3,1]
$ ./nQueen
20
[11,6,14,7,10,8,19,16,9,17,20,18,12,15,13,4,2,5,3,1]

さて、ここからどのように速度をあげていくか....