朝日新聞2006年9月15日のパズル横丁問題

問題

以下の形状の図形がある。

ここに「コ」の字型をした以下の図形をマス目が一致するように重ねる。

元の図形の2升を適当に選べば,「コの字」をどのように乗せても,そのうち1升が必ず「コの字」に重なるように出来る。

2升を求める。

解答への道(ヒント)

図形問題だけどプログラムを作るには比較的簡単な問題。頭で考えても簡単な所が悲しいけど…

元の図形を4x4の図形と見なし,0〜15の番号を振る。

上記番号と16ビット整数のビット位置を対応させて考える。問題図の図形から例えば以下の2点を選択すると選択した図形は数値で

0001 0000 0100 0000 = 0x1040 になる。

元の図形から全ての2升(2点)を選択するには以下のようなコードになる。

  for( int i=0; i< 0x10000; i++) {
    if( !(i&0x0013) &&          // 0x0013 は元の図形の欠けている場所
        bitcount(i) == 2) {     // ビット数が2ということが2点に相当する
      // 元の図形から2点を選択した
    }
  }

「コの字」をどんな配置にしても選択した2点のどちらかと重なればそれが答えになる。

事前に「コの字」の全ての配置を求めておけば,プログラムは以下のようになる。

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

「コの字」は以下のような置き方を基本に4x4の図形内での配置を全て考えておく。

calcAllZ()は以下のようになる。

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

答えは1件出力されました。

 

今年は栗がうまい。去年は買う栗がことごとく外れだった。

解速度