ErlangでN-Queens

コンピュータ

を書いてみた。というか移植した。
N-QueensはチェスのQueen（縦・横・斜めに動ける）をお互いに取り合わないように盤面に置くパズル。本来の盤面は8x8ですが。
あまりに典型的なので、探せば絶対あると思うんだけど、まぁいいや、ということで。
Flengで昔使っていたのをベースにしました。

-module(qu).
-export([qu/1, go/1, count/1]).

go(N) -> timer:tc(qu,count,[qu(N)]).

count(C) -> count(C,0).
count([_H|T],Crnt) -> count(T,Crnt+1);
count([],Crnt) -> Crnt.

append([A|X],Y) -> [A|append(X,Y)];
append([],Y) -> Y.

qu(N) -> qu(generate(N), [],[]).

generate(N) ->
        if N > 0 -> [N|generate(N - 1)];
           N == 0 -> []
        end.

qu([P|Lu],Ls,Lp) -> 
        Lr = append(Lu,Ls),
        Ans1 = check(P,1,Lr,Lp,Lp),
        Ans2 = qu(Lu,[P|Ls],Lp),
        append(Ans1, Ans2);
qu([],[_|_],_) -> [];
qu([],[],Lp) -> [Lp].

check(P,D,L,[Q|Lp0],Lp) ->
        if (Q + D == P) or (Q - D == P) -> [];
           true -> D1 = D + 1, check(P,D1,L,Lp0,Lp)
	end;
check(P,_,L,[],Lp) -> qu(L,[],[P|Lp]).

# なぜ動くのかは聞かないで(^^; 

1> c(qu).
{ok,qu}
2> qu:go(13).
{1122,73712}

サイズ13の時、置き方は73712種類あって、計算に11.22秒かかっています。

ちなみに、KL1移植版をKLICで実行すると、5〜6秒くらい。KLICはa.outになることを考えると、Erlangはそこそこ速いですね。KLICについてくるqueenの実装はもうちょっと速くて1台で4.5秒、pvmを使った2台で2.8秒、とかでした。

Erlang版を並列化するのは挫折 orz