[Prolog]各部分の和が等しいように輪を分割するパズル | Codetter（こーどったー）

append([], List, List).
append([Head|Tail], List, [Head|TailR]) :- append(Tail, List, TailR).

部分リスト(List, (I, I), []).
部分リスト(List, (0, End), SubList) :-
	number(End), End > 0, 部分リスト_(List, End, SubList).
部分リスト([Head|Tail], (Bgn, End), SubList) :-
	number(Bgn), Bgn > 0, Bgn1 is Bgn - 1,
	number(End), End > 0, End1 is End - 1,
	部分リスト(Tail, (Bgn1, End1), SubList).
部分リスト_(_, 0, []).
部分リスト_([Head|Tail], Cnt, [Head|TailAcc]) :-
	Cnt > 0, Cnt1 is Cnt - 1, 部分リスト_(Tail, Cnt1, TailAcc).

整数閉区間(L, L, R) :- L =< R.
整数閉区間(N, L, R) :- L =< R, L1 is L + 1, 整数閉区間(N, L1, R).

和([Head|Tail], Sum) :- 和_acc(Tail, Sum, Head).
和_acc([], Sum, SumAcc) :- Sum is SumAcc.
和_acc([Head|Tail], Sum, SumAcc) :- 和_acc(Tail, Sum, Head + SumAcc).

弧(List, (I, I), []).
弧(List, (0, End), Arc) :- 部分リスト(List, (0, End), Arc).
弧(List, (Bgn, 0), Arc) :- length(List, N), 部分リスト(List, (Bgn, N), Arc).
弧(List, (Bgn_, End_), Arc) :-
	number(Bgn_), number(End_), Bgn_ =\= 0, End_ =\= 0,
	length(List, N),
	Bgn is ((Bgn_ mod N) + N) mod N,	% 非負最小剰余
	End is ((End_ mod N) + N) mod N,
	( Bgn < End
		->	部分リスト(List, (Bgn, End), Arc)
		;	弧(List, (Bgn, 0), ArcLead), 部分リスト(List, (0, End), ArcTrail),
			append(ArcLead, ArcTrail, Arc)
	).
	
輪の等和分割(List, [X|Answer], Div) :-
	和(List, ListSum), ArcSum is ListSum / Div,
	length(List, N),
	整数閉区間(X, 0, N),	% 第一の切断点(の右)
	輪の等和分割(List, [X|Cut], Div, ArcSum, N, N),
	append(Answer, [X], Cut).
	
輪の等和分割(_, [_], 0, _, _, 0).
輪の等和分割(List, [Bgn, End|Cut], Div, Sum, LenFull, LenRemain) :-
	整数閉区間(Len, 1, LenRemain), End is (Bgn + Len) mod LenFull,
	弧(List, (Bgn, End), Arc),
	和(Arc, Sum),
	Div1 is Div - 1, LenRemain1 is LenRemain - Len,
	輪の等和分割(List, [End|Cut], Div1, Sum, LenFull, LenRemain1).

% 例題
	?- 輪の等和分割( [1, 12, 5, 8, 10, 3, 11, 9, 6, 7, 4, 2], Answer, 3 ).
/*
Answer = [2,6,9].	% つまり 5, 11, 7 の左側 B, F, I で切断する
*/

% ---------------------
% おまけ：特殊バージョン (3分割、数値に重複がないことが条件)
between(L, L, R) :- L < R.
between(N, L, R) :- L < R, L1 is L + 1, between(N, L1, R).
 
隣接(1, 12). 隣接(12, 5). 隣接(5, 8). 隣接(8, 10). 隣接(10, 3). 隣接(3, 11).
隣接(11, 9). 隣接(9, 6). 隣接(6, 7). 隣接(7, 4). 隣接(4, 2). 隣接(2, 1).
 
区間(X, R) :- 隣接(X, R) ; (X \== R, 隣接(R1, R), 区間(X, R1)).
 
弧和(X, R, Sum) :- 区間(X, R), 弧和_acc(X, R, Sum, 0).
弧和_acc(X, X, Sum, SumAcc) :- !, Sum is SumAcc.
弧和_acc(X, R, Sum, SumAcc) :- 隣接(X, X1), 弧和_acc(X1, R, Sum, SumAcc + X).
 
３分割( [X, Y, Z], Sum ) :-
	between(X, 1, 13),
	弧和(X, Y, Sum), 弧和(Y, Z, Sum), 弧和(Z, X, Sum).
 
?- Sum is ((12*(12 + 1))/2) / 3, ３分割(A, Sum).
% A = [5,11,7]	% B, F, I