【魔法陣1】https://twitter.com/puzzlegiver_bot/status/278001662394777600
パズルの定番。列、行、対角線の成分の総和がすべて等しくなるようにテーブルを完成させる。
ただし、入りうる値のリストが与えられている場合にのみ解答できる。そうでない場合は和の値が数値(number)ではなく変数であることを考慮して記述しなきゃなので、私には難しそうである。
それと、magic_matrixの P は“変数の少ない順”にソートした方が速い気がするけれど、この例題では違いがあまり感じられなかったので入れていない。無駄に長くなるし。
成分列が Src の順列であることの条件は、最初の3グループを調べるときに Src を減少させていく(‘⊆’の代わりに’∪’を使って差分も取っておき、それを次回のSrcにする)ことで記述できるけれど、そんな条件分岐を入れるとコードが読みづらくなるので省略した。時間の無駄とはいえ。
【魔法陣1】https://twitter.com/puzzlegiver_bot/status/278001662394777600
パズルの定番。列、行、対角線の成分の総和がすべて等しくなるようにテーブルを完成させる。
ただし、入りうる値のリストが与えられている場合にのみ解答できる。そうでない場合は和の値が数値(number)ではなく変数であることを考慮して記述しなきゃなので、私には難しそうである。
それと、magic_matrixの P は“変数の少ない順”にソートした方が速い気がするけれど、この例題では違いがあまり感じられなかったので入れていない。無駄に長くなるし。
成分列が Src の順列であることの条件は、最初の3グループを調べるときに Src を減少させていく(‘⊆’の代わりに’∪’を使って差分も取っておき、それを次回のSrcにする)ことで記述できるけれど、そんな条件分岐を入れるとコードが読みづらくなるので省略した。時間の無駄とはいえ。
append([], List, List). append([Head|Tail], List, [Head|TailR]) :- append(Tail, List, TailR). at([Val|Tail], 0, Val). at([Head|Tail], Idx, Val) :- number(Idx), Idx > 0, Idx1 is Idx - 1, at(Tail, Idx1, Val). % 平坦化 (リストのリスト(2次配列)を、リストの垣根を崩して1次元配列にする) flatten( Matrix, List ) :- flatten_acc( Matrix, List, [] ). flatten_acc( [], List, List ). flatten_acc( [Head|Tail], List, ListAcc ) :- append( ListAcc, Head, ListAcc2 ), flatten_acc( Tail, List, ListAcc2 ). % 行列 matrix([[Val]]). matrix([H|Tail]) :- list(H), length(H, CntColumns), matrix_(Tail, CntColumns). matrix_([X|[]], CntColumns) :- list(X), length(X, CntColumns). matrix_([H|Tail], CntColumns) :- list(H), length(H, CntColumns), matrix_(Tail, CntColumns). matrix_size([H|Tail], (X, Y)) :- matrix([H|Tail]), length([H|Tail], X), length(H, Y). % 対角成分 main_diag(M, L) :- matrix_size(M, (N, N)), diag_(M, L, 0, 1). sub_diag(M, L) :- matrix_size(M, (N, N)), Idx is N - 1, diag_(M, L, Idx, -1). diag_( [], [], _, _ ). diag_( [Row|TailRows], [H|T], Idx, Step ) :- at(Row, Idx, H), Idx1 is Idx + Step, diag_( TailRows, T, Idx1, Step ). % 列ベクトル columns(M, Idx, List) :- number(Idx), columns_acc(M, Idx, List, []). columns_acc([], Idx, List, List). columns_acc([Row|MTail], Idx, List, ListAcc) :- at(Row, Idx, Val), append(ListAcc, [Val], ListAcc2), columns_acc( MTail, Idx, List, ListAcc2 ). % 転置行列 transpose([], []). transpose(M, Mt) :- matrix_size(M, (N, N)), transpose_( M, Mt, 0 ). transpose_(M, [Head|Tail], Idx) :- number(Idx), Idx >= 0, columns(M, Idx, Head), Idx1 is Idx + 1, ( length(M, Idx1) -> Tail = [] ; transpose_(M, Tail, Idx1) ). % 集合操作 elem(E, [E|Others]). % '∈' elem(E, [_|Others]) :- elem(E, Others). addelem(E, Set, [E|Set]). % a.k.a. select 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([], []). multi_set_eq([E|LhsTail], Rhs) :- addelem(E, Rhs1, Rhs), multi_set_eq(LhsTail, Rhs1). % 総和 Σ sum([Head|Tail], Sum) :- sum_acc(Tail, Sum, Head). sum_acc([], Sum, SumAcc) :- Sum is SumAcc. sum_acc([Head|Tail], Sum, SumAcc) :- sum_acc(Tail, Sum, Head + SumAcc). % 魔法陣 magic_matrix(M, A, Src) :- matrix_size(M, (N, N)), M = A, sum(Src, SumSrc), Sum is SumSrc / N, % 総和が実数で求まる transpose(A, T), main_diag(A, DiagL), sub_diag(A, DiagR), append( A, T, P0 ), append( [DiagL, DiagR], P0, P ), % P : 和が Sum になるリストのリスト % write(P), nl, magic_lists(P, Sum, Src), flatten(A, Flat), multi_set_eq(Flat, Src). % 成分列が Src の順列になること magic_lists([], _, _). magic_lists([Head|Tail], Sum, Src) :- multi_subset(Head, Src), sum(Head, Sum), % write(Head), nl, magic_lists(Tail, Sum, Src). % 例題 ?- magic_matrix( [ [_, 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]] % (唯一解; 約8秒) */