n-Queen

バックトラックアルゴリズムを書いたことないなあ、と思い、
n-Queen問題に、C言語で挑戦してみた。

方針はわかるのだけれど、
変数の変更の様子を追うのがしんどくてしんどくて.....
挫折した。
こんなことではダメなので、もっとちゃんと考えてから再挑戦しよう。

しかし、折角取り組み始めた問題を途中で投げ出すのは
とても気持ち悪い。

そんなときは。
Haskellですね。
permutationsを使っているので、非常に効率は悪いです。
とりあえず、n == 10程度まではすぐに答えを出せる。

import Data.List

main = getLine >>= \n -> print.nQueen $ [1..(read n)]

nQueen :: [Int] -> [Int]
nQueen = head.filter notTaken . permutations

notTaken :: [Int] -> Bool
notTaken ls = notSlanting ls' && notStraight ls
  where
    ls' = zip ls [1..]

notSlanting :: [(Int,Int)] -> 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' ls
  where
    length' = length.group.sort

permutations使わずに、
モナド使って書き直してみようか