プログラムは2本あり，最初のプログラムの実行結果は以下の通り。
cnt:70254592 contcnt:64679 種類:705個, 最大パターン数:144 16.89秒
このプログラムは以下のようなファイルを出力する。
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 ………中略……… 37e,54,55,57,58,59,60,61,62 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
このファイルをソートして次のプログラムを実行した結果は以下の通り。
Find 0 1 2 8 16 24 32 33 9 17 21 25 26 27 28 29 10 11 12 13 14 18 22 30 34 35 36 37 38 42 46 54 Find 0 1 2 9 17 25 32 33 3 4 5 12 20 28 35 36 10 11 18 26 34 41 42 43 40 44 48 49 50 51 52 60 Find 0 1 2 3 4 8 12 16 9 10 11 19 27 35 42 43 17 18 25 33 41 49 50 51 20 21 28 36 44 52 53 54 Find 0 1 2 9 17 25 33 34 3 4 5 12 20 28 36 37 10 11 19 27 35 42 43 44 41 45 49 50 51 52 53 57 17.593秒
これを図にすると以下のようになる。
プログラムのソースは以下の通り。2本のプログラムの共通部分をヘッダファイルにしたので，ファイル数は3本になる。
// asahi-puzzleyokocho-20070119-1.cpp と asahi-puzzleyokocho-20070119-1.cpp から共通に使用される
const int64 bit0 = 0x00000001;
const int64 bit1 = 0x00000002;
const int64 bit2 = 0x00000004;
const int64 bit3 = 0x00000008;
const int64 bit4 = 0x00000010;
const int64 bit5 = 0x00000020;
const int64 bit6 = 0x00000040;
const int64 bit7 = 0x00000080;
const int64 bit8 = 0x00000100;
const int64 bit9 = 0x00000200;
const int64 bit10 = 0x00000400;
const int64 bit11 = 0x00000800;
const int64 bit12 = 0x00001000;
const int64 bit13 = 0x00002000;
const int64 bit14 = 0x00004000;
const int64 bit15 = 0x00008000;
const int64 bit16 = 0x00010000;
const int64 bit17 = 0x00020000;
const int64 bit18 = 0x00040000;
const int64 bit19 = 0x00080000;
const int64 bit20 = 0x00100000;
const int64 bit21 = 0x00200000;
const int64 bit22 = 0x00400000;
const int64 bit23 = 0x00800000;
const int64 bit24 = 0x01000000;
const int64 bit25 = 0x02000000;
const int64 bit26 = 0x04000000;
const int64 bit27 = 0x08000000;
const int64 bit28 = 0x10000000;
const int64 bit29 = 0x20000000;
const int64 bit30 = 0x40000000;
const int64 bit31 = 0x80000000;
const int64 bit32 = 0x0000000100000000L;
const int64 bit33 = 0x0000000200000000L;
const int64 bit34 = 0x0000000400000000L;
const int64 bit35 = 0x0000000800000000L;
const int64 bit36 = 0x0000001000000000L;
const int64 bit37 = 0x0000002000000000L;
const int64 bit38 = 0x0000004000000000L;
const int64 bit39 = 0x0000008000000000L;
const int64 bit40 = 0x0000010000000000L;
const int64 bit41 = 0x0000020000000000L;
const int64 bit42 = 0x0000040000000000L;
const int64 bit43 = 0x0000080000000000L;
const int64 bit44 = 0x0000100000000000L;
const int64 bit45 = 0x0000200000000000L;
const int64 bit46 = 0x0000400000000000L;
const int64 bit47 = 0x0000800000000000L;
const int64 bit48 = 0x0001000000000000L;
const int64 bit49 = 0x0002000000000000L;
const int64 bit50 = 0x0004000000000000L;
const int64 bit51 = 0x0008000000000000L;
const int64 bit52 = 0x0010000000000000L;
const int64 bit53 = 0x0020000000000000L;
const int64 bit54 = 0x0040000000000000L;
const int64 bit55 = 0x0080000000000000L;
const int64 bit56 = 0x0100000000000000L;
const int64 bit57 = 0x0200000000000000L;
const int64 bit58 = 0x0400000000000000L;
const int64 bit59 = 0x0800000000000000L;
const int64 bit60 = 0x1000000000000000L;
const int64 bit61 = 0x2000000000000000L;
const int64 bit62 = 0x4000000000000000L;
const int64 bit63 = 0x8000000000000000L;
int64 rotate90( int64 v) // 90度左に回転する
{
// 0 1 2 3 4 5 6 7 => 715233139475563
// 8 9101112131415 614223038465462
// 1617181920212223 513212937455361
// 2425262728293031 412202836445260
// 3233343536373839 311192735435159
// 4041424344454647 210182634425058
// 4849505152535455 1 9172533414957
// 5657585960616263 0 8162432404856
int64 u = 0;
if( v&bit7) u |= bit0;
if( v&bit15) u |= bit1;
if( v&bit23) u |= bit2;
if( v&bit31) u |= bit3;
if( v&bit39) u |= bit4;
if( v&bit47) u |= bit5;
if( v&bit55) u |= bit6;
if( v&bit63) u |= bit7;
if( v&bit6) u |= bit8;
if( v&bit14) u |= bit9;
if( v&bit22) u |= bit10;
if( v&bit30) u |= bit11;
if( v&bit38) u |= bit12;
if( v&bit46) u |= bit13;
if( v&bit54) u |= bit14;
if( v&bit62) u |= bit15;
if( v&bit5) u |= bit16;
if( v&bit13) u |= bit17;
if( v&bit21) u |= bit18;
if( v&bit29) u |= bit19;
if( v&bit37) u |= bit20;
if( v&bit45) u |= bit21;
if( v&bit53) u |= bit22;
if( v&bit61) u |= bit23;
if( v&bit4) u |= bit24;
if( v&bit12) u |= bit25;
if( v&bit20) u |= bit26;
if( v&bit28) u |= bit27;
if( v&bit36) u |= bit28;
if( v&bit44) u |= bit29;
if( v&bit52) u |= bit30;
if( v&bit60) u |= bit31;
if( v&bit3) u |= bit32;
if( v&bit11) u |= bit33;
if( v&bit19) u |= bit34;
if( v&bit27) u |= bit35;
if( v&bit35) u |= bit36;
if( v&bit43) u |= bit37;
if( v&bit51) u |= bit38;
if( v&bit59) u |= bit39;
if( v&bit2) u |= bit40;
if( v&bit10) u |= bit41;
if( v&bit18) u |= bit42;
if( v&bit26) u |= bit43;
if( v&bit34) u |= bit44;
if( v&bit42) u |= bit45;
if( v&bit50) u |= bit46;
if( v&bit58) u |= bit47;
if( v&bit1) u |= bit48;
if( v&bit9) u |= bit49;
if( v&bit17) u |= bit50;
if( v&bit25) u |= bit51;
if( v&bit33) u |= bit52;
if( v&bit41) u |= bit53;
if( v&bit49) u |= bit54;
if( v&bit57) u |= bit55;
if( v&bit0) u |= bit56;
if( v&bit8) u |= bit57;
if( v&bit16) u |= bit58;
if( v&bit24) u |= bit59;
if( v&bit32) u |= bit60;
if( v&bit40) u |= bit61;
if( v&bit48) u |= bit62;
if( v&bit56) u |= bit63;
return u;
}
inline YesNo exist( int x, int y)
{
if( x < 0 || y < 0) return NO;
if( x >= 8 || y >= 8) return NO;
return YES;
}
int64 normal64( int64 val) // 正規化,左上に集める
{
while( (val&(bit0|bit1|bit2|bit3|bit4|bit5|bit6|bit7)) == 0) { val >>= 8; val &= 0x00FFFFFFFFFFFFFF;}
while( (val&(bit0|bit8|bit16|bit24|bit32|bit40|bit48|bit56)) == 0) val >>= 1;
return val;
}
int64 min4( uint64 a, uint64 b, uint64 c, uint64 d) // 4つの数の最小値を求める,uint64にしないと悲劇が
{
return min(min(a,b),min(c,d));
}
最初のファイルを出力するプログラムは以下の通り。
#include "puzutl.h"
#include "asahi-puzzleyokocho-20070119-common.h"
int mat[8][8]; // 8x8の矩形,この上に図形を配置する
int num_erase; // 連続性をチェックするため，消した点の数を記録する
inline void erase( int x, int y)
{
// [x][y] の周りの数を消す。
num_erase++;
mat[x][y] = 0;
if(exist(x+0,y-1)&&mat[x+0][y-1]) { erase(x+0,y-1);}
if(exist(x-1,y+0)&&mat[x-1][y+0]) { erase(x-1,y+0);}
if(exist(x+1,y+0)&&mat[x+1][y+0]) { erase(x+1,y+0);}
if(exist(x+0,y+1)&&mat[x+0][y+1]) { erase(x+0,y+1);}
}
inline YesNo contcheck( int a, int b, int c, int d, int e, int f, int g, int h) // 連続しているかチェックする
{
YesNo cont = YES;
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] = 1;
mat[bx][by] = 1;
mat[cx][cy] = 1;
mat[dx][dy] = 1;
mat[ex][ey] = 1;
mat[fx][fy] = 1;
mat[gx][gy] = 1;
mat[hx][hy] = 1;
num_erase = 0;
erase(ax,ay);
if(num_erase!=8) cont = NO;
mat[ax][ay] = 0;
mat[bx][by] = 0;
mat[cx][cy] = 0;
mat[dx][dy] = 0;
mat[ex][ey] = 0;
mat[fx][fy] = 0;
mat[gx][gy] = 0;
mat[hx][hy] = 0;
return cont;
}
YesNo used[64+10/*予備*/];
int main( int argc, cstring argv[])
{
ProcTime pt;pt.start();
int64 cnt = 0;
int contcnt = 0;
map<int,int> cnt64; // 図形のパターン(正規化した値)とその個数
TextFile tf( "asahi-puzzleyokocho-20070119-tmp.txt", "w");
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;
cnt++; // ここに制約処理を書く
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++;
}
contcnt++;
}
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( "cnt:%I64d\n", cnt);
ps( "contcnt:%d\n", contcnt);
pt.end();
map<int,int>::iterator ite;
int maxpattern = 0;
for( ite=cnt64.begin(); ite != cnt64.end(); ite++) {
//ps( "%d,%d\n", (*ite).first, (*ite).second);
maxpattern = max( maxpattern, (*ite).second);
}
ps( "種類:%d個, 最大パターン数:%d\n", cnt64.size(), maxpattern);
ps( "%g秒\n", pt.sec());
return 0;
}
出力されたファイルを読み込んで解を求めるプログラムは以下の通り。
#include "puzutl.h"
#include "asahi-puzzleyokocho-20070119-common.h"
void get_hex( cstring& s, int& val) // 16進数を次のカンマまで取得する
{
val = 0;
while( *s && *s != ',') {
val *= 16;
if( *s >= '0' && *s <= '9') val += *s - '0';
else val += *s - 'a' + 10;
s++;
}
if( *s == ',') s++;
}
void get_int( cstring& s, int& val) // 10進数を次のカンマまで取得する
{
val = 0;
while( *s && *s != ',') {
val *= 10;
if( *s >= '0' && *s <= '9') val += *s - '0';
else val += *s - 'a' + 10;
s++;
}
if( *s == ',') s++;
}
void get_abcdefgh( cstring s, int& val, int& a, int& b, int& c, int& d, int& e, int& f, int& g, int& h) // "2020b0e,1,2,3,8,9,11,17,25" というような文字列から数字を順に取得する
{
get_hex(s,val);
get_int(s,a);
get_int(s,b);
get_int(s,c);
get_int(s,d);
get_int(s,e);
get_int(s,f);
get_int(s,g);
get_int(s,h);
}
const int s_num_pattern = 160; // 最大は144だけど余裕を見て(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 num_ok = 0;
int mat[8][8];
void expand( int idx, int pattern_no) // [idx]で指定される図形を展開する
{
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;
}
void dump( int idx)
{
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];
ps( "%d %d %d %d %d %d %d %d\n", a, b, c, d, e, f, g, h);
}
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個しかないでしょう
}
}
}
}
}
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;
}