「prolog勉強２５日目　パズルコレクション数字パズルを解いてみた」の編集履歴（バックアップ）一覧はこちら

「prolog勉強２５日目　パズルコレクション数字パズルを解いてみた」(2013/06/28 (金) 15:52:17) の最新版変更点

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

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

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

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

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

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


 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],[]).

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

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

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

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


 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],[]).