朝日新聞2005年4月1日のパズル横丁問題

問題

以下のような形状の図形を2つのパーツに分割し同じ大きさ,同じ形にする。分割したパーツは裏返しても良い。切り口は四角を単位とする。

解答への道(ヒント)

パズルパーク終了後名前を替えて登場したパズル問題の第一段。

問題には「実はこの問題,コンピュータに作らせたものです」とある。

なにー!

じゃあ解く方も当然コンピュータじゃ。

ということで今回はプログラムを作って解くことに挑戦する。実は四角に沿って切れ目を入れるということなのでコンピュータで解くには比較的易しい問題になる。

解法は当然虱潰し方式。どうやって虱潰すかが問題。

四角の数は26個ある。ということは26ビットのループを廻す問題だ。26ビットだとループ回数は約6700万回。ちょっと回数が多いけど気にしない。

まずは四角にビットを割り当てる。

全部で26ビット。これをループで廻す。ちょうどビット数が13個あるのが候補になる。

  for( int i=0; i< 0x3FFFFFF; i++) {
    if( bitcount(i) == 13) 
      // 13個の四角を使った分割の候補
    }
  }

bitcount()は1ビットの数を求める関数を作成する。

extern const int bits4[] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4}; // 4ビット内のビット数
template int bitcount( S x) { // ビット数を計算する
  int n = sizeof(S) * 2; // 4ビットずつ計算するので
  int cnt = 0;
  extern const int bits4[];
  for( int i=0; i< n; i++) {
    cnt += bits4[ (int)(x & 0x0F) ];
    x >>= 4;
  }
  return    cnt;
}

これだけだと候補が1000万もある。もっと絞込が必要。連続性のチェックを追加する。

  for( int i=0; i< 0x3FFFFFF; i++) {
    if( bitcount(i) == 13 && contcheck(i)) 
      // 13個の四角を使い連続している
    }
  }

contcheck()は以下のような感じ。

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

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

これで実行してみると,38245通りの候補が出現する。

うーん,まだ多いな。ビットが立っているところが連続しているかどうかだけを判断材料にしていたが,ビットの立っていないところも連続していなければならないので,以下のようにしてみる。

  for( int i=0; i< 0x3FFFFFF; i++) {
    if( bitcount(i) == 13 && contcheck(i) && contcheck(~i&0x3FFFFFF)) {
      // 13個の四角を使い連続している,残り片も連続している
    }
  }

候補が一気に50に減った。50かー,ここから先はダンプして目で見て確認するって手もあるなー。

しかし,最後までプログラムしよう。ここから先は64ビット変数を使ってプログラムする。以下のように番号を振り直す。

最初の32ビットの数から64ビットの数への変換関数を以下のように定義する。

int64 conv64( ulong x) {
  int64         v = 0;
  if( x&bit0 ) v|= bit3;
  if( x&bit1 ) v|= bit4;
  if( x&bit2 ) v|= bit5;
  if( x&bit3 ) v|= bit10;
  if( x&bit4 ) v|= bit11;
  if( x&bit5 ) v|= bit12;
  if( x&bit6 ) v|= bit13;
  if( x&bit7 ) v|= bit17;
  if( x&bit8 ) v|= bit19;
  if( x&bit9 ) v|= bit20;
  if( x&bit10) v|= bit21;
  if( x&bit11) v|= bit22;
  if( x&bit12) v|= bit23;
  if( x&bit13) v|= bit24;
  if( x&bit14) v|= bit25;
  if( x&bit15) v|= bit26;
  if( x&bit16) v|= bit28;
  if( x&bit17) v|= bit29;
  if( x&bit18) v|= bit30;
  if( x&bit19) v|= bit31;
  if( x&bit20) v|= bit32;
  if( x&bit21) v|= bit33;
  if( x&bit22) v|= bit37;
  if( x&bit23) v|= bit38;
  if( x&bit24) v|= bit40;
  if( x&bit25) v|= bit44;
  return    v;
}

こんな感じで64ビットのマトリックスに変換するとコアになるコードは以下のようになる。結構シンプルでしょ。

for( int i=0; i< 0x3FFFFFF; i++) {
  if( i%100000 == 0) ps( "%d\r", i);
  if( bitcount(i) == 13 && contcheck(i) && contcheck(~i&0x3FFFFFF)) {
    // これを64ビットに変換する。
    int64 black = conv64(i);
    int64 white = conv64(~i&0x3FFFFFF);
    // 正規化する。
    int64 pat0 = normalize(black);
    int64 d1 = white;
    int64 d2 = rotate90(d1);
    int64 d3 = rotate90(d2);
    int64 d4 = rotate90(d3);
    int64 r1 = reverse(d1);
    int64 r2 = rotate90(r1);
    int64 r3 = rotate90(r2);
    int64 r4 = rotate90(r3);
    int64 data[] = { normalize(d1), normalize(d2), normalize(d3), normalize(d4), normalize(r1), normalize(r2), normalize(r3), normalize(r4)};
    for( int j=0; j< 8; j++) {
      if( data[j] == pat0) {
        dumpblock( i);
      }
    }
  }
}

rotate90()は90度回転,reverse()は反転,normalize()は図形を左上に寄せる。

ビットがONの図形とビットがOFFの図形を,ONの図形を固定し,OFFの図形を回転,反転+回転したものと比較する。

答えは2件出力されました。しかし,ビット1の部分とビット0の部分の2通り出力されるので実質1件。

今回のプログラムは2005年2月12日のパズルパーク問題を解くために作ったプログラムをコピペして作成した。切り口が四角に沿っただけなら大体こんな感じで解くことが出来る。

ちなみに2月12日の問題は切り口が斜めも可だったので途中で挫折した。この方法以外に外周と四角の頂点を結ぶ線を辿る迷路方式もちょっと頭に浮かんだがこちらの解法のが簡単そうだったのでこちらの方法を採用した。迷路方式は枝刈りが大変そう。上手に枝刈りが出来れば速そうだけど,そうでなければ爆発だー。

パズルパークではボールペンをゲットした後全然応募していなかった。パズル横丁では「種類は数ヶ月単位で替わる場合があります」とあるから,真面目に応募してみようかな。

解速度

40秒 PentiumV500MHz (デバッグ出力を削ったら34秒)