4次の魔方陣プログラム - C言語

　前回の魔方陣つながりで、4次の魔方陣を求めるプログラムをいつものdo{…}while(next_perm(p,n,r));構文を使って、C言語で作ってみました。(^_^;
　縦横斜めの和が34ならば、四隅の和も34になるらしいので、これを使えば、変数を7個にして、残りは残差から求めれば、
　₁₆Ｐ₇=5765'7600
だけチェックすればよいことになります。回転や鏡像も含めて全部で7040の解を得ました。
　ちなみに、中央の和も34になるそうです。(^_^;

●MagicSquare4.c

/*
 * MagicSquare4.c
 *   m              |   p
 * [ 0][ 1][ 2][ 3] | [ 0][ 1][ 2][ *]
 * [ 4][ 5][ 6][ 7] | [ 3][ 4][ 5][ *]
 * [ 8][ 9][10][11] | [ 6][ *][ *][ *]
 * [12][13][14][15] | [ *][ *][ *][ *]←四隅の和も34
 *
 * 変数は、 7個
 * [ *]は、残差で求める
 */

#include <stdio.h>
#include <time.h>
// 参考URLの順列生成プログラムの main を #if 0 〜 #endif で無効化して_genperm.c に改名したソース
#include "_genperm.c"

#define Rem(a,b,c)	(34-(a)-(b)-(c))	// 残差を求める
#define M	7	// 変数の数
#define N	16

// 1〜Nまでちゃんと揃っているか調べる関数
int check_all_num(int *x)
{
	int i,j;
	
	for(i=1;i<=N; i++){
		for(j=0; j< N; j++)
			if(x[j]==i) break;
		if(j==N) return(0);
	}	
	return(1);
}
void disp(int c, int *p)	// 表示
{
	printf("[%d]\n",c);
	printf("%3d%3d%3d%3d\n",p[ 0],p[ 1],p[ 2],p[ 3]);
	printf("%3d%3d%3d%3d\n",p[ 4],p[ 5],p[ 6],p[ 7]);
	printf("%3d%3d%3d%3d\n",p[ 8],p[ 9],p[10],p[11]);
	printf("%3d%3d%3d%3d\n",p[12],p[13],p[14],p[15]);
	printf("\n");
}

int main(void)
{
	int p[]={ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14,15,16};	// 順列生成用
	int m[N];

	int cnt=0;
	clock_t tm;
	
	tm=clock();		// Timer Start
	do{
		m[ 0]=p[ 0], m[ 1]=p[ 1], m[ 2]=p[ 2];
		m[ 4]=p[ 3], m[ 5]=p[ 4], m[ 6]=p[ 5];
		m[ 8]=p[ 6];
		
		if((m[ 3]=Rem(m[ 0],m[ 1],m[ 2]))<1) continue;
		if((m[ 7]=Rem(m[ 4],m[ 5],m[ 6]))<1) continue;
		if((m[12]=Rem(m[ 0],m[ 4],m[ 8]))<1) continue;
		if((m[ 9]=Rem(m[ 3],m[ 6],m[12]))<1) continue;
		if((m[13]=Rem(m[ 1],m[ 5],m[ 9]))<1) continue;
		if((m[15]=Rem(m[ 0],m[ 3],m[12]))<1) continue; // ∵四隅の和も34
 		if((m[10]=Rem(m[ 0],m[ 5],m[15]))<1) continue;
		if((m[11]=Rem(m[ 8],m[ 9],m[10]))<1) continue;
		if((m[14]=Rem(m[ 2],m[ 6],m[10]))<1) continue;
		
		// 1〜Nまでちゃんと揃っているか調べる
		if(!check_all_num(m)) continue;
		// チェックを潜り抜けたものだけを出力
		cnt++;
		disp(cnt,m);
		//break;
	}while (next_perm(p,N,M));
	printf("Total : %d\n",cnt);
	tm=clock()-tm;		// Timer Stop
	printf("Runtime : %.3f [sec]\n",(double)tm/CLOCKS_PER_SEC);
	return(0);
}

●実行結果

[1]
  1  2 15 16
 12 14  3  5
 13  7 10  4
  8 11  6  9

[2]
  1  2 15 16
 13 14  3  4
 12  7 10  5
  8 11  6  9

…(省略)…

[7040]
 16 15  2  1
  5  3 14 12
  4 10  7 13
  9  6 11  8

Total : 7040
Runtime : 14.072 [sec]

※参考URL
●よしいずの雑記帳　再帰呼び出しを使わずに順列や組合せを得るC言語プログラム (2)
●４次魔方陣を求めるプログラム
●4x4 Magic Square

●魔方陣パズル - rscの日記
●魔方陣パズル(2) - C言語 - rscの日記
●数的推理の魔方陣の問題をJavaで解いてみた。 - rscの日記
●数的推理の魔方陣の問題をPythonで解いてみた。 - rscの日記

●C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)　奥村晴彦 (著)