朝日新聞2005年6月24日パズル横丁解答

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

□□□□□□
□□  □□
□□  ■□■■
□□□■■■■■
□□ ■■■■
□□□■■■
10.656秒

図示すると以下の通り。

90度左に回転し,以下のように貼り付ける。

プログラムのソースは以下の通り。

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

void neighborOff( int64& n, int64 bit)
{
  //dumpblock( n);
  if     ( bit0  & n & bit) {n &= ~(int64)bit0;  neighborOff( n, bit1);  neighborOff( n, bit2); }
  else if( bit1  & n & bit) {n &= ~(int64)bit1;  neighborOff( n, bit0);  neighborOff( n, bit3); }
  else if( bit2  & n & bit) {n &= ~(int64)bit2;  neighborOff( n, bit0);  neighborOff( n, bit3);  neighborOff( n, bit7); }
  else if( bit3  & n & bit) {n &= ~(int64)bit3;  neighborOff( n, bit1);  neighborOff( n, bit2);  neighborOff( n, bit4); neighborOff( n, bit8); }
  else if( bit4  & n & bit) {n &= ~(int64)bit4;  neighborOff( n, bit3);  neighborOff( n, bit9);  }
  else if( bit5  & n & bit) {n &= ~(int64)bit5;  neighborOff( n, bit6);  neighborOff( n, bit11); }
  else if( bit6  & n & bit) {n &= ~(int64)bit6;  neighborOff( n, bit5);  neighborOff( n, bit7); neighborOff( n, bit12); }
  else if( bit7  & n & bit) {n &= ~(int64)bit7;  neighborOff( n, bit2);  neighborOff( n, bit6); neighborOff( n, bit8); neighborOff( n, bit13); }
  else if( bit8  & n & bit) {n &= ~(int64)bit8;  neighborOff( n, bit3);  neighborOff( n, bit7);  neighborOff( n, bit9); neighborOff( n, bit14); }
  else if( bit9  & n & bit) {n &= ~(int64)bit9;  neighborOff( n, bit4);  neighborOff( n, bit8); neighborOff( n, bit10); neighborOff( n, bit15); }
  else if( bit10 & n & bit) {n &= ~(int64)bit10; neighborOff( n, bit9);  neighborOff( n, bit16); }
  else if( bit11 & n & bit) {n &= ~(int64)bit11; neighborOff( n, bit5);  neighborOff( n, bit12);  neighborOff( n, bit17); }
  else if( bit12 & n & bit) {n &= ~(int64)bit12; neighborOff( n, bit6);  neighborOff( n, bit11);  neighborOff( n, bit13); }
  else if( bit13 & n & bit) {n &= ~(int64)bit13; neighborOff( n, bit7);  neighborOff( n, bit12);  neighborOff( n, bit14); }
  else if( bit14 & n & bit) {n &= ~(int64)bit14; neighborOff( n, bit8);  neighborOff( n, bit13);  neighborOff( n, bit15); neighborOff( n, bit18); }
  else if( bit15 & n & bit) {n &= ~(int64)bit15; neighborOff( n, bit9);  neighborOff( n, bit14);  neighborOff( n, bit21); neighborOff( n, bit16); neighborOff( n, bit19); }
  else if( bit16 & n & bit) {n &= ~(int64)bit16; neighborOff( n, bit10); neighborOff( n, bit15);  neighborOff( n, bit20); }
  else if( bit17 & n & bit) {n &= ~(int64)bit17; neighborOff( n, bit11); neighborOff( n, bit21);  }
  else if( bit18 & n & bit) {n &= ~(int64)bit18; neighborOff( n, bit14); neighborOff( n, bit19);  neighborOff( n, bit22); }
  else if( bit19 & n & bit) {n &= ~(int64)bit19; neighborOff( n, bit15); neighborOff( n, bit18);  neighborOff( n, bit20); }
  else if( bit20 & n & bit) {n &= ~(int64)bit20; neighborOff( n, bit16); neighborOff( n, bit19);  neighborOff( n, bit23); }
  else if( bit21 & n & bit) {n &= ~(int64)bit21; neighborOff( n, bit17); neighborOff( n, bit29); }
  else if( bit22 & n & bit) {n &= ~(int64)bit22; neighborOff( n, bit18); neighborOff( n, bit32); }
  else if( bit23 & n & bit) {n &= ~(int64)bit23; neighborOff( n, bit20); neighborOff( n, bit34); }
  else if( bit29 & n & bit) {n &= ~(int64)bit29; neighborOff( n, bit21); neighborOff( n, bit30); }
  else if( bit30 & n & bit) {n &= ~(int64)bit30; neighborOff( n, bit29); neighborOff( n, bit31); }
  else if( bit31 & n & bit) {n &= ~(int64)bit31; neighborOff( n, bit30); neighborOff( n, bit32); }
  else if( bit32 & n & bit) {n &= ~(int64)bit32; neighborOff( n, bit22); neighborOff( n, bit31); neighborOff( n, bit33); }
  else if( bit33 & n & bit) {n &= ~(int64)bit33; neighborOff( n, bit32); neighborOff( n, bit34); }
  else if( bit34 & n & bit) {n &= ~(int64)bit34; neighborOff( n, bit23); neighborOff( n, bit33); }
}

YesNo contcheck( int64 n)
{
  //--------------------------------------------------------------------
  // パーツが連続しているかどうか調べる。
  // YES:連続している。
  // NO :連続していない。
  // 最初に見つかったビットに隣接するビットを削除していって戻ってきたとき,
  // 削除されていないビットがあれば連続していない。削除されていないビットがなければ連続している。
  //--------------------------------------------------------------------
  for( int i=0; i< 34; i++) {
    if( bits[i] & n) {
      neighborOff( n, bits[i]);
      n &= ~(int64)bits[i];
      return    n?NO:YES;
    }
  }
  return    NO;
}

void prb( int on)
{
  if( on< 0) ps( " "); else if( on) ps( "■"); else ps( "□");
}

void print( int i)
{
  prb(0); prb(0); prb( i&bit21); prb( i&bit17); prb( i&bit11); prb( i&bit5); ps( "\n");
  prb(0); prb(0); prb( -1); prb( -1); prb( i&bit12); prb( i&bit6); ps( "\n");
  prb(0); prb(0); prb( -1); prb( -1); prb( i&bit13); prb( i&bit7); prb( i&bit2); prb( i&bit0); ps( "\n");
  prb(0); prb(0); prb( i&bit22); prb( i&bit18); prb( i&bit14); prb( i&bit8); prb( i&bit3); prb( i&bit1); ps( "\n");
  prb(0); prb(0); prb( -1); prb( i&bit19); prb( i&bit15); prb( i&bit9); prb( i&bit4); ps( "\n");
  prb(0); prb(0); prb( i&bit23); prb( i&bit20); prb( i&bit16); prb( i&bit10); ps( "\n");
}

int main( int argc, cstring argv[])
{
ProcTime      pt;
  int cnt = 0;
  int i, j;
  int sp = bit24|bit25|bit26|bit27|bit28;
  for( i=0; i< 0xFFFFFF; i++) {
    cnt++;
    j = 0;
    // 0,1,2,3の4つの矩形が26,24,27,25の4つにマッピングされるように変換する。
    if( i & bit0 ) j |= bit26;
    if( i & bit1 ) j |= bit24;
    if( i & bit2 ) j |= bit27;
    if( i & bit3 ) j |= bit25;
    if( i & bit4 ) j |= bit13;
    if( i & bit7 ) j |= bit22;
    if( i & bit8 ) j |= bit18;
    if( i & bit9 ) j |= bit14;
    if( i & bit10) j |= bit8;
    if( i & bit13) j |= bit28;
    if( i & bit14) j |= bit19;
    if( i & bit15) j |= bit15;
    if( i & bit16) j |= bit9;
    if( i & bit18) j |= bit20;
    if( i & bit19) j |= bit16;
    if( i & bit20) j |= bit10;
    if( (j&sp) == sp) {         // 変換された
      if( contcheck(i) && contcheck(~(int64)i&0x7FFFFFFFF&~(int64)sp)) { // 元の図形が連続しており,残りの図形も連続している
        if( ((i&j)|(bit0|bit1|bit2|bit3|bit4)|sp) == (i|j)) { // 正方形になっているか?
          print( i);
        }         
      }
    }
  }
  pt.end();
  ps( "%g秒\n", pt.sec());
  return    0;
}