プログラムの実行結果は以下の通り。
find[1]
6x6 Layout:
C C C C C C
C C C C C C
x . . . . .
x . . . . .
x . . . . .
x . . . . .
7x7 Layout:
. . . . . C C
. . . . . C C
. . . . . C C
. . . . . C C
A A A B B C C
A A A B B C C
A A A x x x x
0.125秒
図にすると以下の通り。
プログラムのソースは以下の通り。
#include "puzutl.h"
const ulong bit0 = 0x00000001;
const ulong bit1 = 0x00000002;
const ulong bit2 = 0x00000004;
const ulong bit3 = 0x00000008;
const ulong bit4 = 0x00000010;
const ulong bit5 = 0x00000020;
const ulong bit6 = 0x00000040;
const ulong bit7 = 0x00000080;
const ulong bit8 = 0x00000100;
const ulong bit9 = 0x00000200;
const ulong bit10 = 0x00000400;
const ulong bit11 = 0x00000800;
const ulong bit12 = 0x00001000;
const ulong bit13 = 0x00002000;
const ulong bit14 = 0x00004000;
const ulong bit15 = 0x00008000;
const ulong bit16 = 0x00010000;
const ulong bit17 = 0x00020000;
const ulong bit18 = 0x00040000;
const ulong bit19 = 0x00080000;
const ulong bit20 = 0x00100000;
const ulong bit21 = 0x00200000;
const ulong bit22 = 0x00400000;
const ulong bit23 = 0x00800000;
const ulong bit24 = 0x01000000;
const ulong bit25 = 0x02000000;
const ulong bit26 = 0x04000000;
const ulong bit27 = 0x08000000;
const ulong bit28 = 0x10000000;
const ulong bit29 = 0x20000000;
const ulong bit30 = 0x40000000;
const ulong 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;
inline int64 shift_right( int64 v)
{
if( (v&bit6) || (v&bit13) || (v&bit20) || (v&bit27) || (v&bit34) || (v&bit41) || (v&bit48)) return 0;
return v<<1;
}
inline int64 shift_down( int64 v)
{
if( (v&bit42) || (v&bit43) || (v&bit44) || (v&bit45) || (v&bit46) || (v&bit47) || (v&bit48)) return 0;
return v<<7;
}
inline int64 shift( int64 v, int x, int y) // 正規化した位置からx,y移動する
{
while( x-->0) v = shift_right(v);
while( y-->0) v = shift_down(v);
return v;
}
inline int64 normalize( int64 v) // 正規化する(左上に図形を移動する)
{
while( !(v & (bit0|bit1|bit2|bit3|bit4|bit5|bit6))) {
v >>= 7;
}
while( !(v & (bit0|bit7|bit14|bit21|bit28|bit35|bit42))) {
v = ((v&(bit1|bit2|bit3|bit4|bit5|bit6))>>1)
| ((v&(bit8|bit9|bit10|bit11|bit12|bit13))>>1)
| ((v&(bit15|bit16|bit17|bit18|bit19|bit20))>>1)
| ((v&(bit22|bit23|bit24|bit25|bit26|bit27))>>1)
| ((v&(bit29|bit30|bit31|bit32|bit33|bit34))>>1)
| ((v&(bit36|bit37|bit38|bit39|bit40|bit41))>>1)
| ((v&(bit43|bit44|bit45|bit46|bit47|bit48))>>1)
;
}
return v;
}
int64 rotate90( int64 x) { // 90度回転する
int64 v = 0;
if( x&bit0) v |= bit42;
if( x&bit1) v |= bit35;
if( x&bit2) v |= bit28;
if( x&bit3) v |= bit21;
if( x&bit4) v |= bit14;
if( x&bit5) v |= bit7;
if( x&bit6) v |= bit0;
if( x&bit7) v |= bit43;
if( x&bit8) v |= bit36;
if( x&bit9) v |= bit29;
if( x&bit10) v |= bit22;
if( x&bit11) v |= bit15;
if( x&bit12) v |= bit8;
if( x&bit13) v |= bit1;
if( x&bit14) v |= bit44;
if( x&bit15) v |= bit37;
if( x&bit16) v |= bit30;
if( x&bit17) v |= bit23;
if( x&bit18) v |= bit16;
if( x&bit19) v |= bit9;
if( x&bit20) v |= bit2;
if( x&bit21) v |= bit45;
if( x&bit22) v |= bit38;
if( x&bit23) v |= bit31;
if( x&bit24) v |= bit24;
if( x&bit25) v |= bit17;
if( x&bit26) v |= bit10;
if( x&bit27) v |= bit3;
if( x&bit28) v |= bit46;
if( x&bit29) v |= bit39;
if( x&bit30) v |= bit32;
if( x&bit31) v |= bit25;
if( x&bit32) v |= bit18;
if( x&bit33) v |= bit11;
if( x&bit34) v |= bit4;
if( x&bit35) v |= bit47;
if( x&bit36) v |= bit40;
if( x&bit37) v |= bit33;
if( x&bit38) v |= bit26;
if( x&bit39) v |= bit19;
if( x&bit40) v |= bit12;
if( x&bit41) v |= bit5;
if( x&bit42) v |= bit48;
if( x&bit43) v |= bit41;
if( x&bit44) v |= bit34;
if( x&bit45) v |= bit27;
if( x&bit46) v |= bit20;
if( x&bit47) v |= bit13;
if( x&bit48) v |= bit6;
return v;
}
int64 mirror( int64 x) {
int64 v = 0;
if( x&bit0) v |= bit6;
if( x&bit1) v |= bit5;
if( x&bit2) v |= bit4;
if( x&bit3) v |= bit3;
if( x&bit4) v |= bit2;
if( x&bit5) v |= bit1;
if( x&bit6) v |= bit0;
if( x&bit7) v |= bit13;
if( x&bit8) v |= bit12;
if( x&bit9) v |= bit11;
if( x&bit10) v |= bit10;
if( x&bit11) v |= bit9;
if( x&bit12) v |= bit8;
if( x&bit13) v |= bit7;
if( x&bit14) v |= bit20;
if( x&bit15) v |= bit19;
if( x&bit16) v |= bit18;
if( x&bit17) v |= bit17;
if( x&bit18) v |= bit16;
if( x&bit19) v |= bit15;
if( x&bit20) v |= bit14;
if( x&bit21) v |= bit27;
if( x&bit22) v |= bit26;
if( x&bit23) v |= bit25;
if( x&bit24) v |= bit24;
if( x&bit25) v |= bit23;
if( x&bit26) v |= bit22;
if( x&bit27) v |= bit21;
if( x&bit28) v |= bit34;
if( x&bit29) v |= bit33;
if( x&bit30) v |= bit32;
if( x&bit31) v |= bit31;
if( x&bit32) v |= bit30;
if( x&bit33) v |= bit29;
if( x&bit34) v |= bit28;
if( x&bit35) v |= bit41;
if( x&bit36) v |= bit40;
if( x&bit37) v |= bit39;
if( x&bit38) v |= bit38;
if( x&bit39) v |= bit37;
if( x&bit40) v |= bit36;
if( x&bit41) v |= bit35;
if( x&bit42) v |= bit48;
if( x&bit43) v |= bit47;
if( x&bit44) v |= bit46;
if( x&bit45) v |= bit45;
if( x&bit46) v |= bit44;
if( x&bit47) v |= bit43;
if( x&bit48) v |= bit42;
return v;
}
int64 getbit( int i)
{
int64 bits[] = { bit0, bit1, bit2, bit3, bit4, bit5, bit6, bit7, bit8, bit9, bit10, bit11, bit12, bit13, bit14, bit15, bit16, bit17, bit18, bit19, bit20, bit21, bit22, bit23, bit24, bit25, bit26, bit27, bit28, bit29, bit30, bit31, bit32, bit33, bit34, bit35, bit36, bit37, bit38, bit39, bit40, bit41, bit42, bit43, bit44, bit45, bit46, bit47, bit48, bit49, bit50, bit51, bit52, bit53, bit54, bit55, bit56, bit57, bit58, bit59, bit60, bit61, bit62, bit63};
assert( i>= 0 && i< 64);
return bits[i];
}
int bitcountcmp( const void* v1, const void* v2)
{
int64 c1 = *(int64*)v1;
int64 c2 = *(int64*)v2;
return bitcount(c2) - bitcount(c1);
}
void cut66( int row, int col, int64& c1, int64& c2, int64& c3, int64& orgC1, int64& orgC2, int64& orgC3) // 6x6の図形Cを3分割する
{
c1 = c2 = c3 = 0;
for( int i=0; i< row; i++) { // 横に入れる切り込み線の上がc1
for( int j=0; j< 6; j++) {
c1 |= getbit(i*7+j);
}
}
for( ; i< 6; i++) { // 横の切り込み線の下にc2,c3がある。
for( int j=0; j< col; j++) { // 縦の切り込み線の左がc2
c2 |= getbit(i*7+j);
}
for( ; j< 6; j++) { // 縦の切り込み線の右がc3
c3 |= getbit(i*7+j);
}
}
int64 c[3] = {c1,c2,c3};
qsort( c, 3, sizeof(int64), bitcountcmp); // ビット数順にソートして返す,一番大きな図形を7x7の左上に配置するため
c1 = normalize(c[0]);
c2 = normalize(c[1]);
c3 = normalize(c[2]);
orgC1 = c[0]; // 元の図形のレイアウトを表示するために使用する
orgC2 = c[1];
orgC3 = c[2];
}
YesNo layout( int64& mat, int64 v, int64& shiftV) // 左上から空いている場所を探しvを配置する。
{
for( int row=0; row< 7; row++) {
for( int col=0; col< 7; col++) {
if( (mat&getbit(row*7+col)) == 0) { // 空きが見つかった,ここにvを配置する
shiftV = shift(v,col,row);
if( shiftV == 0) return NO; // 7x7の矩形を溢れた
mat |= shiftV;
return YES;
}
}
}
assert( 0); // ここに来ることは無いはず
return NO; // あり得ない
}
set<string> goal; // 見つかった解答を重複出力しないようにする
int num_goal = 0; // 重複除去した結果の解答数
void pack_goal( astring p, int64 A, char a, int64 B, char b, int64 C, char c, int64 D, char d, int64 E, char e) // 7x7の矩形を文字列に変換する
{
// 出力用と重複チェックの両方で使う。
YesNo yn_printed;
for( int i=0; i< 49; i++) {
yn_printed = NO;
if( A & 1) { *p++ = a; yn_printed = YES;}
if( B & 1) { *p++ = b; yn_printed = YES;}
if( C & 1) { *p++ = c; yn_printed = YES;}
if( D & 1) { *p++ = d; yn_printed = YES;}
if( E & 1) { *p++ = e; yn_printed = YES;}
*p++= ' ';
if( ((i+1)%7)==0) *p++ = '\n';
A>>=1;
B>>=1;
C>>=1;
D>>=1;
E>>=1;
}
*p = NIL;
}
void regist_goal( int64 A, char a, int64 B, char b, int64 C, char c, int64 D, char d, int64 E, char e) // 解の組み合わせを登録する
{
char buf[100];
for( int mirror=0; mirror< 2; mirror++) {
for( int rotate=0; rotate< 4; rotate++) {
pack_goal( buf, A, a, B, b, C, c, D, d, E, e);
goal.insert( buf);
A = rotate90(A);
B = rotate90(B);
C = rotate90(C);
D = rotate90(D);
E = rotate90(E);
}
A = ::mirror(A);
B = ::mirror(B);
C = ::mirror(C);
D = ::mirror(D);
E = ::mirror(E);
}
}
YesNo used[10];
void check( int64 orgC1, int64 orgC2, int64 orgC3, int64 C1, int64 C2, int64 C3, int64 A, int64 B) // 組み合わせて7x7の矩形になるか調べる
{
// C1,C2,C3はC1が最大。C1を左上に置くことを前提にする。
char s[] = {'.','C','x','A','B'}; // 出力用
char S[] = {'C','C','C','A','B'}; // 重複チェック用
int64 z[] = {C1,C2,C3,A,B};
for( int a=0; a< 1; a++) { // C1
used[a] = YES;
for( int b=1; b< 5; b++) { // C2
if( used[b]) continue;
used[b] = YES;
for( int c=1; c< 5; c++) { // C3
if( used[c]) continue;
used[c] = YES;
for( int d=1; d< 5; d++) { // A
if( used[d]) continue;
used[d] = YES;
for( int e=1; e< 5; e++) { // B
if( used[e]) continue;
used[e] = YES;
int64 mat = 0; // 7x7の矩形
int64 layoutA, layoutB, layoutC, layoutD, layoutE; // 実際のレイアウト
if( layout(mat,z[a],layoutA) && // 順番に空いている場所に配置していく
layout(mat,z[b],layoutB) &&
layout(mat,z[c],layoutC) &&
layout(mat,z[d],layoutD) &&
layout(mat,z[e],layoutE) &&
bitcount(mat) == 49) {// 全て配置できたら7x7の矩形を隙間が無いか調べる
char buf[128];
pack_goal( buf, layoutA, S[a], layoutB, S[b], layoutC, S[c], layoutD, S[d], layoutE, S[e]);
if( goal.find(buf) == goal.end()) { // 重複チェック
regist_goal( layoutA, S[a], layoutB, S[b], layoutC, S[c], layoutD, S[d], layoutE, S[e]);
num_goal++; // 初めて出現する状態なので
ps( "find[%d]\n", num_goal); // 出力する
ps( "6x6 Layout:\n");
pack_goal( buf, orgC1, '.', orgC2, 'C', orgC3, 'x', 0, 0, 0, 0);
ps( "%s", buf);
pack_goal( buf, layoutA, s[a], layoutB, s[b], layoutC, s[c], layoutD, s[d], layoutE, s[e]);
ps( "7x7 Layout:\n%s\n", buf);
}
}
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();
int64 A = bit0|bit1|bit2|bit7|bit8|bit9|bit14|bit15|bit16; // 3x3の矩形
int64 B = bit0|bit1|bit7|bit8; // 2x2の矩形
int64 orgC1, orgC2, orgC3; // 6x6を3分割した図形(6x6の分割を解と一緒に表示するために使用する)
int64 C1, C2, C3; // 6x6を3分割した図形,正規化したもの
for( int row=1; row<= 5; row++) { // 横に切り込みを入れる位置
for( int col=1; col<= 5; col++) { // 縦に切り込みを入れる位置
cut66( row, col, C1, C2, C3, orgC1, orgC2, orgC3); // 6x6の矩形を3分割する。最大図形をC1に返す
// A,Bは正方形なので回転を考慮する必要は無いが，C1,C2,C3は回転を考慮する
for( int r1=0; r1< 4; r1++) {
for( int r2=0; r2< 4; r2++) {
for( int r3=0; r3< 4; r3++) {
check( orgC1, orgC2, orgC3, normalize(C1), normalize(C2), normalize(C3), A, B); // A,B,C1,C2,C3の5つの矩形で7x7になるか調べる
C3 = rotate90(C3);
}
C2 = rotate90(C2);
}
C1 = rotate90(C1);
}
}
}
pt.end();
ps( "%g秒\n", pt.sec());
return 0;
}