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

prolog勉強18日目 六望星のフィリップイットスターを解くプログラム - (2013/06/15 (土) 12:11:23) の編集履歴(バックアップ)


Prolog勉強18~19日目。
小学校の算数までしかできないと創価学会の方に噂を流されている堀江伸一こと私の勉強日記。
今日はリンク先のパズル問題を解くコードをPrologで書いてみた。
http://www.geocities.jp/m_hiroi/puzzle/flip_it.html


今日の挑戦は手続き的なアプローチから脱却するためのコードの書き方の模索。
今回のコードは失敗だった気がする。
事実の定義がめんどくさいことになっていてもう少し賢く書けそうな気がする。

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

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

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


%
%____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]]).