プログラムの実行結果は以下の通り。3個目と4個目が答え。
+--+--+--+ | 2| 7| 6| +--+--+--+ | 9| 5| 1| +--+--+--+ | 4| 3| 8| +--+--+--+ +--+--+--+ |11|16|15| +--+--+--+ |18|14|10| +--+--+--+ |13|12|17| +--+--+--+ +--+--+--+ | 2|13| 9| +--+--+--+ |15| 8| 1| +--+--+--+ | 7| 3|14| +--+--+--+ +--+--+--+ | 5|16|12| +--+--+--+ |18|11| 4| +--+--+--+ |10| 6|17| +--+--+--+ +--+--+--+ | 3|13|11| +--+--+--+ |17| 9| 1| +--+--+--+ | 7| 5|15| +--+--+--+ +--+--+--+ | 4|14|12| +--+--+--+ |18|10| 2| +--+--+--+ | 8| 6|16| +--+--+--+ 0.343秒
文章にすると，「2倍して元の数を3で割った余りに1足したものを引く。もう一つは，それに+3したもの」。
わかり辛い。式だと「2*x-mod(x,3)-1」。
プログラムのソースは以下の通り。
#include "puzutl.h"
YesNo used[18+1]; // 1〜18の数字を使ったか? 1オリジンで使用する
int ga,gb,gc,gd,ge,gf,gg,gh,gi,gj; // 魔方陣を見つける関数を使い廻すので最初の魔方陣を見つけたら記録しておく
set<string> finded; // 見つけた魔方陣
void rotate90( int mat[3][3]) // 左に90度回転
{
// abc => cfi
// def beh
// ghi adg
int a=mat[0][0];
int b=mat[0][1];
int c=mat[0][2];
int d=mat[1][0];
int e=mat[1][1];
int f=mat[1][2];
int g=mat[2][0];
int h=mat[2][1];
int i=mat[2][2];
mat[0][0] = c;
mat[0][1] = f;
mat[0][2] = i;
mat[1][0] = b;
mat[1][1] = e;
mat[1][2] = h;
mat[2][0] = a;
mat[2][1] = d;
mat[2][2] = g;
}
void mirror( int mat[3][3]) // 左右対称
{
// abc => cba
// def fed
// ghi ihg
int a=mat[0][0];
int b=mat[0][1];
int c=mat[0][2];
int d=mat[1][0];
int e=mat[1][1];
int f=mat[1][2];
int g=mat[2][0];
int h=mat[2][1];
int i=mat[2][2];
mat[0][0] = c;
mat[0][1] = b;
mat[0][2] = a;
mat[1][0] = f;
mat[1][1] = e;
mat[1][2] = d;
mat[2][0] = i;
mat[2][1] = h;
mat[2][2] = g;
}
cstring mat2str( int mat[3][3])
{
static char buf[128];
buf[0] = 'A' + mat[0][0]; // 1数字1文字で記録できるように数字でなくアルファベットで記録する
buf[1] = 'A' + mat[0][1]; // 'A'から使う必要も無いので -1 しないでよい
buf[2] = 'A' + mat[0][2]; // 結局'B'から18文字使う
buf[3] = 'A' + mat[1][0];
buf[4] = 'A' + mat[1][1];
buf[5] = 'A' + mat[1][2];
buf[6] = 'A' + mat[2][0];
buf[7] = 'A' + mat[2][1];
buf[8] = 'A' + mat[2][2];
buf[9] = NIL; // 文字列にして
return buf;
}
void print( int mat[3][3]) // 魔方陣を出力する
{
cstring s = mat2str( mat);
if( finded.find(s) == finded.end()) {
ps( "+--+--+--+\n");
ps( "|%2d|%2d|%2d|\n", mat[0][0], mat[0][1], mat[0][2]);
ps( "+--+--+--+\n");
ps( "|%2d|%2d|%2d|\n", mat[1][0], mat[1][1], mat[1][2]);
ps( "+--+--+--+\n");
ps( "|%2d|%2d|%2d|\n", mat[2][0], mat[2][1], mat[2][2]);
ps( "+--+--+--+\n\n");
finded.insert(s);
}
}
void regist( int mat[3][3]) // 重複出力を避けるために見つかった魔方陣を記録する
{
cstring s = mat2str( mat);
finded.insert( s); // 登録する,既に登録してあれば登録できない
}
void print_find( int a, int b, int c, int d, int e, int f, int g, int h, int i) // 見つかった魔方陣を出力する
{
int mat[3][3] = {a,b,c,d,e,f,g,h,i}; // 見つかった魔方陣
print(mat); // 見つかった魔方陣を出力する,関数の中で重複チェックする
// 重複を出力しないように見つかった魔方陣と回転,ミラーしたものも登録しておく
regist(mat); mirror(mat); regist(mat); mirror(mat); rotate90(mat);
regist(mat); mirror(mat); regist(mat); mirror(mat); rotate90(mat);
regist(mat); mirror(mat); regist(mat); mirror(mat); rotate90(mat);
regist(mat); mirror(mat); regist(mat); mirror(mat); rotate90(mat);
}
void magic3( int once)
{
// abc
// def
// ghi
int abc;
for( int a=1; a<= 18; a++) { // 1〜9でなく1〜18の数字を使う魔方陣
if( used[a]) continue; // 一個だけの時は必要ないが関数を2回使い廻すので
used[a] = YES;
for( int b=1; b<= 18; b++) {
if( used[b]) continue;
used[b] = YES;
for( int c=1; c<= 18; c++) {
if( used[c]) continue;
abc = a+b+c; // 最初の行は何の制約もなく作成できる
used[c] = YES;
for( int d=1; d<= 18; d++) {
if( used[d]) continue;
if( a+d >= abc || a+d+18 < abc) continue;
used[d] = YES;
for( int e=1; e<= 18; e++) {
if( used[e]) continue;
if( b+e >= abc || b+e+18 < abc) continue;
if( a+e >= abc || a+e+18 < abc) continue;
if( c+e >= abc || c+e+18 < abc) continue;
used[e] = YES;
for( int f=1; f<= 18; f++) {
if( used[f]) continue;
if( d+e+f != abc) continue;
if( c+f >= abc || c+f+18 < abc) continue;
used[f] = YES;
for( int g=1; g<= 18; g++) {
if( used[g]) continue;
if( a+d+g != abc) continue;
if( c+e+g != abc) continue;
used[g] = YES;
for( int h=1; h<= 18; h++) {
if( used[h]) continue;
if( b+e+h != abc) continue;
used[h] = YES;
for( int i=1; i<= 18; i++) {
if( used[i]) continue;
if( g+h+i != abc) continue;
if( c+f+i != abc) continue;
if( a+e+i != abc) continue;
used[i] = YES;
if( once) { // 最初の魔方陣が見つかった
ga=a,gb=b,gc=c,gd=d,ge=e,gf=f,gg=g,gh=h,gi=i;// 解答を出力するため記録しておく
magic3( 0); // 2個目の魔方陣を探す
}
else { // 2個目の魔方陣が見つかった
print_find( ga,gb,gc,gd,ge,gf,gg,gh,gi); // 1個目の魔方陣
print_find( a,b,c,d,e,f,g,h,i); // 2個目の魔方陣
}
used[i] = NO;
}
used[h] = NO;
}
used[g] = NO;
}
used[f] = NO;
}
used[e] = NO;
}
used[d] = NO;
}
used[c] = NO;
}
used[b] = NO;
}
used[a] = NO;
}
}
int main( int argc, cstring argv[])
{
ProcTime pt;pt.start();
magic3( 1);
pt.end();
ps( "%g秒\n", pt.sec());
return 0;
}