エイト・クイーン問題(Wikipedia)をErlangで解いてみました。
工夫した点：
- バックトラッキング方式です。
- 2つのクイーンが同じ行に来ない性質を利用し、1行ごとに1つのクイーンの場所を探しています。
- クイーンがぶつかるかどうかは、これから置こうとしている場所がすでに置かれたクイーンと同じ列にあるか、行の差と列の差が等しい(＝斜めに位置している)かで判断しています。
- 解の総数が合っているかどうか確認するため、カウンターを別プロセスで起動し、解を発見するごとにカウントアップし、処理の最後に値を表示しています。
eq.erl
% solve 8-queens problem.
-module(eq).
-compile(export_all).
solve() ->
register(counter, spawn(fun() -> counter(0) end)),
solve(cols(), []),
counter ! show.
cols() -> [1,2,3,4,5,6,7,8].
solve(_, Queens) when length(Queens) == 8 -> display(Queens);
solve([], _) -> ok;
solve([Col|T], Queens) ->
case not conflict(Col, Queens) of
true -> solve(cols(), [Col | Queens]);
false -> ok
end,
solve(T, Queens).
conflict(Col, Queens) ->
Conflict = fun({N, QCol}) -> Col == QCol orelse abs(Col - QCol) == N end,
lists:any(Conflict, with_idx(Queens)).
with_idx(L) -> lists:zip(lists:seq(1, length(L)), L).
display(Queens) ->
counter ! countup,
Frame = "**********",
io:fwrite("~s~n", [Frame]),
lists:foreach(fun(X) -> io:fwrite("*~s*~n", [make_line(X)]) end, Queens),
io:fwrite("~s~n~n", [Frame]).
make_line(X) -> string:chars($., X - 1) ++ "Q" ++ string:chars($., 8 - X).
counter(N) ->
receive
countup -> counter(N + 1);
show -> io:fwrite("Count: ~w~n", [N])
end.
「c(eq).」「eq:solve().」を実行すると、解を延々と表示します。最後の部分は次のような感じになります。
**********
*....Q...*
*......Q.*
*.Q......*
*.....Q..*
*..Q.....*
*Q.......*
*...Q....*
*.......Q*
**********
Count: 92
92と表示されます。Wikipediaによると解の総数は92個とのことですので、合っているようです。