オフラインリアルタイムどう書く第四回の参考問題、「フカシギの通行止め」。絶対にPrologはこの問題を解くのに向いているはず…と思いつつも力量が追いつかずにそのままになっていました。
で、Prolog力をもっと身につけようとこちらのPrologのTutorialを読んでいたところ。ありました。答えそのものがありました。
あとはグラフを4x4のマスになるようにすればフカシギの数え方になります。
では。通行止めはどう表現すればよいか?
答え。定義そのものを削除すればよい。
neighbor(a, b)
でノードaとノードbが隣接していることを事実として定義していますが、retract(neighbor(a, b))
とすることで定義そのものを削除することがPrologではできてしまいます。
ちなみに。連続して問題を解きたかったので、一旦retract(neighbor(a, b))
で通行止めにした経路=削除した定義をassert(neighbor(a, b))
で再定義しています。
以下、コード。neighbor
、next
、depth_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 |