1〜18までの数を使って3x3の魔方陣を2個作る。全部で3通りあるが，以下の2つ以外を見つける。
星3つ問題だけどプログラムを作って解くと結構簡単な問題。
但し出力された数字を見てオリジナルの魔方陣に対しどのようなパターンなのかということを見つける方が大変かな。
3x3の9升に以下の文字を割り当てる。
この問題は1〜18の数から9個を選択する数字の割り当て問題と見なすことが出来る。
数字の割り当て問題をコピーしてきて制約条件を追加する。
制約条件は以下の通り。
制約を加えないと爆発してしまう。2番目の制約は加えても速度に違いは無かったので外しても構わない。
制約を加えたプログラムは以下のようになる。
#include "puzutl.h"
YesNo used[1+18]; // 1〜18の数字を使ったか? 1オリジンで使用する
int main( int argc, cstring argv[])
{
// abc
// def
// ghi
int numFind = 0;
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;
numFind++;
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;
}
ps( "1〜18の数字を使う3x3の魔方陣の個数:%d\n", numFind);
return 0;
}
これで出力すると400件出力されます。
但し，これだと1個目だけしか見つけることが出来ないので，関数にしてもう一つ見ることが出来るようにする。
int ga,gb,gc,gd,ge,gf,gg,gh,gi,gj; // 魔方陣を見つける関数を使い廻すので最初の魔方陣を見つけたら記録しておく
void magic3( int once)
{
…
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個目の魔方陣
}
…
}
int main( int argc, cstring argv[])
{
magic3( 1);
return 0;
}
更に回転，鏡像のパターンを除去するように print_finded() を以下のようにする。
set<string> finded; // 見つけた魔方陣
void rotate90( int mat[3][3]) // 左に90度回転
{
// abc => cfi
// def beh
// ghi adg
…
}
void mirror( int mat[3][3]) // 左右対称
{
// abc => cba
// def fed
// ghi ihg
…
}
cstring mat2str( int mat[3][3])
{
static char buf[128];
… mat[3][3] を文字列に変換する。1つの値→1文字になるように「値+'A'」で文字列を作成。
return buf;
}
void print( int mat[3][3]) // 魔方陣を出力する
{
cstring s = mat2str( mat);
if( finded.find(s) == finded.end()) {
…出力する
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);
}
結果は以下のように6件出力される。
+--+--+--+ | 2| 7| 6| <= これがオリジナル,新聞の問題とは並びが異なる +--+--+--+ | 9| 5| 1| +--+--+--+ | 4| 3| 8| +--+--+--+ +--+--+--+ |11|16|15| <= オリジナルに +9したもの +--+--+--+ |18|14|10| +--+--+--+ |13|12|17| +--+--+--+ …ここに更に2件出力される +--+--+--+ | 3|13|11| <= オリジナルに *2-1 したもの +--+--+--+ |17| 9| 1| +--+--+--+ | 7| 5|15| +--+--+--+ +--+--+--+ | 4|14|12| <= オリジナルに *2 したもの +--+--+--+ |18|10| 2| +--+--+--+ | 8| 6|16| +--+--+--+ 0.343秒
問題では見た目が違うが4件指定されているので，残り2件が答えになる。
残り2件を「…したもの」で表現するのは結構大変。式なら簡単に書けるけど文字で表現するのはちょっと，てな感じ。
重複チェックは厳密には2個の魔方陣をセットで調べなければならないが，2個セットでチェックすると難しさが倍増するので1個毎にチェックしている。
今日からマクドナルドで「メガマック」が発売されたので早速購入してみた。「BIG」の次は「MEGA」か。更に大きいのが出たら「ギガマック」？
最近ハードディスクが個人でも「ギガ」を超えて「テラ」の時代に入ってきた。プログラムを作っているだけだと1ギガでも十分なんだけど，写真や動画を入れると途端に要領が不足する。2,3日前の新聞では「日立が1テラサイズの3.5型ハードディスクを発売」という話が載っていた。
意味はちょっと違うけど，いよいよ「地球へ」か。
解速度
Pentium Xeon2.4GHz で約0.35秒