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

Text

[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 の順では待てど暮らせど終わらなかったので、修整を間違えたかと焦ったが、どうやら時間がかかりすぎているだけのようだった。なぜかは知らない。

ue_dai
2012/12/12 0:07

タグ：
prolog
puzzle

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
% 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]] (唯一解)
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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