朝日新聞2006年5月12日パズル横丁解答

プログラムの実行結果は以下の通り。

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;
}