「prolog勉強21日目 平面蛙とびパズルの解」の編集履歴(バックアップ)一覧に戻る

prolog勉強21日目 平面蛙とびパズルの解 - (2013/06/18 (火) 12:33:01) のソース

http://www.geocities.jp/m_hiroi/puzzle/kaeru.html#chap3

平面蛙とびパズルの最短手順をPrologで幅優先探索で求めて表示するプログラムの勉強。
もちろんパズルが解けるようになることが目標なのではない。
今のところパズルを通して色々な実装を試すことが目標である。
今回は事実の定義を短くできる処理系を目指して書いてみた。
なにやら複雑なことになってしまって失敗だったかもしれない。
盤面にa~qまでの番号を割り、
 [[a,w],[b,s],,,[q,w]].のようにどのマス目がどの石か隙間かを2つ目の変数に追加してリストとして表現した。
これによって事実は短くなったが、コードが品雑になってしまった。
しかしこれは良い失敗だと思う。
データをどう定義すればコード量がどれだけ変化するか。
それが実感としてわかったので私としては成功だと思う。
Prologでプログラムを書いてるとなにやら学術的な記述を書いてるような気分になるのは不思議である。
学問とは全く関係のないわが身にそういう感覚を抱かせる。
Prologとはなかなか面白い言語だと思う。

ただ幅優先探索の効率的なやり方がよくわからない。
C++なら瞬きする間に終わる処理がいつまでたっても終わらないのには少し辟易するところもある。
何かちゃんとした方法をとれば早くなるのだろうか?
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).