「プロジェクトオイラー問68」の編集履歴(バックアップ)一覧はこちら
「プロジェクトオイラー問68」(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は外側の点なのでそれを出発点とし、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.
http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2068
*Problem 68 「Magic 5-gon ring」 †
変わった形の魔法陣を完成させる問題。
解法
10は外側の点なのでそれを出発点とし、10の入った合計すべき3つ点ラインに数字を入れます。
後はその数字と合計が同じになるように一つのライずつ埋めていって最後まで到達したものが答えの候補です。
外側の点が一番小さなものが手前に来るようにして出力すれば答えです。
要は枝狩りつき全探索。
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.