「プロジェクトオイラー問６８」の編集履歴（バックアップ）一覧に戻る

プロジェクトオイラー問６８ - (2014/03/02 (日) 00:26:52) のソース

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2068
*Problem 68 「Magic 5-gon ring」 †
変わった形の魔法陣を完成させる問題。

解法
10は外側の点なのでそれを出発点とし、１０の入った合計すべき３つ点ラインに数字を入れます。
後はその数字と合計が同じになるように一つのライずつ埋めていって最後まで到達したものが答えの候補です。
外側の点が一番小さなものが手前に来るようにして出力すれば答えです。
要は枝狩りつき全探索。
 
 
 first([10,A0,A1],Nums,Nums2,Sum):-
 	select(A0,Nums,Nums1),
 	select(A1,Nums1,Nums2),
 	Sum is 10+A0+A1.
 
 sum3([],Nums,Sum,Nums,Sum):-!.
 sum3([X|Rest],Nums,Sum,ReNum,ReSum):-
 	select(X,Nums,Nums1),
 	Sum1 is Sum+X,
 	sum3(Rest,Nums1,Sum1,ReNum,ReSum).
 sum3([X|Rest],Nums,Sum,ReNum,ReSum):-
 	integer(X),
 	!,
 	Sum1 is Sum+X,
 	sum3(Rest,Nums,Sum1,ReNum,ReSum).
 
 
 search([],[],_):-!.
 search([Line|Rest],Nums,Sum):-
 	sum3(Line,Nums,0,Nums1,Sum1),
 	Sum1=:=Sum,
 	search(Rest,Nums1,Sum).
 
 search_TopMin([],Min,Min):-!.
 search_TopMin([[Top,_,_]|Rest],Min,Result):-
 	Top<Min,
 	!,
 	search_TopMin(Rest,Top,Result).
 search_TopMin([_|Rest],Min,Result):-
 	!,
 	search_TopMin(Rest,Min,Result).
 
 slide([[Min,X,Y]|Rest],Tops,Min,Result):-
 	!,
  	A=[[Min,X,Y]|Rest],
 	append(A,Tops,Result).
 slide([A|Rest],Tops,Min,Result):-
 	append(Tops,[A],Tops1),
 	slide(Rest,Tops1,Min,Result).
 
 
  main68:-
 	[Top|Rest]=[[10,A0,A1],[_,A1,A3],[_,A3,A5],[_,A5,A7],[_,A7,A0]],
 	Nums=[1,2,3,4,5,6,7,8,9],
  	first(Top,Nums,Nums2,Sum),
         search(Rest,Nums2,Sum),
  	Board=[Top|Rest],
 	search_TopMin(Board,10,Min),
 	slide(Board,[],Min,Ans),
 	write(Ans),nl,fail.