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

Text

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

【魔法陣1】https://twitter.com/puzzlegiver_bot/status/278001662394777600
パズルの定番。列、行、対角線の成分の総和がすべて等しくなるようにテーブルを完成させる。
ただし、入りうる値のリストが与えられている場合にのみ解答できる。そうでない場合は和の値が数値(number)ではなく変数であることを考慮して記述しなきゃなので、私には難しそうである。

それと、magic_matrixの P は“変数の少ない順”にソートした方が速い気がするけれど、この例題では違いがあまり感じられなかったので入れていない。無駄に長くなるし。
成分列が Src の順列であることの条件は、最初の3グループを調べるときに Src を減少させていく(‘⊆’の代わりに’∪’を使って差分も取っておき、それを次回のSrcにする)ことで記述できるけれど、そんな条件分岐を入れるとコードが読みづらくなるので省略した。時間の無駄とはいえ。

ue_dai
2012/12/11 22:29

タグ：
prolog
pazzle

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
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秒)
*/
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

このコードをツイートする