魔方陣の枝刈りのこと 04月13日, 2010


ダン・ブラウン「ロスト・シンボル」に4x4の魔方陣の話がでてきます。まだ読んでいない方もあるでしょうが、謎解きに関わる事柄とは違うので、ネタバレでもないでしょうからかまわず書きますと、デューラーの版画に見えている魔方陣なのです。縱、横、ななめ、四隅、各隅4桝、中央4桝の合計が一致する魔方陣です。「不可能とも思える」魔方陣に驚嘆し興奮するラングドンとキャサリンの様子を読んだ時、これはそれほど難しい魔方陣なのだろうか、と思ったことが発端です。

別解を探してみることにしました。rubyやperlでも組めるでしょうが、こんな場合は、LISPのカッコだらけの記述は、どうも好みではないので、やはりprologに味があります。適当に述語を並べた時にパッと動き出す爽快感は、力技で多重ループをやっと抜け出すのとは全然違います。

最初は、permutationで探索するありふれた方法を試したのですが、残念なことに終了しません。チェックする枝が多すぎて、私のMacBookでは力が足りないのです。単純に計算すれば、20兆もあるので、力不足を嘆いても無理というもの。そこでNet上ではあまり見かけない枝刈りを工夫してみました。prologは、GNUのprolog-1.3.2を用い、ローカルな述語はほとんどありませんが、解を数えるのにglobal変数を利用しています。リスト中のsequentialは、自然数の並びを得る(1,2,3…)もので、16個の数字入力をさぼっただけです。deletesは、deleteを利用してリスト中の要素を別リストから削除します。これが枝刈りの根幹部分でしょう。permutationの代わりにcombinationで4桁ずつ題意に合うリストを発生させています。さて、「ロスト・シンボル」の主旨に従って下段の中2桝を(15,14)と指定した上で解を得ると、29秒後に解答は16個もあり、本に登場するのは12番目の解でした。以外に多い。満足、満足。

deletes(X, [], X).
deletes(L, [H|Ls], X) :-
    delete(L, H, X1),
    deletes(X1, Ls, X).

combination(0, _, []).
combination(N, [X | Xs], [X | Zs]) :-
    N > 0, N1 is N - 1, combination(N1, Xs, Zs).
combination(N, [_ | Xs], Zs) :- N > 0, combination(N, Xs, Zs).

sequential(I, N, []):- I > N.
sequential(I, N, [I|L1]):-
    I =< N, I1 is I + 1,
    sequential(I1, N, L1).

dan.pl