朝日新聞2006年9月15日パズル横丁解答

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

××□□
×□□□
□□□●
□□●□

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

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

int shiftZukei( int z, YesNo yn_dirx, YesNo yn_diry) // 4x4の図形を移動する上下左右に移動する
{
  // +--+--+--+--+
  // |Ａ|Ｂ|Ｃ|Ｄ|
  // +--+--+--+--+
  // |Ｅ|Ｆ|Ｇ|Ｈ|
  // +--+--+--+--+
  // |Ｉ|Ｊ|Ｋ|Ｌ|
  // +--+--+--+--+
  // |Ｍ|Ｎ|Ｏ|Ｐ|
  // +--+--+--+--+
  if( yn_dirx) {                // 横方向に移動する
    // +--+--+--+--+
    // |　|Ａ|Ｂ|Ｃ|
    // +--+--+--+--+
    // |　|Ｅ|Ｆ|Ｇ|
    // +--+--+--+--+
    // |　|Ｉ|Ｊ|Ｋ|
    // +--+--+--+--+
    // |　|Ｍ|Ｎ|Ｏ|
    // +--+--+--+--+
    if( z & (bit3|bit7|bit11|bit15)) return 0; // NG(D,H,L,Pに1が立っていれば移動後溢れる)
    int         newZ = 0;
    if( z & bit0 ) newZ |= bit1;
    if( z & bit1 ) newZ |= bit2;
    if( z & bit2 ) newZ |= bit3;

    if( z & bit4 ) newZ |= bit5;
    if( z & bit5 ) newZ |= bit6;
    if( z & bit6 ) newZ |= bit7;

    if( z & bit8 ) newZ |= bit9;
    if( z & bit9 ) newZ |= bit10;
    if( z & bit10) newZ |= bit11;

    if( z & bit12) newZ |= bit13;
    if( z & bit13) newZ |= bit14;
    if( z & bit14) newZ |= bit15;
    z           = newZ;
  }
  if( yn_diry) {
    // +--+--+--+--+
    // |　|　|　|　|
    // +--+--+--+--+
    // |Ａ|Ｂ|Ｃ|Ｄ|
    // +--+--+--+--+
    // |Ｅ|Ｆ|Ｇ|Ｈ|
    // +--+--+--+--+
    // |Ｉ|Ｊ|Ｋ|Ｌ|
    // +--+--+--+--+
    if( z & (bit12|bit13|bit14|bit15)) return    0; // NG(M,N,O,Pに1が立っていれば移動後溢れる)
    int         newZ = 0;
    if( z & bit0 ) newZ |= bit4;
    if( z & bit1 ) newZ |= bit5;
    if( z & bit2 ) newZ |= bit6;
    if( z & bit3 ) newZ |= bit7;
    if( z & bit4 ) newZ |= bit8;
    if( z & bit5 ) newZ |= bit9;
    if( z & bit6 ) newZ |= bit10;
    if( z & bit7 ) newZ |= bit11;
    if( z & bit8 ) newZ |= bit12;
    if( z & bit9 ) newZ |= bit13;
    if( z & bit10) newZ |= bit14;
    if( z & bit11) newZ |= bit15;
    z           = newZ;
  }
  return    z;
}

int calcAllZ( int z[], int n, int zukei) // 「コの字」の配置方法を求める
{
  int           saveZukei = zukei;
  // 4x4内で基本図形をずらして配置できるものを選ぶ
  for( int ix=0; ix< 3; ix++) { // X方向にずらす
    zukei       = saveZukei;
    for( int iy=0; iy< 3; iy++) { // Y方向にずらす
      if( zukei) {              // ずらしても4x4内に図形が存在する
        if( !(zukei & 0x0013)) { // 左上の欠けている部分に重なっている場合はダメ
          z[n++]  = zukei;      // そうでなければ配置できる
        }
      }
      else {
        break;
      }
      zukei   = shiftZukei( zukei, NO, YES); // Y方向にずらす
    }
    saveZukei   = shiftZukei( saveZukei, YES, NO); // X方向にずらす
  }
  return    n;
}

void print_find( int i)
{
  if( i & bit0 ) ps( "●"); else ps( "×");
  if( i & bit1 ) ps( "●"); else ps( "×");
  if( i & bit2 ) ps( "●"); else ps( "□");
  if( i & bit3 ) ps( "●"); else ps( "□"); ps( "\n");
  if( i & bit4 ) ps( "●"); else ps( "×");
  if( i & bit5 ) ps( "●"); else ps( "□");
  if( i & bit6 ) ps( "●"); else ps( "□");
  if( i & bit7 ) ps( "●"); else ps( "□"); ps( "\n");
  if( i & bit8 ) ps( "●"); else ps( "□");
  if( i & bit9 ) ps( "●"); else ps( "□");
  if( i & bit10) ps( "●"); else ps( "□");
  if( i & bit11) ps( "●"); else ps( "□"); ps( "\n");
  if( i & bit12) ps( "●"); else ps( "□");
  if( i & bit13) ps( "●"); else ps( "□");
  if( i & bit14) ps( "●"); else ps( "□");
  if( i & bit15) ps( "●"); else ps( "□"); ps( "\n");
}

int main( int argc, cstring argv[])
{
  // まず「コの字」の配置を全て求めておく。
  int           N = 0;          // 「コの字」の置き方の総数
  const int     S = 100;
  int           z[S+1] = {0};   // 「コの字」のビット表現
  N             = calcAllZ( z, N, 0x0057); // 「コの字」の置き方-1
  N             = calcAllZ( z, N, 0x0313); // 「コの字」の置き方-2
  N             = calcAllZ( z, N, 0x0075); // 「コの字」の置き方-3
  N             = calcAllZ( z, N, 0x0323); // 「コの字」の置き方-4
  // 16升の中から2点を選択して，図形の全ての可能性と比較する。
  for( int i=0; i< 0x10000; i++) {
    if( !(i&0x0013) &&          // 0x0013 は元の図形の欠けている場所
        bitcount(i) == 2) {     // ビット数が2ということが2点に相当する
      // 16マスの中から2点を選択した
      // 全ての組み合わせと重なり合うか調べる。
      YesNo     yn_find = YES;
      for( int j=0; j< N; j++) {
        if( !(i & z[j])) {
          // 重なりが無い
          yn_find   = NO;
          break;
        }
      }
      if( yn_find) {
        print_find( i);
      }
    }
  }
  return    0;
}