大きさが8の同じ形の4枚の図形が互いに接触するように升の上に組み合わせる。図形はひっくり返してはならない。
大きさ15の板の場合の組み合わせ例を示す。
大きさが8というところが如何にもプログラムを作って解いてくださいって感じ。
8より大きかったらちょっと無理だけど，8なのでプログラムを作って解くことにする。
8x8の矩形に収まる形で解が見つかるという前提でプログラムを作る。これで64ビットの整数で処理できる。
図形は升の上に配置することが前提なので以下のような図形は考え無くて良い。
解き方は少々強引であるが以下のようにする。
一旦ファイルに出力するようにしたのは，前後の処理で時間が掛かるので問題を分けた方が開発が簡単になるからである。
2つに分ける必然性は無いので，1つのプログラムで作成しても良い。
まずは8x8の盤上に大きさ8の図形を作成する。プログラムは以下のようになる。
YesNo used[64+10/*予備*/];
for( int a=0; a< 64; a++) {
used[a] = YES;
for( int b=a+1; b<= min(a+8,64); b++) {
if( used[b]) continue;
used[b] = YES;
for( int c=b+1; c<= min(b+8,64); c++) {
if( used[c]) continue;
used[c] = YES;
for( int d=c+1; d<= min(c+8,64); d++) {
if( used[d]) continue;
used[d] = YES;
for( int e=d+1; e<= min(d+8,64); e++) {
if( used[e]) continue;
used[e] = YES;
for( int f=e+1; f<= min(e+8,64); f++) {
if( used[f]) continue;
used[f] = YES;
for( int g=f+1; g<= min(f+8,64); g++) {
if( used[g]) continue;
used[g] = YES;
for( int h=g+1; h<= min(g+8,64); h++) {
if( used[h]) continue;
used[h] = YES;
// a,b,c,d,e,f,g,hが図形候補
used[h] = NO;
}
used[g] = NO;
}
used[f] = NO;
}
used[e] = NO;
}
used[d] = NO;
}
used[c] = NO;
}
used[b] = NO;
}
used[a] = NO;
}
ポイントはb,c,d,e,f,g,hのループ回数を最大8回に絞ったこと。これをやらないと処理時間が掛かりすぎることになる。
以下の図でaの位置が決まったとすると，bはそこから最大1周り分しか候補値としては存在しないことになる。
a,b,c,d,e,f,g,hは連続していなければならないので，連続性をチェックして連続していたら正規化してファイルに出力する。
正規化することで以下の図形が同じ形状であることが判る。
ファイルへの出力部分は以下のようになる。
map<int,int> cnt64; // 図形のパターン(正規化した値)とその個数
if( contcheck(a,b,c,d,e,f,g,h)) { // a,b,c,d,e,f,g,hが連続しているか?
int64 val1 = (bit0<<a) | (bit0<<b) | (bit0<<c) | (bit0<<d) | (bit0<<e) | (bit0<<f) | (bit0<<g) | (bit0<<h);
int64 val2 = rotate90(val1);
int64 val3 = rotate90(val2);
int64 val4 = rotate90(val3);
int64 val = min4(normal64(val1),normal64(val2),normal64(val3),normal64(val4));
tf.ps( "%x,%d,%d,%d,%d,%d,%d,%d,%d\n", (int)val, a,b,c,d,e,f,g,h);
assert( (val & 0xFFFFFFFF00000000) == 0); // 正規化したら32ビットに収まるはず
map<int,int>::iterator ite = cnt64.find( (int)val);
if( ite == cnt64.end()) {
cnt64.insert( pair<int,int>(val,1));
}
else {
(*ite).second++;
}
}
正規化することで例えば上記図形は 10141f がパターンとして出力されることになる。
ファイルには以下のようなデータが64,679件出力される。同じパターンのものが最大144件出力される。ちなみにパターン自体は705件ある。
ff,0,1,2,3,4,5,6,7 17f,0,1,2,3,4,5,6,8 27f,0,1,2,3,4,5,6,9 47f,0,1,2,3,4,5,6,10 87f,0,1,2,3,4,5,6,11 …中略… 33f,54,55,58,59,60,61,62,63 17f,54,56,57,58,59,60,61,62 27f,54,57,58,59,60,61,62,63 17f,55,57,58,59,60,61,62,63 ff,56,57,58,59,60,61,62,63
このファイルをソートして同じパターンが塊となるようにする。ソートはOpt-Tech Sortを使用したが別に何を使っても良い。
次はこのファイルを読んで同じパターン同士の図形を4個取り出して調べる。プログラムは以下のようになる。
const int s_num_pattern = 160; // 最大は144だけど余裕を見て
int A[s_num_pattern], B[s_num_pattern], C[s_num_pattern], D[s_num_pattern], E[s_num_pattern], F[s_num_pattern], G[s_num_pattern], H[s_num_pattern]; // a,b,c,d,e,f,g,h
int64 pattern[s_num_pattern]; // a,b,c,d,e,f,g,hで作る図形を64ビットで表現したもの
int num_pattern; // 同じパターンが何通りあるか?
int main( int argc, cstring argv[])
{
ProcTime pt;pt.start();
TextFile tf( "asahi-puzzleyokocho-20070119-sort.txt", "r");
cstring s;
int val, old_val=0, a,b,c,d,e,f,g,h;
while( (s=tf.gets()) != NULL) {
get_abcdefgh(s,val,a,b,c,d,e,f,g,h); // 正規化した数字とa,b,c,d,e,f,g,hを取り出す
if( val != old_val) { // 新しいパターンが出現した。
check_overlap_and_contact(); // 図形の重なりと接触をチェックする
num_pattern = 0;
old_val = val;
}
A[num_pattern] = a;
B[num_pattern] = b;
C[num_pattern] = c;
D[num_pattern] = d;
E[num_pattern] = e;
F[num_pattern] = f;
G[num_pattern] = g;
H[num_pattern] = h;
pattern[num_pattern] = (bit0<<a) | (bit0<<b) | (bit0<<c) | (bit0<<d) | (bit0<<e) | (bit0<<f) | (bit0<<g) | (bit0<<h);
num_pattern++;
}
check_overlap_and_contact(); // 図形の重なりと接触をチェックする
pt.end();
ps( "%g秒\n", pt.sec());
return 0;
}
check_overlap_and_contact() で読み込んである図形から4個取り出し重なりと接触を調べる。プログラムは以下のようになる。
int mat[8][8];
void expand( int idx, int pattern_no)
{
int a = A[idx], b = B[idx], c = C[idx], d = D[idx], e = E[idx], f = F[idx], g = G[idx], h = H[idx];
int ax,ay,bx,by,cx,cy,dx,dy,ex,ey,fx,fy,gx,gy,hx,hy;
ax = a%8; ay = a/8;
bx = b%8; by = b/8;
cx = c%8; cy = c/8;
dx = d%8; dy = d/8;
ex = e%8; ey = e/8;
fx = f%8; fy = f/8;
gx = g%8; gy = g/8;
hx = h%8; hy = h/8;
mat[ax][ay] = pattern_no;
mat[bx][by] = pattern_no;
mat[cx][cy] = pattern_no;
mat[dx][dy] = pattern_no;
mat[ex][ey] = pattern_no;
mat[fx][fy] = pattern_no;
mat[gx][gy] = pattern_no;
mat[hx][hy] = pattern_no;
}
YesNo check_neighbor_pattern( int x, int y, int pattern_no)
{
// [x][y] の隣に pattern_no が存在すればOK，存在しなければNG
if(exist(x+0,y-1)&&mat[x+0][y-1]==pattern_no) return YES;
if(exist(x-1,y+0)&&mat[x-1][y+0]==pattern_no) return YES;
if(exist(x+1,y+0)&&mat[x+1][y+0]==pattern_no) return YES;
if(exist(x+0,y+1)&&mat[x+0][y+1]==pattern_no) return YES;
return NO;
}
YesNo check_neighbor( int idx, int pattern_no)
{
// あるパターンの隣に指定したパターンが存在するか?
int a = A[idx], b = B[idx], c = C[idx], d = D[idx], e = E[idx], f = F[idx], g = G[idx], h = H[idx];
int ax,ay,bx,by,cx,cy,dx,dy,ex,ey,fx,fy,gx,gy,hx,hy;
ax = a%8; ay = a/8;
bx = b%8; by = b/8;
cx = c%8; cy = c/8;
dx = d%8; dy = d/8;
ex = e%8; ey = e/8;
fx = f%8; fy = f/8;
gx = g%8; gy = g/8;
hx = h%8; hy = h/8;
// 上下左右のどこかに指定したパターンが存在すれば隣り合う。
if( check_neighbor_pattern( ax, ay, pattern_no)) return YES;
if( check_neighbor_pattern( bx, by, pattern_no)) return YES;
if( check_neighbor_pattern( cx, cy, pattern_no)) return YES;
if( check_neighbor_pattern( dx, dy, pattern_no)) return YES;
if( check_neighbor_pattern( ex, ey, pattern_no)) return YES;
if( check_neighbor_pattern( fx, fy, pattern_no)) return YES;
if( check_neighbor_pattern( gx, gy, pattern_no)) return YES;
if( check_neighbor_pattern( hx, hy, pattern_no)) return YES;
return NO;
}
YesNo check_contact( int i, int j, int k, int m) // 重なりと接触を調べる
{
YesNo ok = YES;
expand(i,1); // 4枚の図形に1〜4の番号を割り当てて展開する
expand(j,2); // 既に重なりはチェックしてあるので，展開しても同じ場所に展開されることはない
expand(k,3);
expand(m,4);
if( check_neighbor( i, 2) == NO || // 図形1は図形2,図形3,図形4と接触しないとダメ
check_neighbor( i, 3) == NO ||
check_neighbor( i, 4) == NO ||
check_neighbor( j, 3) == NO || // 図形2は図形3,図形4と接触しないとダメ
check_neighbor( j, 4) == NO ||
check_neighbor( k, 4) == NO) { // 図形3は図形4と接触しないとダメ
ok = NO;
}
if( ok) { // 4つの図形がお互いに接触すれば解になる
ps( "Find\n");
dump( i);
dump( j);
dump( k);
dump( m);
}
expand(i,0); // mat[8][8]を毎回初期化しないで済むように
expand(j,0); // 元に戻す。
expand(k,0); // 毎回初期化すると多分遅くなる
expand(m,0);
return ok; // 見つかった?
}
void check_overlap_and_contact() // 4つの図形の重なりと接触を調べる
{
int64 valA, valB, valC, valD;
if( num_pattern == 0) return;
for( int i=0; i< num_pattern; i++) {
valA = pattern[i];
for( int j=i+1; j< num_pattern; j++) {
valB = pattern[j];
if( valA & valB) continue; // 重なり合うのでダメ
for( int k=j+1; k< num_pattern; k++) {
valC = pattern[k];
if( valA & valC) continue; // 重なり合うのでダメ
if( valB & valC) continue; // 重なり合うのでダメ
for( int m=k+1; m< num_pattern; m++) {
valD = pattern[m];
if( valA & valD) continue; // 重なり合うのでダメ
if( valB & valD) continue; // 重なり合うのでダメ
if( valC & valD) continue; // 重なり合うのでダメ
if( check_contact( i, j, k, m)) return; // 同じパターンでは解は1個しかないでしょう
}
}
}
}
}
答えは4件出力されました。2件は鏡像になっているので，実質2件。
最近小田原厚木道路に「シカに注意」の看板が出てることに気づいた。去年シカにぶつかる事故が発生したせいだと考えられる。
猪にぶつかったら「イノシシに注意」，熊にぶつかったら「クマに注意」，狸にぶつかったら「タヌキに注意」とかなっていくのかな？
こういうのってプログラマにとっては笑えないことだと思う。
「ライトついてますか？」の世界だな。
解速度
1つめのプログラムはPentium Xeon2.4GHz で約17秒
2つめのプログラムはPentium Xeon2.4GHz で約17秒
ありゃ，両方とも殆ど同じ時間だ。