gensym

プログラミングと読書、勉強に関するメモ

Prolog で魔方陣

思い立って prolog で魔方陣を作るコードを書いた。

3 * 3 の正方形のマスの中に 1~9 までの数字を入れて、すべての行、列、対角の和を等しくする。

% magic.pl

members([]). % リスト中の全ての要素が 1~9 のどれかであるか
members([Head | Tail]) :-
	member(Head, [1,2,3,4,5,6,7,8,9]),
	members(Tail).

magic(Solution) :-
	Solution = [S11,S12,S13,	
                    S21,S22,S23,	
                    S31,S32,S33],
	fd_all_different(Solution), % 要素が全て異なっているか
	members(Solution),
	C1 = S11 + S21 + S31, % 魔方陣の縦、横、斜めの要素の和
	C2 = S12 + S22 + S32,
	C3 = S13 + S23 + S33,
	R1 = S11 + S12 + S13,
	R2 = S21 + S22 + S23,
	R3 = S31 + S32 + S33,
	D1 = S11 + S22 + S33,
	D2 = S13 + S22 + S31,

	C1 =:= C2, C2 =:= C3, C3 =:= R1, R1 =:= R2, % それらが等しいか
	R2 =:= R3, R3 =:= D1, D1 =:= D2.
$ gprolog

インタプリタに入り、

| ?- [magic].

でファイルを読み込む。

| ?- magic(S).

のように尋ねると、 prolog

S = [2,7,6,9,5,1,4,3,8] ?

のような答えを8つ返す。回転や鏡像を考慮すると、これらは全て同じ物と見なすことができる。
リストで尋ねてもよい。

| ?- magic([_,_,_,_,1,_,_,_,_]).

| ?- magic([_,_,_,_,_,_,_,_]).

これらはどちらも no が返る。中心が1だったり、要素の数が8であったりする魔方陣は存在しない。

| ?- magic([_,A,_,3,5,_,_,_,_]).

のように合法な場合は yes を返し、 A が取り得る値も教えてくれる。

処理系は gnu prolog を使用した。ほかに有名なものに swi-prolog があるが、こちらでは上のコードの fd_all_different が使えないようで、動かなかった。処理系ごとに組み込みの関数などに結構な差があるようだ。


コードを書き加えて4 * 4の魔方陣もやってみたが、固まってしまった。どうやら 4*4の場合正解の場合の数が膨大になり、時間も莫大にかかってしまうようだ。 リストを渡してヒントを与えることで時間を短縮できる。