堀江伸一
http://gunture.blog3.fc2.com/blog-entry-737.html
こちらのサイトで紹介されていた数字パズルというものをProlog言語でPCに解かせてみました。
多分現物を手作業で解けば15分くらいで解が見つかる気もするのですが、コンピュータに解かせてみたかったのです。
プログラムに一時間かかりました(手作業より遅いw)。

3流プログラマの見本みたいなコードがあるとしたらまさしくこのプログラムかもしれません。
コード自体は単なる深さ優先探索で左上から右下へ隙間なくピースの全回転パターンを敷き詰めようと試してるだけで何の工夫もありません。
回転パターンも全部手書きで定義してます。
回転反転をプログラムで書いてもよかったのですが、回転反転しても同じ形という重複の排除とかも記述すると考えたら。
それくらいなら事実をすべて網羅するのとコード量がそんなに大差ないかなという気もしたので全ての回転パターンを直書きしてみました。
2と5、6と9のパターンは共通するとか多少は省けたりしたので意外と記述時間は短かったです。

まあ回転反転重複排除で回転パターン全てをassertしたほうが技術的に勉強になったかもしれませんね。

一つ心残りは出力が見づらいこと。
辺を使うパズルはCUIでは表現しづらいものがあります。


num_pattern(0,[[1,0],[0,1],[2,1],[0,3],[2,3],[1,4]]).
num_pattern(0,[[1,0],[3,0],[0,1],[4,1],[1,2],[3,2]]).

num_pattern(1,[[0,1],[0,3]]).
num_pattern(1,[[1,0],[3,0]]).

num_pattern(2,[[1,0],[2,1],[1,2],[0,3],[1,4]]).
num_pattern(2,[[1,0],[0,1],[2,1],[4,1],[3,2]]).
num_pattern(2,[[1,0],[0,1],[1,2],[2,3],[1,4]]).
num_pattern(2,[[3,0],[0,1],[2,1],[4,1],[1,2]]).

num_pattern(3,[[1,0],[2,1],[1,2],[2,3],[1,4]]).
num_pattern(3,[[0,1],[1,2],[2,1],[3,2],[4,1]]).
num_pattern(3,[[1,0],[0,1],[1,2],[0,3],[1,4]]).
num_pattern(3,[[1,0],[3,0],[0,1],[2,1],[4,1]]).
 

num_pattern(4,[[0,1],[2,1],[1,2],[2,3]]).
num_pattern(4,[[1,0],[0,1],[-1,2],[1,2]]).
num_pattern(4,[[0,1],[1,2],[0,3],[2,3]]).
num_pattern(4,[[1,0],[3,0],[2,1],[1,2]]).

num_pattern(4,[[0,1],[2,1],[1,2],[0,3]]).
num_pattern(4,[[1,0],[2,1],[1,2],[3,2]]).
num_pattern(4,[[0,1],[-1,2],[-2,3],[0,3]]).
num_pattern(4,[[1,0],[3,0],[2,1],[3,2]]). 


num_pattern(5,Pattern):-num_pattern(2,Pattern).


num_pattern(6,[[1,0],[0,1],[1,2],[0,3],[2,3],[1,4]]).
num_pattern(6,[[1,0],[3,0],[0,1],[2,1],[4,1],[1,2]]).
num_pattern(6,[[1,0],[0,1],[2,1],[1,2],[2,3],[1,4]]).
num_pattern(6,[[3,0],[0,1],[2,1],[4,1],[1,2],[3,2]]).

num_pattern(6,[[1,0],[2,1],[1,2],[0,3],[2,3],[1,4]]).
num_pattern(6,[[1,0],[0,1],[2,1],[4,1],[1,2],[3,2]]).
num_pattern(6,[[1,0],[0,1],[2,1],[1,2],[0,3],[1,4]]).
num_pattern(6,[[1,0],[3,0],[0,1],[2,1],[4,1],[3,2]]).

num_pattern(7,[[1,0],[2,1],[2,3]]).
num_pattern(7,[[0,1],[-1,2],[-3,2]]).
num_pattern(7,[[0,1],[0,3],[1,4]]).
num_pattern(7,[[1,0],[3,0],[0,1]]).

num_pattern(7,[[1,0],[0,1],[0,3]]).
num_pattern(7,[[1,0],[3,0],[4,1]]).
num_pattern(7,[[0,1],[0,3],[-1,4]]).
num_pattern(7,[[0,1],[1,2],[3,2]]).

num_pattern(8,[[1,0],[0,1],[2,1],[1,2],[0,3],[2,3],[1,4]]).
num_pattern(8,[[1,0],[3,0],[0,1],[2,1],[4,1],[1,2],[3,2]]).

num_pattern(9,Pattern):-num_pattern(6,Pattern). 

update(_,_,_,[],NowState,NowState):-!.
update(Row,Col,No,[[X,Y]|Rest],NowState,[[X1,Y1,No]|Result]):- 
	X1 is Col+X,
	Y1 is Row+Y,
	XMax is 9+(Y1 mod 2),
	YMax is 7+(X1 mod 2),
	0=<X1,
	0=<Y1,
	X1=<XMax,
	Y1=<YMax,
	not(member([X1,Y1,_],NowState)),
	update(Row,Col,No,Rest,NowState,Result).

print_b([]).
print_b([[_,_,N0],[_,_,N1],[_,_,N2],[_,_,N3],[_,_,N4]|Rest]):-
	write([N0,s,N1,s,N2,s,N3,s,N4]),nl,
	print_a(Rest).

print_a([[_,_,N0],[_,_,N1],[_,_,N2],[_,_,N3]|Rest]):-
	write([s,N0,s,N1,s,N2,s,N3]),nl,
	print_b(Rest).


search(_,_,[],Ans):-
	!,sort(Ans,Ans1),
	print_a(Ans1).

search(Row,Col,Nums,Ans):-
	Row=:=8,
	Col1 is Col+1,
	member([Col1,Row,_],Ans),
	!,
	Col2 is Col+2,
	search(Row,Col2,Nums,Ans).

search(Row,Col,Nums,Ans):-
	Col=:=10,
	Row1 is Row+1,
	member([Col,Row1,_],Ans),
	!,
	Col2 is 0,
	Row2 is Row+2,
	search(Row2,Col2,Nums,Ans).

search(Row,Col,Nums,Ans):-
	Row1 is Row+1,
	Col1 is Col+1,
	member([Col1,Row,_],Ans),
	member([Col,Row1,_],Ans),
	!,
	Col2 is Col+2,
	search(Row,Col2,Nums,Ans).
search(Row,Col,Nums,Ans):-
	select(Num,Nums,RestNums),
	num_pattern(Num,NumP),
	update(Row,Col,Num,NumP,Ans,NextAns),
	search(Row,Col,RestNums,NextAns).

main:-search(0,0,[0,1,2,3,4,5,6,7,8,9],[]).

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2013年06月28日 15:52