スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

エイト・クイーン問題を解くHaskellプログラムの例 (1)

チェスにおいて、クイーンの駒は縦・横・斜めの 8 方向に任意のマスの数だけ動かすことができます。エイト・クイーン問題とは、8×8 マスの盤上に 8 個のクイーンを互いに他の駒に取られないように配置せよ、という問題です。解は全部で 92 個あり、回転と鏡映の操作で一致するものを同一視すると 12 個であることが知られています。

プログラム例

import Monad

main = 
  let queens = searchSolutions 8 in 
  do mapM_ (print.reverse) $ queens
     print $ length $ queens

searchSolutions :: Int -> [[Int]]
searchSolutions n = foldM placeQueen [] [1 .. n]
  where
    -- 行ごとにクイーンを置く
    placeQueen :: [Int] -> Int -> [[Int]]
    placeQueen js _ = map (:js) $ filter (check js 1) [1 .. n]

-- 他のクイーンの射程にあるかどうか
check :: [Int] -> Int -> Int -> Bool
check [] _ _ = True
check (j:js) k x =
  x /= j     &&  -- 縦
  x /= j - k &&  -- 斜め(左下)
  x /= j + k &&  -- 斜め(右下)
  check js (k + 1) x

クイーンの射程をチェックする際、本来なら縦・横・斜めのチェックが必要ですが、行ごとに駒を置いているので、横方向は省略できます。また、ある行に新しいクイーンを置くにあたって、リスト js の k 番目の要素を j とすると、k 行前のクイーンは j 列目に置かれているため、j-k, j, j+k 列目が射程となって置けない場所になります。

実行結果:

[1,5,8,6,3,7,2,4]
[1,6,8,3,7,4,2,5]
[1,7,4,6,8,2,5,3]
[1,7,5,8,2,4,6,3]
[2,4,6,8,3,1,7,5]
...
...
[7,5,3,1,6,8,2,4]
[8,2,4,1,7,5,3,6]
[8,2,5,3,1,7,4,6]
[8,3,1,6,2,5,7,4]
[8,4,1,3,6,2,7,5]
92

各リストについて、左から i 番目の要素 j が、i 行 j 列のところにクイーンを置くことを表しています。

【theme : プログラミング
【genre : コンピュータ

プロフィール

よしいず

Author:よしいず
MATHEMATICS.PDFというウェブサイトを運営しています。

管理の都合上、トラックバックとコメントはオフにしてあります。ブログ経験者なら分かっていただけると思いますが、スパム(アダルトやその他の宣伝)ばかりなのが現実です。

リンクは自由です。当サイトの記事に対する間違いの指摘・意見・感想などを述べた記事からのリンクは歓迎です。ただし、ブログ記事アップ直後はミスが多く、頻繁に修正します。場合によっては削除する可能性もあります。その際、何も断りもなく修正・削除しますがご了承ください。内容を参考にする場合には投稿後一週間ほど様子を見てからにしてください(笑)。

記事の間違いを指摘するときは、その具体的箇所、理由(仕様に反するなど)・根拠(参考にした文献など)、代替案(同じ結果を得るための正しいやり方)も教えてください。そうしないと、(指摘される側および第三者はその時点では無知の状態なので、)どこが間違いなのか分かりませんし、本当に間違っているのかどうかが判断・検証できません。実際、間違いだと指摘されたことが結局は正しかったというケースもありますので。

このブログのタイトル一覧

リンク
月別アーカイブ
カテゴリ
最新記事
検索フォーム
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。