エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

フカシギのPrologな通行止め

オフラインリアルタイムどう書く第四回の参考問題、「フカシギの通行止め」。絶対にPrologはこの問題を解くのに向いているはず…と思いつつも力量が追いつかずにそのままになっていました。


で、Prolog力をもっと身につけようとこちらのPrologのTutorialを読んでいたところ。ありました。答えそのものがありました。


あとはグラフを4x4のマスになるようにすればフカシギの数え方になります。


では。通行止めはどう表現すればよいか?
答え。定義そのものを削除すればよい。


neighbor(a, b)でノードaとノードbが隣接していることを事実として定義していますが、retract(neighbor(a, b))とすることで定義そのものを削除することがPrologではできてしまいます。


ちなみに。連続して問題を解きたかったので、一旦retract(neighbor(a, b))で通行止めにした経路=削除した定義をassert(neighbor(a, b))で再定義しています。


以下、コード。neighbornextdepth_searchの定義は上記のTutorialほぼそのままです。
neighborを動的に変更できるように1行目でdynamicの指定をしています。

:- dynamic neighbor/2.

neighbor(a, b). neighbor(b, c). neighbor(c, d). neighbor(d, e).
neighbor(f, g). neighbor(g, h). neighbor(h, i). neighbor(i, j).
neighbor(k, l). neighbor(l, m). neighbor(m, n). neighbor(n, o).
neighbor(p, q). neighbor(q, r). neighbor(r, s). neighbor(s, t).
neighbor(u, v). neighbor(v, w). neighbor(w, x). neighbor(x, y).

neighbor(a, f). neighbor(b, g). neighbor(c, h). neighbor(d, i). neighbor(e, j).
neighbor(f, k). neighbor(g, l). neighbor(h, m). neighbor(i, n). neighbor(j, o).
neighbor(k, p). neighbor(l, q). neighbor(m, r). neighbor(n, s). neighbor(o, t).
neighbor(p, u). neighbor(q, v). neighbor(r, w). neighbor(s, x). neighbor(t, y).

next(X, Y) :- neighbor(X, Y).
next(X, Y) :- neighbor(Y, X).

depth_search(End,  End, Path, Ans) :-
    reverse([ End | Path ], Ans), !.

depth_search(Node, End, Path, Ans) :-
    not(member(Node, Path)),
    next(Node, Next),
    depth_search(Next, End, [ Node | Path ], Ans).

block([]).
block([ [X, Y] | Bs]) :- retract(neighbor(X, Y)), block(Bs).

permit([]).
permit([ [X, Y] | Bs]) :- assert(neighbor(X, Y)), permit(Bs).

solve(Start, End) :-
    read(Blocked),      % 通行止めの箇所を読み込む
    block(Blocked),     % 通行止めする
    findall(Path, depth_search(Start, End, [], Path), Paths), % 経路を全検索
    length(Paths, Ans), % 経路の個数の取得
    writeln(Ans),       % 経路の個数の表示
    permit(Blocked),    % 通行止めを解除する
    solve(Start, End).  % 次の問題を解く


テストパタン。文字列からパタンを読み込む根性がなかったので、最初からPrologで扱いやすい形式にしてます。

[ ].
[ [a,f] ].
[ [x,y] ].
[ [p,q], [q,r], [r,s], [s,t], [d,i], [i,n], [n,s], [s,x] ].
[ [a,f], [p,q], [q,r], [r,s], [s,t], [d,i], [i,n], [n,s], [s,x] ].
[ [b,g], [c,h], [d,i], [i,j], [n,o], [s,t] ].
[ [b,c], [a,f], [c,h], [d,i], [n,o], [k,p], [m,r], [n,s], [o,t], [p,u], [r,s] ].
[ [a,b], [a,f] ].
[ [t,y], [x,y] ].
[ [b,g], [c,h], [e,j], [g,h], [l,m], [l,q], [m,r], [o,t], [r,s], [s,x] ].
[ [t,y], [c,h], [h,i], [m,n], [k,p], [m,r], [r,s], [s,x] ].
[ [x,y], [c,h], [h,i], [m,n], [k,p], [m,r], [r,s], [s,x] ].
[ [c,h], [h,i], [m,n], [k,p], [m,r], [r,s], [s,x] ].
[ [a,b], [c,d], [u,v], [w,x] ].
[ [g,h], [m,n], [s,t], [l,q], [q,r] ].
[ [f,g], [g,l], [l,m], [m,r], [r,s] ].


実行。ノードaからノードyまでの経路を全検索して経路の個数を表示しています。

$ swipl -s fukashigi.pl -g "solve(a,y)" -t halt < testpattern.txt
: 8512
4256 4256 184 92 185 16 0 0 11 18 32 50 621 685 171