魔方陣パズル

　魔方陣パズルを先日ネットで見つけた速い順列生成アルゴリズムを使って解いてみました。(^_^;
　ちなみに、解を1つ見つけたらbreakすると半分ぐらいの時間で終了します。それから、No.2の方も作ってみましたが、そちらは、1秒かかりませんでした。
　最近、ずっと思いつくままにパズルを解くプログラムを作ってきましたが、順列を使うものが多いような気がします。

●パズルに挑戦 ★★★魔方陣パズル★★★

+--+--+--+--+--+
|  |10|  |16|  |
+--+--+--+--+--+
|17|  |  |  |18|
+--+--+--+--+--+
|  |  | 3|  |  |
+--+--+--+--+--+
|25|  |  |  | 2|
+--+--+--+--+--+
|  |21|  |19|  |
+--+--+--+--+--+

/*
 * Magic.c
 *
 * [ a][10][ b][16][ *]  0  1  2  3  4
 * [17][ c][ d][ *][18]  5  6  7  8  9
 * [ e][ f][ 3][ g][ *] 10 11 12 13 14
 * [25][ *][ *][ *][ 2] 15 16 17 18 19
 * [ *][21][ *][19][ *] 20 21 22 23 24
 *
 * 変数: a,b,c,d,e,f,g 7個
 * [ *]は、残差から求める
 *
 */
 
#include <stdio.h>
#include <time.h>
// 参考URLの順列生成プログラムの main を #if 0 〜 #endif で無効化して_genperm.c に改名したソース
#include "_genperm.c"

#define Rem(a,b,c,d)	(65-(a)-(b)-(c)-(d))	// 残差を求める

// 1〜25までちゃんと揃っているか調べる関数
int check_all_num(int *x)
{
	int i,j;
	
	for(i=1;i<=25;i++){
		for(j=0; j<25; j++)
			if(x[j]==i) break;
		if(j==25) return(0);
	}
	
	return(1);
}

int main(void)
{
	int p[]={ 1, 4, 5, 6, 7, 8, 9,11,12,13,14,15,20,22,23,24};	// 順列生成用
	int m[]={	 0,10, 0,16, 0,
		17, 0, 0, 0,18,
		 0, 0, 3, 0, 0,
		25, 0, 0, 0, 2,
		 0,21, 0,19, 0
	};
	
	clock_t st,dt;
	
	st=clock();			// タイマースタート
	do{
		m[ 0]=p[ 0], m[ 2]=p[ 1];
		m[ 6]=p[ 2], m[ 7]=p[ 3];
		m[10]=p[ 4], m[11]=p[ 5], m[13]=p[ 6];
		
		if((m[ 4]=Rem(m[ 0],m[ 1],m[ 2],m[ 3]))<1) continue;
		if((m[ 8]=Rem(m[ 5],m[ 6],m[ 7],m[ 9]))<1) continue;
		if((m[14]=Rem(m[10],m[11],m[12],m[13]))<1) continue;
		if((m[16]=Rem(m[ 1],m[ 6],m[11],m[21]))<1) continue;
		if((m[18]=Rem(m[ 3],m[ 8],m[13],m[23]))<1) continue;
		if((m[17]=Rem(m[15],m[16],m[18],m[19]))<1) continue;
		if((m[20]=Rem(m[ 0],m[ 5],m[10],m[15]))<1) continue;
		if((m[22]=Rem(m[ 2],m[ 7],m[12],m[17]))<1) continue;
		if((m[24]=Rem(m[20],m[21],m[22],m[23]))<1) continue;
		
		if(m[24]!=Rem(m[ 4],m[ 9],m[14],m[19])) continue;

		// 1〜25までちゃんと揃っているか調べる
		if(!check_all_num(m)) continue;
								
		// チェックを潜り抜けたものだけを出力 		
		printf("%3d%3d%3d%3d%3d\n",m[ 0],m[ 1],m[ 2],m[ 3],m[ 4]);
		printf("%3d%3d%3d%3d%3d\n",m[ 5],m[ 6],m[ 7],m[ 8],m[ 9]);
		printf("%3d%3d%3d%3d%3d\n",m[10],m[11],m[12],m[13],m[14]);
		printf("%3d%3d%3d%3d%3d\n",m[15],m[16],m[17],m[18],m[19]);
		printf("%3d%3d%3d%3d%3d\n",m[20],m[21],m[22],m[23],m[24]);
		printf("\n");
		//break;
	}while (next_perm(p,16,7));
	dt=clock()-st;		// タイマーストップ
	printf("Runtime : %ld.%03ld [sec]\n",dt/1000,dt%1000);
	return(0);
}

●出力結果

 11 10 13 16 15
 17  6 23  1 18
  7 24  3  9 22
 25  4 14 20  2
  5 21 12 19  8

Runtime : 12.465 [sec]

※参考URL
●よしいずの雑記帳　 再帰呼び出しを使わずに順列や組合せを得るC言語プログラム (2)
●魔方陣パズル(2) - C言語 - rscの日記
●4次の魔方陣プログラム - C言語 - rscの日記
●数的推理の魔方陣の問題をJavaで解いてみた。 - rscの日記
●数的推理の魔方陣の問題をPythonで解いてみた。 - rscの日記

C言語によるはじめてのアルゴリズム入門 改訂第3版