平面蛙とびパズルの最短手順をＰｒｏｌｏｇで幅優先探索で求めて表示するプログラムの勉強。
もちろんパズルが解けるようになることが目標なのではない。
今のところパズルを通して色々な実装を試すことが目標である。
今回は事実の定義を短くできる処理系を目指して書いてみた。
なにやら複雑なことになってしまって失敗だったかもしれない。
盤面にa～ｑまでの番号を割り、
[[a,w],[b,s],,,[q,w]].のようにどのマス目がどの石か隙間かを２つ目の変数に追加してリストとして表現した。
これによって事実は短くなったが、コードが品雑になってしまった。
しかしこれは良い失敗だと思う。
データをどう定義すればコード量がどれだけ変化するか。
それが実感としてわかったので私としては成功だと思う。
Ｐｒｏｌｏｇでプログラムを書いてるとなにやら学術的な記述を書いてるような気分になるのは不思議である。
学問とは全く関係のないわが身にそういう感覚を抱かせる。
Ｐｒｏｌｏｇとはなかなか面白い言語だと思う。
ただ幅優先探索の効率的なやり方がよくわからない。
Ｃ++なら瞬きする間に終わる処理がいつまでたっても終わらないのには少し辟易するところもある。
何かちゃんとした方法をとれば早くなるのだろうか？
assertをやめてキューを使うとか？
%abc
%def
%ghijk
%__lmn
%__opq
cell_rev(a,q).
cell_rev(b,p).
cell_rev(c,o).
cell_rev(d,n).
cell_rev(e,m).
cell_rev(f,l).
cell_rev(g,k).
cell_rev(h,j).
cell_rev(i,i).
cell_rev_a(A,B):-cell_rev(A,B),A\==B.
cell_rev_a(A,B):-cell_rev(B,A).
move_table1(a,b).
move_table1(b,c).
move_table1(d,e).
move_table1(e,f).
move_table1(g,h).
move_table1(h,i).
move_table1(i,j).
move_table1(j,k).
move_table1(l,m).
move_table1(m,n).
move_table1(o,p).
move_table1(p,q).
move_table2(a,d).
move_table2(d,g).
move_table2(b,e).
move_table2(e,h).
move_table2(c,f).
move_table2(f,i).
move_table2(i,l).
move_table2(l,o).
move_table2(j,m).
move_table2(m,p).
move_table2(k,n).
move_table2(n,q).
moves(A,B):-move_table1(A,B).
moves(A,B):-move_table2(A,B).
moves(A,B,C):-move_table1(A,B),move_table1(B,C).
moves(A,B,C):-move_table2(A,B),move_table2(B,C).
move_exe([From,b],[To,s],[From,s],[To,b]).
move_exe([From,s],[To,w],[From,w],[To,s]).
move_exe([From,b],[In,w],[To,s],[From,s],[In,w],[To,b]).
move_exe([From,s],[In,b],[To,w],[From,w],[In,b],[To,s]).
path_print([]):-!.
path_print(State):-state_chain(OldState,State),path_print(OldState),one_print(State).
one_print([[_,A],[_,B],[_,C],[_,D],[_,E],[_,F],[_,G],[_,H],[_,I],
[_,J],[_,K],[_,L],[_,M],[_,N],[_,O],[_,P],[_,Q]]):-
nl,
write([A,B,C]),nl,
write([D,E,F]),nl,
write([G,H,I,J,K]),nl,
write([-,-,L,M,N]),nl,
write([-,-,O,P,Q]), nl.
change(w,b).
change(b,w).
change(s,s).
state_reverse([],[]):-!.
state_reverse([[Cell1,C1]|Rest],[[Cell2,C1]|Result]):-cell_rev_a(Cell1,Cell2),state_reverse(Rest,Result).
state_reverse_a(State,Result):-!,state_reverse(State,Rev1),sort(Rev1,Result).
one_move(_,State):-
state_rev_list(State),
state_chain(Last,[]),
!,write(ok),path_print(Last).
one_move(P,State):-
moves(From,To),
select([From,C1],State,Rest1),
select([To,C2],Rest1,Rest2),
move_exe([From,C1],[To,C2],Re1,Re2),
Temp=[Re1,Re2 | Rest2],
sort(Temp,NextState),
assert_state_a(P,State,NextState).
one_move(P,State):-
moves(From,In,To),
select([From,C1],State,Rest1),
select([In,C2],Rest1,Rest2),
select([To,C3],Rest2,Rest3),
move_exe([From,C1],[In,C2],[To,C3],Re1,Re2,Re3),
Temp=[Re1,Re2,Re3|Rest3],
sort(Temp,NextState),
assert_state_a(P,State,NextState).
assert_state_a(P,State,NextState):-
not(state_chain(_,NextState)),
assert(state_chain(State,NextState)),
assert(state_list(P,NextState)),
state_reverse_a(NextState,RevStateOld),
state_reverse_a(State,RevStateNext),
assert(state_chain(RevStateOld,RevStateNext)),
assert(state_rev_list(RevStateOld)),fail.
next_search(P):-
P1 is P+1,
write(P),
findall(State,state_list(P,State),List),length(List,Len),write(Len),nl,
!,state_list(P,State),
one_move(P1,State).
main:-State=[[a,b],[b,b],[c,b],[d,b],[e,b],[f,b],[g,b],[h,b],[i,s],
[j,w],[k,w],[l,w],[m,w],[n,w],[o,w],[p,w],[q,w]],
state_reverse_a(State,RevState),
write(RevState),
assert(state_list(0,State)),
assert(state_chain([],State)),
assert(state_rev_list(State)),
retractall(state_list(_,_)),
retractall(state_chain(_,_)),
retractall(state_rev_list(_)),
assert(state_chain([],State)),
assert(state_list(0,State)),
assert(state_rev_list(RevState)),
assert(state_chain(RevState,[])),
between(0,25,P),next_search(P).
最終更新：2013年06月18日 12:33
