プログラムの実行結果は以下の通り。
Find:24 : 84183 10884c 642210 1830420 pattern: 84183 □□□□□ ■□□□□ ■□□□□ □■■□□ □□□■■ pattern: 10884c □□□□■ □□□□■ □□□■□ □□□■□ □■■□□ pattern: 642210 □□■■□ □■□□□ □■□□□ ■□□□□ ■□□□□ pattern: 1830420 ■■□□□ □□■■□ □□□□■ □□□□■ □□□□□ pattern: 1ffefff ■■■■■ ■■■■■ ■■□■■ ■■■■■ ■■■■■ Find:24 : c10821 1082106 84d8 364200 pattern: c10821 □■■□□ □□□■□ □□□■□ □□□□■ □□□□■ pattern: 1082106 ■□□□□ ■□□□□ □■□□□ □■□□□ □□■■□ pattern: 84d8 □□□□□ □□□□■ □□□□■ □□■■□ ■■□□□ pattern: 364200 □□□■■ □■■□□ ■□□□□ ■□□□□ □□□□□ pattern: 1ffefff ■■■■■ ■■■■■ ■■□■■ ■■■■■ ■■■■■
2件出力されているが実質1件。
判りやすい絵にすると以下の通り。
プログラムのソースは以下の通り。
#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; int ngbit[] = { // 行,列上の並び // 行 bit24|bit23|bit22|bit21|bit20, bit19|bit18|bit17|bit16|bit15, bit14|bit13|bit12|bit11|bit10, bit9 |bit8 |bit7 |bit6 |bit5, bit4 |bit3 |bit2 |bit1 |bit0, // 列 bit24|bit19|bit14|bit9 |bit4, bit23|bit18|bit13|bit8 |bit3, bit22|bit17|bit12|bit7 |bit2, bit21|bit16|bit11|bit6 |bit1, bit20|bit15|bit10|bit5 |bit0, }; const int nngbit = sizeof(ngbit)/sizeof(ngbit[0]); YesNo samerc( int block1, int block2, int block3) // ブロック3個を5x5に配置できるか? { int cnt = 0; for( int i=0; i< nngbit; i++) { cnt = 0; if( ngbit[i] & block1) cnt++; if( ngbit[i] & block2) cnt++; if( ngbit[i] & block3) cnt++; if( cnt > 1) return YES; } return NO; } YesNo exist( int row, int col) { // 5x5の矩形内に存在する位置か? if( row < 0 || row >= 5) return NO; if( col < 0 || col >= 5) return NO; return YES; } void printpat( int bit) { ps( "pattern:%8x\n", bit); int p = 1<<24; for( int row=0; row< 5; row++) { for( int col=0; col< 5; col++) { if( bit&p) ps( "■"); else ps( "□"); p>>=1; } ps( "\n"); } } int main( int argc, cstring argv[]) { int row, col; int bit = 1; int i=0, j, k; // まず,5x5の矩形にビットを割り当てる。 int bits[5][5]; for( row=0; row< 5; row++) { for( col=0; col< 5; col++) { bits[row][col] = bit; bit<<=1; } } // ブロックをビットで表現する。 // ブロックの置き方は,25カ所に縦,横の2通りの置き方があるので,高々25x2通り=50通り。 int color[50]; // 高々50通りの置き方がある int ncolor = 0; for( row=0; row< 5; row++) { for( col=0; col< 5; col++) { if( exist(row+0,col+1)) { // 横置き color[ncolor++] = bits[row][col] | bits[row+0][col+1]; } if( exist(row+1,col+0)) { // 縦置き color[ncolor++] = bits[row][col] | bits[row+1][col+0]; } } } // 全部でncolor通りの置き方があった。 // 今度は,ncolor通りの置き方を3つ組み合わせた置き方がいくつあるか調べる。 // 同じ色のブロックが3個あるので。最大ncolor*ncolor*ncolor通りの置き方がある。 int* pattern = new int[ncolor*ncolor*ncolor]; int npattern = 0; // 実際に何通りの置き方があるか。 for( i=0; i< ncolor; i++) { for( j=i+1; j< ncolor; j++) { for( k=j+1; k< ncolor; k++) { if( (color[i] & color[j]) || (color[j] & color[k]) || (color[i] & color[k])) { // ブロック同士が重なっている。同じ位置に置けない continue; } // 同じ行,列に置けない。 if( samerc( color[i], color[j], color[k])) continue; // 5x5の矩形に同じ色の3個のブロックを置けた。 pattern[npattern] = color[i] | color[j] | color[k]; npattern++; } } } // ブロック3個を5x5に置く場合の数は全部でnpatternある。 int colorA, colorAB, colorABC, colorABCD; int a,b,c,d; // この組み合わせで互いに重ならないように置けるか調べる。 for( a=0; a< npattern; a++) { colorA = pattern[a]; for( b=a+1; b< npattern; b++) { if( colorA & pattern[b]) continue; colorAB = colorA | pattern[b]; for( c=b+1; c< npattern; c++) { if( colorAB & pattern[c]) continue; colorABC = colorAB | pattern[c]; for( d=c+1; d< npattern; d++) { if( colorABC & pattern[d]) continue; colorABCD = colorABC | pattern[d]; ps( "Find:%d : %8x %8x %8x %8x\n", bitcount(colorABCD), pattern[a], pattern[b], pattern[c], pattern[d]); printpat(pattern[a]); printpat(pattern[b]); printpat(pattern[c]); printpat(pattern[d]); printpat(pattern[a]|pattern[b]|pattern[c]|pattern[d]); } } } } return 0; }