N-Queen (Haskell + Common Lisp)

common lisp algorithm speed haskell

Etsukata blog: Haskellでlist monadを使ってN-Queens問題を解いてみました を見たのをきっかけに久しぶりにN-Queen問題を解くプログラムをHaskellで書いてみた。

---- ファイル名: nqueen.hs
---- コンパイル: ghc -O2 -o nqueen nqueen.hs  # Glasgow Haskell Compiler, Version 7.0.3

import System

-- クイーンの配置: リスト内のオフセットが列を、値が行を表す
type Queens = [Int]

-- N-Queenを解く: ボードのサイズを受け取り、全ての解答(可能な配置のリスト)を返す
nQueens :: Int -> [Queens]
nQueens n = solve n []
  where solve 0   queens = [queens]   -- 最後の列: 全てのクイーンを配置できた
        solve col queens =            -- 途中の列: 全ての行に対して配置可能かを調べ、可能なら次の列に進む
          concat $ map (solve (col-1) . (:queens)) $ filter (check queens 1) [0..(n-1)]

-- クイーンが配置可能かどうか調べる
check :: Queens -> Int -> Int -> Bool  
check [] _ _  = True
check (q:qs) r row    -- rは対角線上の(チェックすべき)クイーンの位置を知るための変数
  | q /= row && q /= row+r && q /= row-r = check qs (r+1) row
  | otherwise = False
  
-- メイン関数
main = do
  args <- getArgs
  let size = (read $ head args)::Int
  let rlt = nQueens size
  putStrLn $ show . length $ rlt

実行結果:

$ ./nqueen 12
14200

処理時間

冒頭で挙げた記事のもの(Etsutaka)、および、Common Lisp版(後述)との処理速度の比較。

　 処理時間(サイズ=11) 処理時間(サイズ=12) 処理時間(サイズ=13)
nqueen(Haskell:本記事) 0.080秒 0.424秒 2.592秒
nqueen(Haskell:Etsutaka) 0.132秒 0.736秒 4.424秒
nqueen(Common Lisp) 0.071秒 0.375秒 2.289秒

この中ではCommon Lisp版が一番速くなっているけど、Haskellで効率の良いプログラムの書き方とかが全く分かっていないので、その辺を把握してちゃんと書けばHaskell版はもっと速くなるかもしれない。

Common Lisp版

Common Lisp版のソースコード。
内容的には N-Queen(1) - sileの日記 に最適化宣言を加えただけ。

(defvar *fastest* '(optimize (speed 3) (safety 0) (debug 0) (compilation-speed 0)))
(deftype max-board-size () '(mod #x100))

(defun check (row queens &optional (r 1))
  (declare #.*fastest*
           (max-board-size r row))
  (or (null queens) 
      (and (/= (the max-board-size (car queens)) row (+ row r) (- row r)) 
	   (check row (cdr queens) (1+ r)))))

(defun n-queen (n)
  (declare #.*fastest*
           (max-board-size n))
  (nlet-acc self (queens (col n))
    (if (zerop col)
        (accumulate queens) 
      (dotimes (row n)
        (when (check row queens)
          (self (cons row queens) (1- col)))))))

;; SBCL-1.0.51
> (n-queen 4)
--> ((2 0 3 1) (1 3 0 2))

> (time (length (n-queen 12)))
Evaluation took:
  0.401 seconds of real time
  0.400025 seconds of total run time (0.400025 user, 0.000000 system)
  [ Run times consist of 0.012 seconds GC time, and 0.389 seconds non-GC time. ]
  99.75% CPU
  800,068,094 processor cycles
  13,926,400 bytes consed
  
--> 14200