« Haskell の配列 | トップページ | Codeforces 35 »

2012年1月 4日 (水)

n Queen 問題

 先日、Haskell で「N-Queens 問題」を扱ったブログを見つけました。
 そういえば「N-Queens 問題」を自分で解いたことがなかったなぁ…ということで、自分でもコードを書いてみました。

import System
import Data.List

queen :: Int -> [[Int]]
queen n = loop n [([], [1 .. n])]
    where
      loop 0 xs = [x | (x, _) <- xs]
      loop n xs = loop (n - 1) $ concatMap addLine xs

-- 斜めに重複しない行を付け加える
addLine :: ([Int], [Int]) -> [([Int], [Int])]
addLine (xs, ys) = [(y : xs, delete y ys) | y <- ys, check y 1 xs]

-- 斜めの重複の判定する
check :: Int -> Int -> [Int] -> Bool
check y d (x : xs)
    | y - d == x || y + d == x = False
    | otherwise = check y (d + 1) xs
check _ _ _ = True


main :: IO ()
main = do n <- getArgs
          print $ length $ queen (read $ head n)

 クイーンの配置は「その行の左から何列目にクイーンがあるか」を整数で表わすことにしました。
 例えば

 ---------------
| Q |   |   |   |
|---+---+---+---|
|   | Q |   |   |
|---+---+---+---|
|   |   | Q |   |
|---+---+---+---|
|   |   |   | Q |
 ---------------

という配置は [1,2,3,4] というリストで表わされます。
 このようなデータ構造を使うと、n × n の盤面の場合 [1 .. n] の順列を考えれば縦と横の重複を調べる必要がありません。

 こちらこちらのコードと比べて処理時間が速かったので、自分では満足してたのですが、「ビット演算を使うともう少し速くなる」といったブログの記事を散見したので、時間があれば改良してみようかと思っています。

Date: 2012-01-04 11:45:13 JST

HTML generated by org-mode 6.33x in emacs 23

« Haskell の配列 | トップページ | Codeforces 35 »

Haskell」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/53651085

この記事へのトラックバック一覧です: n Queen 問題:

« Haskell の配列 | トップページ | Codeforces 35 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ