QueensパズルをElixirで -Elixir見習いの実習-

#はじめに
Elixirに習熟するために基本的なコードを書いています。Nqueens、女王問題に取り組みました。

#女王問題とは
チェスのqueenは縦、横、斜めに駒を進めて相手の駒を取りことができます。8Queensであれば8×8の盤面で8個のqueenの駒を互いに利き筋にならないように配置するというパズルです。

例えば次のような配置は解のうちの１つです。

（出典　wikipedia）

#方策
効率のことはとりあえず考えないで、素朴かつ関数プログラミング的な発想で取り組みました。queenの位置をリストで表します。　[1,2,3,4,5,6,7,8] というリストは図の(a,1)(b,2)(c,3)... にqueenがある配置だと考えることにします。８つの数字が全部異なるのであれば縦横方向への利き筋はきいてないと考えることができます。そうすると斜めに効いてるかどうかを調べればいいはずです。１の隣に２がある場合には利き筋ですからこれは答えにはなっていません。

まずは1..8の順列を生成することを考えます。その順列の中には答えの配置の順列もあるはずです。これをfilterで篩にかけて答えを探すという方法で考えていきます。

#順列の生成
いくつか方法があることが知られています。今回はM.Hiroiさんのページで解説されていたバックトラック法によることにしました。
M.Hiroiさんの解説ページ

解説のページではSchemeでコードが示されています。これはほぼElixirに直訳可能です。再帰を巧みに使っています。foldrはElixirのEnumモジュールにありますので、これを使いました。コードは次のようです。

　def perm_list(ls) do
    perm_list1(ls,[],[])
  end

  def perm_list1([],a,b) do [Enum.reverse(a)|b] end
  def perm_list1(ls,a,b) do
    List.foldr(ls,
              b,
              fn(x,y) -> perm_list1(ls--[x],[x|a],y) end)
  end

これを使うとリストの順列を求めることができます。

iex(14)> P.perm_list([1,2,3])
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
iex(15)>

#利き筋のチェック
縦横方向には効いてないことは明らかですから、斜め方向にぶつかるqueenが置いてないかを調べる関数safe/1を考えます。

まずリストの先頭要素を取り出します。これが2番目以降のqueenとぶつかっていないかと調べます。先頭のqueensの位置を表す数とそこからの距離nを使えば判定できます。それをリストの先頭から全部について調べます。コードにすると下記のようになります。

  def safe([]) do true end
  def safe([l|ls]) do
    if safe1(ls,l,1) do
      safe(ls)
    else
      false
    end
  end

  def safe1([],_,_) do true end
  def safe1([l|ls],a,n) do
    if a+n == l || a-n == l do
      false
    else
      safe1(ls,a,n+1)
    end
  end
  

safe/1がメインです。先頭と残りと位置番号を下請け関数のsafe1/3に渡します。リストが空になるまで再帰により調べて判定を下します。空リストまでたどり着けばセーフ、trueです。

#仕上げ
ここまで部品が揃えばあとは簡単です。

1..8までの順列リストを生成します。
それをパイプ演算子でsafeかどうかでふるい落とすfilterに回します。
これだけです。

  def queens(n) do
    Enum.to_list(1..n)
    |> perm_list
    |> Enum.filter(fn(x) -> safe(x) end)
  end

実行すると92個の答えのリストがでてくるはずです。

iex(12)> P.queens(8)
[
  [1, 5, 8, 6, 3, 7, 2, 4],
  [1, 6, 8, 3, 7, 4, 2, 5],
  ...
  [5, ...],
  [...],
  ...
]

lengthで確認してみます。

iex(13)> length(P.queens(8))
92

どうやら、うまくできたようです。

#効率の問題
この方法では無駄な点が多くあり、実行速度は遅いのです。順列の中のsafeではない順列もすべて生成してからfilterにかけて除去しているからです。順列生成段階で明らかに解にならないものを生成しなければもっと効率よくなります。

詳しいことはM.Hiroiさんの解説やMITの教科書のSICPに解説があります。

#全コード

defmodule P do
  def queens(n) do
    Enum.to_list(1..n)
    |> perm_list
    |> Enum.filter(fn(x) -> safe(x) end)
  end

  def perm_list(ls) do
    perm_list1(ls,[],[])
  end

  def perm_list1([],a,b) do [Enum.reverse(a)|b] end
  def perm_list1(ls,a,b) do
    List.foldr(ls,
              b,
              fn(x,y) -> perm_list1(ls--[x],[x|a],y) end)
  end

  def safe([]) do true end
  def safe([l|ls]) do
    if safe1(ls,l,1) do
      safe(ls)
    else
      false
    end
  end

  def safe1([],_,_) do true end
  def safe1([l|ls],a,n) do
    if a+n == l || a-n == l do
      false
    else
      safe1(ls,a,n+1)
    end
  end
  
#使われていない。おまけ
  def perm([],a) do :io.write(Enum.reverse(a)) end
  def perm(ls,a) do
    Enum.each(ls,fn(n) ->
                  perm(ls--[n],[n|a]) end)
  end
end

#参考文献
N queens problem M.Hiroi