※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「prolog勉強18日目 六望星のフィリップイットスターを解くプログラム」の編集履歴(バックアップ)一覧に戻る

prolog勉強18日目 六望星のフィリップイットスターを解くプログラム - (2013/06/16 (日) 03:34:08) のソース

Prolog勉強18~19日目。
このページは小学校の算数までしかできないと創価学会の方に噂を流されている堀江伸一こと私の勉強日記。
あとあのカス野郎とかひたすら気持ち悪いとか、色々うわさを流されてます。
このような噂を流されている私ですが例えば小学校の算数までしかできないかどうかはこのページを読んで噂どおりかはご自分で判断して下さい。


今回はリンク先のパズル問題を解くコードをPrologで書いてみました。
http://www.geocities.jp/m_hiroi/puzzle/flip_it.html


今回の挑戦は手続き的なアプローチから脱却するためのコードの書き方の模索です。
正しい答えは出てますあgコードは失敗してる気がします。
事実の定義がめんどくさいことになっていましてもう少し賢く書けそうな気がしました。
手続き的な処理なら書けるのですがProlog的処理はまだまだみについてない感じです。

パズルをプログラムで解く理由ですが。
あるプログラム言語が実用品を記述できる能力がどれだけあるか、これは一つの問題です。
これの一つの判断材料に。
パズル(競技プログラムに出てくるような問題や数学的問題も含む)を解くプログラムをその言語で書いたとき。
どれだけ効率よく書けるかで、その言語が実用品を作る能力をどれだけもっているかある程度はかることが出来るという有名な数学者による格言があります。

逆に言えば、パズルを解く記述を書くことは色々な問題を解くテクニックの基礎になる勉強してるのと同じだといえます。

またパズルを解くプログラムを書くにはそのプログラム言語の基礎機能を組み合わせる必要があり、基礎機能を効率よく復習するのと同じ効果はあります。
そのプログラム言語の基礎機能を覚えれたかの確認にパズルはある程度向いています。
これがパズルがプログラムの勉強で出題される一つの理由です。
それとパズルだと誰でもわかるので、問題への挑戦意欲もわきやすいという利点があるようです。


 %
 %____A
 %B_C___D_E
 %_F_____G
 %H_I___J_K
 %____L
 %C,D,F,G,I,J
 change(b,w).
 change(w,b).
 
 %C to E'
 move_table([A,B,C,D,s,F,G,H,I,J,K,L],[A,B,s,D1,C,F,G,H,I,J,K,L]):-
 	change(D,D1).
 
 
 %C to H'
 move_table([A,B,C,D,E,F,G,s,I,J,K,L],[A,B,s,D,E,F1,G,C,I,J,K,L]):-
 	change(F,F1).
 
 
 %D to B'
 move_table([A,s,C,D,E,F,G,H,I,J,K,L],[A,D,C1,s,E,F,G,H,I,J,K,L]):-
         change(C,C1).
 
 %D to K'
 move_table([A,B,C,D,E,F,G,H,I,J,s,L],[A,B,C,s,E,F,G1,H,I,J,D,L]):-
 	change(G,G1).
 
 
 %G to A'
 move_table([s,B,C,D,E,F,G,H,I,J,K,L],[G,B,C,D1,E,F,s,H,I,J,K,L]):-
 	change(D,D1).
 
 
 %G to L'
 move_table([A,B,C,D,E,F,G,H,I,J,K,s],[A,B,C,D,E,F,s,H,I,J1,K,G]):-
 	change(J,J1).
 
 
 %J to E'
 move_table([A,B,C,D,s,F,G,H,I,J,K,L],[A,B,C,D,J,F,G1,H,I,s,K,L]):-
 	change(G,G1).
 %J H'
 move_table([A,B,C,D,E,F,G,s,I,J,K,L],[A,B,C,D,E,F,G,J,I1,s,K,L]):-
 	change(I,I1).
 
 %K I'
 move_table([A,B,C,D,E,F,G,H,s,J,K,L],[A,B,C,D,E,F,G,H,K,J1,s,L]):-
 	change(J,J1).
 
 %B to I'
 move_table([A,B,C,D,E,F,G,H,s,J,K,L],[A,s,C,D,E,F1,G,H,B,J,K,L]):-
	change(F,F1). 
 
 %L to F'
 move_table([A,B,C,D,E,s,G,H,I,J,K,L],[A,B,C,D,E,L,G,H,I1,J,K,s]):-
 	change(I,I1).
 %F to A'
 move_table([s,B,C,D,E,F,G,H,I,J,K,L],[F,B,C1,D,E,s,G,H,I,J,K,L]):-
 	change(C,C1).
 
 %
 %____A
 %B_C___D_E
 %_F_____G
 %H_I___J_K
 %____L
 %C,D,F,G,I,J
 %
 %B to L'
 move_table([A,B,C,D,E,F,G,H,I,J,K,s],[A,s,C,D,E,F1,G,H,I1,J,K,B]):-
 	change(I,I1),change(F,F1).
 %L to E'
 move_table([A,B,C,D,s,F,G,H,I,J,K,L],[A,B,C,D,L,F,G1,H,I,J1,K,s]):-
 	change(G,G1),change(J,J1).
 %E to B'
 move_table([A,s,C,D,E,F,G,H,I,J,K,L],[A,E,C1,D1,s,F,G,H,I,J,K,L]):-
 	change(C,C1),change(D,D1).
 
 
 %H to A'
 move_table([s,B,C,D,E,F,G,H,I,J,K,L],[H,B,C1,D,E,F1,G,s,I,J,K,L]):-
 	change(C,C1),change(F,F1).
 %K to A'
 move_table([s,B,C,D,E,F,G,H,I,J,K,L],[K,B,C,D1,E,F,G1,H,I,J,s,L]):-
 	change(D,D1),change(G,G1).
 %K to H'
 move_table([A,B,C,D,E,F,G,s,I,J,K,L],[A,B,C,D,E,F,G,K,I1,J1,s,L]):-
 	change(I,I1),change(J,J1).
 
 one_move(X,Y):-move_table(X,Y).
 one_move(X,Y):-move_table(Y,X).
 
 w_count([],0):-!.
 w_count([X|Rest],Result):-X==w,!,w_count(Rest,Re),Result is Re +1.
 w_count([_|Rest],Result):-w_count(Rest,Result).
 
 one_print([A,B,C,D,E,F,G,H,I,J,K,L]):-
 	format('____~a\n',[A]),
 	format('~a_~a___~a_~a\n',[B,C,D,E]),
 	format('_~a_____~a\n',[F,G]),
 	format('~a_~a___~a_~a\n',[H,I,J,K]),
 	format('____~a\n',[L]).
 
 print_answer([]).
 print_answer([State|Rest]):-
 	print_answer(Rest),
 	one_print(State),nl.
 
 
 next_search(P,Limit,[State|Rest]):-
 	P<Limit,
         w_count(State,WC),
 	WC=:=11,
 	write(P),
 	!,print_answer([State|Rest]).
 next_search(P,Limit,[State|Rest]):-
 	P<Limit,
 	one_move(State,NextState),
 	P1 is P+1,
         not(member(NextState,Rest)),
 	next_search(P1,Limit,[NextState,State|Rest]).
 
 main:-between(17,19,N),
 	next_search(0,N,[[s,b,b,b,b,b,b,b,b,b,b,b]]).





----
上記コードを変更して今度は最長手数のリストを表示する処理を記述。
まあまあかな。
事実の定義がやっぱり長い。

 %
 %____A
 %B_C___D_E
 %_F_____G
 %H_I___J_K
 %____L
 %C,D,F,G,I,J
 change(b,w).
 change(w,b).
 
 %C to E'
 move_table([A,B,C,D,s,F,G,H,I,J,K,L],[A,B,s,D1,C,F,G,H,I,J,K,L]):-
 	change(D,D1).
 
 
 %C to H'
 move_table([A,B,C,D,E,F,G,s,I,J,K,L],[A,B,s,D,E,F1,G,C,I,J,K,L]):-
 	change(F,F1).
 
 
 %D to B'
 move_table([A,s,C,D,E,F,G,H,I,J,K,L],[A,D,C1,s,E,F,G,H,I,J,K,L]):-
         change(C,C1).
 
 %D to K'
 move_table([A,B,C,D,E,F,G,H,I,J,s,L],[A,B,C,s,E,F,G1,H,I,J,D,L]):-
 	change(G,G1).
 
 
 %G to A'
 move_table([s,B,C,D,E,F,G,H,I,J,K,L],[G,B,C,D1,E,F,s,H,I,J,K,L]):-
 	change(D,D1).
 
 
 %G to L'
 move_table([A,B,C,D,E,F,G,H,I,J,K,s],[A,B,C,D,E,F,s,H,I,J1,K,G]):-
 	change(J,J1).
 
 
 %J to E'
 move_table([A,B,C,D,s,F,G,H,I,J,K,L],[A,B,C,D,J,F,G1,H,I,s,K,L]):-
 	change(G,G1).
 %J H'
 move_table([A,B,C,D,E,F,G,s,I,J,K,L],[A,B,C,D,E,F,G,J,I1,s,K,L]):-
 	change(I,I1).
 
 % K I'
 move_table([A,B,C,D,E,F,G,H,s,J,K,L],[A,B,C,D,E,F,G,H,K,J1,s,L]):-
 	change(J,J1).
 
 %B to I'
 move_table([A,B,C,D,E,F,G,H,s,J,K,L],[A,s,C,D,E,F1,G,H,B,J,K,L]):-
 	change(F,F1).
 
 %L to F'
 move_table([A,B,C,D,E,s,G,H,I,J,K,L],[A,B,C,D,E,L,G,H,I1,J,K,s]):-
 	change(I,I1).
 %F to A'
 move_table([s,B,C,D,E,F,G,H,I,J,K,L],[F,B,C1,D,E,s,G,H,I,J,K,L]):-
 	change(C,C1).
 
 %
 %____A
 %B_C___D_E
 %_F_____G
 %H_I___J_K
 %____L
 %C,D,F,G,I,J
 % 
 %B to L'
 move_table([A,B,C,D,E,F,G,H,I,J,K,s],[A,s,C,D,E,F1,G,H,I1,J,K,B]):-
 	change(I,I1),change(F,F1).
 %L to E'
 move_table([A,B,C,D,s,F,G,H,I,J,K,L],[A,B,C,D,L,F,G1,H,I,J1,K,s]):-
 	change(G,G1),change(J,J1).
 %E to B'
 move_table([A,s,C,D,E,F,G,H,I,J,K,L],[A,E,C1,D1,s,F,G,H,I,J,K,L]):-
 	change(C,C1),change(D,D1).
 
 
 %H to A'
 move_table([s,B,C,D,E,F,G,H,I,J,K,L],[H,B,C1,D,E,F1,G,s,I,J,K,L]):-
 	change(C,C1),change(F,F1).
 %K to A'
 move_table([s,B,C,D,E,F,G,H,I,J,K,L],[K,B,C,D1,E,F,G1,H,I,J,s,L]):-
 	change(D,D1),change(G,G1).
 %K to H'
 move_table([A,B,C,D,E,F,G,s,I,J,K,L],[A,B,C,D,E,F,G,K,I1,J1,s,L]):-
 	change(I,I1),change(J,J1).
 
 one_move(X,Y):-move_table(X,Y).
 one_move(X,Y):-move_table(Y,X).
 
 w_count([],0):-!.
 w_count([X|Rest],Result):-X==w,!,w_count(Rest,Re),Result is Re +1.
 w_count([_|Rest],Result):-w_count(Rest,Result).
 
 one_print([]):-!.
 one_print([A,B,C,D,E,F,G,H,I,J,K,L]):-
 	format('____~a\n',[A]),
 	format('~a_~a___~a_~a\n',[B,C,D,E]),
 	format('_~a_____~a\n',[F,G]),
 	format('~a_~a___~a_~a\n',[H,I,J,K]),
 	format('____~a\n',[L]).
 
 one_search(OldList,NowList,NextState):-
 	select(NowState,NowList,_),
 	one_move(NowState,NextState),
  	not(member(NextState,OldList)),
 	not(member(NextState,NowList)). 
 
 write_all([]).
 write_all([State|Rest]):-write_all(Rest),one_print(State).
 
 next_search(_,OldList,[]):-!,write_all(OldList).
 next_search(P,OldList,NowList):-
 	!,
 	length(NowList,Len),
 	write(Len),nl,
 	findall(State,one_search(OldList,NowList,State),NextList),
 	P1 is P+1,
 	sort(NextList,NextList1),
 	next_search(P1,NowList,NextList1).
 
 main:-next_search(0,[],[[s,b,b,b,b,b,b,b,b,b,b,b],
  			[b,s,b,b,b,b,b,b,b,b,b,b],
  		        [b,b,s,b,b,b,b,b,b,b,b,b],
  			[b,b,b,s,b,b,b,b,b,b,b,b],
  			[b,b,b,b,s,b,b,b,b,b,b,b],
  			[b,b,b,b,b,s,b,b,b,b,b,b],
  			[b,b,b,b,b,b,s,b,b,b,b,b],
  			[b,b,b,b,b,b,b,s,b,b,b,b],
  			[b,b,b,b,b,b,b,b,s,b,b,b],
  			[b,b,b,b,b,b,b,b,b,s,b,b],
  			[b,b,b,b,b,b,b,b,b,b,s,b],
  			[b,b,b,b,b,b,b,b,b,b,b,s]]).


19日目
5星陣の組み合わせ数を求めるプログラムを書いてみた。
手続き的発想からすこしProlog的発想に近寄れた気がする。
でも手続きの方がプログラマの自由度を高めて便利に作られている気がするのでPrologはあまり好きにはなれないかもしれない。
 
 sums([A0,_,A2,_,_,A5,_,_,A8,_],Sum):-Sum is A0+A2+A5+A8.
 sums([_,_,_,_,A4,_,A6,A7,A8,_],Sum):-Sum is A8+A7+A6+A4.
 sums([_,A1,A2,A3,A4,_,_,_,_,_],Sum):-Sum is A4+A3+A2+A1.
 sums([_,A1,_,_,_,A5,_,A7,_,A9],Sum):-Sum is A1+A5+A7+A9.
 sums([A0,_,_,A3,_,_,A6,_,_,A9],Sum):-Sum is A9+A6+A3+A0.
 
 all_ok([A,A,A,A,A]).
 
 round_ok([A0,A1,_,_,A4,_,_,_,A8,A9]):-A0<A1,A0<A4,A0<A8,A0<A9.
 revers_ok([_,_,A2,A3,_,_,_,_,_,_]):-A2>A3.
 
 selects([],_,_).
 selects(_,_,[A1,A0]):-A0>A1,!,fail.
 selects(_,_,[A4,_,_,_,A0]):-A0>A4,!,fail.
 selects([X|Rest],List,Temp):-select(X,List,Rest1),selects(Rest,Rest1,[X|Temp]).
 
 
 search(List,Result):-
 	selects([A0,A1,A2,A3,A4,A5,A6,A7,A8,A9],List,[]),
 	Result=[A0,A1,A2,A3,A4,A5,A6,A7,A8,A9],
 	round_ok(Result),
 	revers_ok(Result),
 	findall(Sum,sums(Result,Sum),SumList),
 	all_ok(SumList).
 
 main:-findall(Perm,search([1,2,3,4,5,6,8,9,10,12],Perm),List), 
	length(List,Len),
 	write(Len).