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

「prolog勉強25日目 パズルコレクション数字パズルを解いてみた」の編集履歴(バックアップ)一覧に戻る

prolog勉強25日目 パズルコレクション数字パズルを解いてみた - (2013/06/28 (金) 15:50:15) の1つ前との変更点

追加された行は青色になります

削除された行は赤色になります。

+堀江伸一
+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],[]).