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

「プロジェクトオイラー問68」の編集履歴(バックアップ)一覧に戻る

プロジェクトオイラー問68 - (2014/03/02 (日) 00:25:49) の編集履歴(バックアップ)


Problem 68 「Magic 5-gon ring」 †

変わった形の魔法陣を完成させる問題。

解法
10は外側の点なのでそれを出発点とし、10の入った合計すべき3つ点ラインに数字を入れます。
後はその数字と合計が同じになるように一つのライずつ埋めていって最後まで到達したものが答えの候補です。
外側の点が一番小さなものが手前に来るようにして出力すれば答えです。
要は枝狩りつき全探索。


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.