・アルゴリズム
4次魔方陣は、16のセルのうち7つを決めると残りはすべて計算で求められます。この7個をどう選ぶかはいろいろですが、ここでは右図の青いセルとします。
回転や裏返しで同じになるものを重複して出さないようにするには以下の条件を付けておきます。
a < d < m , a < p
・Ｃ言語のプログラム
プログラムでは以上の7つのセルの数を順に決めるため7重のforループとなっています。1〜16の数が重複しないようにするには、使った数には使用済みの印（フラグ）を付けておきます。計算で求められる数は、１以上16以下であってまだ使われていない数であることを確認します。もし条件に合わない場合は、すぐに次の候補へと進みます。
なお、時間のかかるような仕事はないので、計算量を減らす対策はほとんどしていません。実行は表示を含めても1〜2秒でしょう。
/*
4次魔方陣の全解を求める Y.Oishi Jun,10,2008
4次魔方陣のセルに下のような変数を当てます
a b c d
e f g h
i j k l
m n o p
回転と裏返しの重複を禁止ために以下の条件をつけます。
a<d a<m a<p （４隅で最小が左上にくる：回転禁止）
d<m （裏返し禁止）
決定の手順
1) aを決める
2）dを決める（d>a)
3) mを決める（m>d）
p=34-a-d-m ∵4隅の和=34 (p>a）
4) fを決める
k=34-a-f-p
5) bを決める
c=34-a-b-d;
6) gを決める
j=34-d-g-m
o=34-c-g-k
n=34-b-f-j
7) eを決める
h=34-e-f-g
i=34-a-e-m
l=34-d-f-p
used[z]： 数の使用/未使用のフラグ 1:使用 0:未使用
*/
#include <stdio.h>
int main(void) {
int a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,used[17],z,count=0;
for(z=1;z<=16;z++) used[z]=0; /* 使用フラグのクリア */
for(a=1;a<=13;a++) { /* aのループ */
used[a]=1;
for(d=a+1;d<=15;d++) { /* dのループ */
used[d]=1;
for(m=d+1;m<=16;m++) { /* mのループ */
p=34-a-d-m; /* pを計算 */
if(p<a) break; /* 回転禁止条件より */
if(p>16) continue; /* 16以下であること*/
if(used[p]) continue; /* pが既に使用されていないか */
if(p==m) continue; /* mはまだusedに登録されていないので */
used[m]=used[p]=1; /* 使用済みのフラグを立てる */
for(f=1;f<=16;f++) { /* fのループ */
if(used[f]) continue; /* fが既に使用されていないか */
k=34-a-f-p; /* kを計算 */
if(k<1) break; /* 1以上であること（kはこの先減る） */
if(k>16) continue; /* 16以下であること */
if(used[k]) continue; /* kが既に使用されていないか */
if(f==k) continue; /* fはまだusedに登録されていないので */
used[f]=used[k]=1; /* 使用済みのフラグを立てる */
for(b=1;b<=16;b++) { /* bのループ */
if(used[b]) continue;
c=34-a-b-d;
if(c<1) break;
if(c>16) continue;
if(used[c]) continue;
if(b==c) continue;
used[b]=used[c]=1;
for(g=1;g<=16;g++) { /* gのループ */
if(used[g]) continue;
j=34-d-g-m;
if(j<1) break;
if(j>16) continue;
if(used[j]) continue;
if(j==g) continue;
o=34-c-g-k;
if(o<1) break;
if(o>16) continue;
if(used[o]) continue;
if(o==g || o==j) continue;
n=34-b-f-j;
if(n>16) break;
if(n<1) continue;
if(used[n]) continue;
if(n==g || n==j || n==o) continue;
used[g]=used[j]=used[o]=used[n]=1;
for(e=1;e<=16;e++) { /* eのループ */
if(used[e]) continue;
h=34-e-f-g;
if(h<1) break;
if(h>16) continue;
if(used[h]) continue;
if(h==e) continue;
i=34-a-e-m;
if(i<1) break;
if(i>16) continue;
if(used[i]) continue;
if(i==e || i==h ) continue;
l=34-d-h-p;
if(l>16) break;
if(l<1) continue;
if(used[l]) continue;
if(l==e || l==h || l==i) continue;
/* 完成：表示 */
count++;
printf("%3d%3d%3d%3d\n",a,b,c,d);
printf("%3d%3d%3d%3d\n",e,f,g,h);
printf("%3d%3d%3d%3d\n",i,j,k,l);
printf("%3d%3d%3d%3d%8d\n\n",m,n,o,p,count);
}
used[g]=used[j]=used[o]=used[n]=0; /* フラグを降ろす */
}
used[b]=used[c]=0;
}
used[f]=used[k]=0;
}
used[m]=used[p]=0;
}
used[d]=0;
}
used[a]=0;
}
return 0;
}
大同大学 情報学部 情報システム学科 大石研究室