[Prolog]魔法陣<4×4> (入る値が与えられている場合)

【魔法陣1】https://twitter.com/puzzlegiver_bot/status/278001662394777600
先ほどのコード(http://codetter.com/?p=849)を 4×4 に特殊化したもの (groups_4x4 と同じことを記述するのにコードの半分近くを費やしていたことになる)。与えられた問題を解くだけならこれだけのコードで十分である。

また、どうやら調べるグループの順序によって速度が大きく異なるらしく、前回同様の対角線→行→列の順でそれなりの速さになる (もっと速い順序もあるかもしれない)。Row0→3, Clm0→3, DiagL, DiagR の順では待てど暮らせど終わらなかったので、修整を間違えたかと焦ったが、どうやら時間がかかりすぎているだけのようだった。なぜかは知らない。

【魔法陣1】https://twitter.com/puzzlegiver_bot/status/278001662394777600
先ほどのコード(http://codetter.com/?p=849)を 4×4 に特殊化したもの (groups_4x4 と同じことを記述するのにコードの半分近くを費やしていたことになる)。与えられた問題を解くだけならこれだけのコードで十分である。

また、どうやら調べるグループの順序によって速度が大きく異なるらしく、前回同様の対角線→行→列の順でそれなりの速さになる (もっと速い順序もあるかもしれない)。Row0→3, Clm0→3, DiagL, DiagR の順では待てど暮らせど終わらなかったので、修整を間違えたかと焦ったが、どうやら時間がかかりすぎているだけのようだった。なぜかは知らない。

% 4×4 行列分解
groups_4x4(
	[
		[M00, M01, M02, M03],	% 行ベクトルのリスト
		[M10, M11, M12, M13],
		[M20, M21, M22, M23],
		[M30, M31, M32, M33]
	], [
		[M00, M10, M20, M30],	% 列ベクトルのリスト
		[M01, M11, M21, M31],
		[M02, M12, M22, M32],
		[M03, M13, M23, M33]
	],
	[ M00, M11, M22, M33 ],		% 主対角線 (左上→右下)
	[ M30, M12, M21, M03 ],		%  対角線 (左下←右上)
	[ M00, M01, M02, M03,
	  M10, M11, M12, M13,
	  M20, M21, M22, M23,
	  M30, M31, M32, M33 ]	% 全成分のリスト
).

% addelem(S, E, S2): 集合Sに元Eを加えたものが、集合S2に等しいこと (ただし、主に S2 から E を取り除くために使う)
addelem(E, Set, [E|Set]).
addelem(E, [X|Set1], [X|Set2]) :- addelem(E, Set1, Set2).

% 多重集合の部分集合 ‘⊆’
multi_subset([], Rhs).
multi_subset([E|LhsTail], Rhs) :- addelem(E, Rhs1, Rhs), multi_subset(LhsTail, Rhs1).
multi_set_eq(L, R) :- multi_subset(L, R), multi_subset(R, L).	% 集合 ‘=’ :⇔ ‘⊆’ ∧ ‘⊇’

% 総和 Σ (sum(L, S): リストLの元の総和が数値Sumに等しい)
sum([Head|Tail], Sum) :- sum_acc(Tail, Sum, Head).
sum_acc([], Sum, Sum).
sum_acc([Head|Tail], Sum, SumAcc) :- SumAcc2 is SumAcc + Head, sum_acc(Tail, Sum, SumAcc2).

% 魔法陣
magic_matrix_4x4(M, A, Src) :-
	sum(Src, SumSrc), Sum is SumSrc / 4,
	M = A,
	M = [Row0, Row1, Row2, Row3],
	groups_4x4( M, [Clm0, Clm1, Clm2, Clm3], DiagL, DiagR, Flat ),
	magic_matrix_4x4_( [
		DiagL, DiagR,
		Row0, Row1, Row2, Row3,
		Clm0, Clm1, Clm2, Clm3 %,
	], Sum, Src ),
	multi_set_eq(Flat, Src).	% 成分列が Src の順列になること
	
magic_matrix_4x4_( [], _, _ ).
magic_matrix_4x4_( [Head|Tail], Sum, Src ) :-
	multi_subset(Head, Src),
	sum(Head, Sum),
	magic_matrix_4x4_(Tail, Sum, Src).
	
% 例題
?- magic_matrix_4x4( [
		[_, 18, _, _],
		[7, _, _, 10],
		[_, _, 9, _],
		[_, 5, _, _]
	], A, [2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19] ).

% A = [[6,18,17,2],[7,12,14,10],[11,8,9,15],[19,5,3,16]] (唯一解)