朝日新聞2005年6月24日のパズル横丁問題

問題

以下の図形を線に沿って2分割し6x6の正方形を作成する方法は?

分割した図形は裏返してはならない。

解答への道(ヒント)

お，一見プログラムで解けそうな問題。4月1日の問題に似ている。

だけど矩形の数が全部で36ある。これに全部番号を振って虱潰すにはちょっと数が多いなー。もう少し絞り込みをしないと。

直感的には以下のような分割が浮かぶから，

右の出っ張りの方から番号を振っていけば全部虱潰す前に解が見つかる可能性がある。

長さが７になる分割はあり得ないから，以下のように１と27が同じ分割片になることは無いはず。

そうすると24〜35までは考えなくて良いのかも知れない。となると24ビット。1600万か，結構絞り込めるな。

0〜4は同じ分割片に入れないと出っ張りが出来てしまうから，実質5〜23(19ビット)までの組合せを虱潰せば良いかな。

実はここら辺を考えていたのは風呂の中。POWER TANK(ボールペン)と耐水紙を持って風呂場でプログラミングと思いきや，ここまで方針が決まった後，ちょっと頭で考えてみようと思って直感の図から他の矩形の色分けを考えたら拍子抜けするほど簡単に出来てしまった。

うーん，プログラムを作成するべきかどうか迷うところだ。ちょっとインチキっぽいけどプログラムを作ってみようかな。

以下のように番号を振り，0,1,2,3が空きの部分に来るように

以下のような変換を考える。

以下のような24ビットのループを作成する。29,30,31,32,33,34は連続性のﾁｪｯｸだけに使用する。

int main( int argc, cstring argv[])
{
  int i, j;
  for( i=0; i< 0xFFFFFF; i++) {
    j = 0;
    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の24,25,26,27,28のビットがONで，iが連続し，jが連続し，iとjで0〜23を埋め尽くす場合) {
      答え発見
    }
  }
  return    0;
}

解速度

10秒(Pentium�V 500MHz)