朝日新聞2005年2月19日のパズルパーク問題

問題

以下のように対角位置で連なっている16枚の矩形がある。これを4x4の正方形になるように並べ替える。但し矢印が全て上を向くようにしなければならない。

A,Bに示した矩形はどこに配置されるか?

解答への道(ヒント)

今年の車検の時に付けたETCを今日始めて使った。ちょっと緊張したけど,バーが開くと気持ちが良いものだ。

問題を見るとプログラムを作って解けそうな問題だ。矩形が16個しか無いから簡単に虱潰し出来そう。問題となるのはこれをどうやってデータ構造に表現するかということ。

最初矩形を順に4x4に配置していくことを考えた。

find( level)
{
  右に配置できる? find( level+1);
  上に配置できる? find( level+1);
  左に配置できる? find( level+1);
  下に配置できる? find( level+1);
}

だけど実は

を見ると,上下左右を考えるだけではダメなことが判る。

というように斜めも考えなければならない。何となく面倒な感じがする。そこで次に考えたのは,矩形を連結している部分に順に番号を振り,それをどこに配置すれば良いか考えるようにした。

これら0〜16の数字を以下の矩形上に配置することを考える。

例えば,10が7に配置されたとき,11は3,1,11,13の何れかに配置される可能性がある。

そうするとこれを虱潰すコードは以下のようになる。

find( level, nextpos)
{
  if( nextposの右上の点が存在すれば) find( level+1, nextposの右上の点);
  if( nextposの左上の点が存在すれば) find( level+1, nextposの左上の点);
  if( nextposの左下の点が存在すれば) find( level+1, nextposの左下の点);
  if( nextposの右下の点が存在すれば) find( level+1, nextposの右下の点);
}

後はこれに終了条件と制約条件を追加する。

終了条件はlevelが16になったとき,nextposがlevel=0の時と同じ位置になること。

制約条件は同じ矩形を踏まないことと,矢印が出現したlevelで矢印が上を向くことである。

find( level, nextpos)
{
  if( level==16) {
    if( 出発点に戻ったか?) Find;
    return;
  }
  if( 同じ矩形を踏んだ?) return;
  if( level==2 && 矢印の向きが上でない) return;
  if( level==3 && 矢印の向きが上でない) return;
  if( level==7 && 矢印の向きが上でない) return;
  if( level==8 && 矢印の向きが上でない) return;
  if( level==12 && 矢印の向きが上でない) return;
  if( level==13 && 矢印の向きが上でない) return;
  if( nextposの右上の点が存在すれば) find( level+1, nextposの右上の点);
  if( nextposの左上の点が存在すれば) find( level+1, nextposの左上の点);
  if( nextposの左下の点が存在すれば) find( level+1, nextposの左下の点);
  if( nextposの右下の点が存在すれば) find( level+1, nextposの右下の点);
}

最初の点は0〜24の25箇所を調べるので以下のようなコードになる。

level = 0;
for( i=0; i< 25; i++) {
  if( iの右上の点が存在すれば) find( level+1, iの右上の点);
  if( iの左上の点が存在すれば) find( level+1, iの左上の点);
  if( iの左下の点が存在すれば) find( level+1, iの左下の点);
  if( iの右下の点が存在すれば) find( level+1, iの右下の点);
}  

25箇所の位置について,次の移動先を以下の構造体で表現する。

struct struct_nextpos {
  int rt, lt, lb, rb; // 0〜24
  int rtbox, ltbox, lbbox, rbbox; // 0〜15
} nextpos[25];
int visit[16+1];// 訪問位置(0〜24)
int box[16+1]; // 踏んだ矩形(0〜15),初期値を-1に設定しておく

struct_nextpoosに初期値を設定する関数は以下の通り。

void init()
{
  for( int i=0; i< 25; i++) {
    nextpos[i].rt = i-5+1;
    nextpos[i].lt = i-5-1;
    nextpos[i].lb = i+5-1;
    nextpos[i].rb = i+5+1;
    nextpos[i].rtbox = i/5*4 + i%5 - 4;
    nextpos[i].ltbox = i/5*4 + i%5 - 4 - 1;
    nextpos[i].lbbox = i/5*4 + i%5 - 1;
    nextpos[i].rbbox = i/5*4 + i%5;
  }
  for( i=0; i< 5; i++) {
    nextpos[i].rt = -1;
    nextpos[i].lt = -1;
    nextpos[20+i].lb = i+5-1;
    nextpos[20+i].rb = i+5+1;
  }
  for( i=0; i< 25; i+=5) {
    nextpos[4+i].rt = -1;
    nextpos[i].lt = -1;
    nextpos[i].lb = -1;
    nextpos[4+i].rb = -1;
  }
  for( i=0; i< 16; i++) {
    box[i] = -1;
  }
}

ここまでは順調に来た。後は向きを考えるだけ。連結している矩形を並べ替えてみると以下のようになる。

初期状態は2の時右,3の時上,7の時上,8の時左,12の時右,13の時右を向いている。

以下の7の位置に注目すると,7から右上は0°回転,左上は90°回転,左下は180°回転,右下は240°回転する。

このことを考慮してfind()の引数に回転を加えた結果find()とmain()は以下のようになる。

void find( int level, int nexti, int nextbox, int rotate)
{
  visit[level] = nexti;
  if( level == 16) {
    // 出発点に戻ったか?
    if( nexti == visit[0]) {
      ps( "発見\n");
      for( int k=0; k<= level; k++) {
        ps( "%2d ", visit[k]);
      }
      ps( "\n");
    }
    return;
  }
  if( box[nextbox] >= 0) return;      // このBOXは既に訪問済み
  box[nextbox] = 1;
  // 2:右
  // 3:上
  // 7:上
  // 8:左
  // 12:右
  // 13:右
  if( (level == 2 && ((rotate+3)%4) != 0) ||
      (level == 3 && ((rotate+0)%4) != 0) ||
      (level == 7 && ((rotate+0)%4) != 0) ||
      (level == 8 && ((rotate+1)%4) != 0) ||
      (level == 12 && ((rotate+3)%4) != 0) || 
      (level == 13 && ((rotate+3)%4) != 0)) {
    box[nextbox] = -1;
    return;
  }
  rotate += 4- (rotate%4);      // 正規化
  // 右上,左上,左下,右下を順に調べる。
  if( nextpos[nexti].rt != -1) find( level+1, nextpos[nexti].rt, nextpos[nexti].rtbox, rotate+0);
  if( nextpos[nexti].lt != -1) find( level+1, nextpos[nexti].lt, nextpos[nexti].ltbox, rotate+1);
  if( nextpos[nexti].lb != -1) find( level+1, nextpos[nexti].lb, nextpos[nexti].lbbox, rotate+2);
  if( nextpos[nexti].rb != -1) find( level+1, nextpos[nexti].rb, nextpos[nexti].rbbox, rotate+3);
  box[nextbox] = -1;
}
int main( int argc, cstring argv[])
{
  init();
  int level = 0;
  for( int i=0; i< 25; i++) {
    visit[level] = i;
    if( nextpos[i].rt != -1) find( level+1, nextpos[i].rt, nextpos[i].rtbox, 0);
    if( nextpos[i].lt != -1) find( level+1, nextpos[i].lt, nextpos[i].ltbox, 1);
    if( nextpos[i].lb != -1) find( level+1, nextpos[i].lb, nextpos[i].lbbox, 2);
    if( nextpos[i].rb != -1) find( level+1, nextpos[i].rb, nextpos[i].rbbox, 3);
    visit[level] = -1;
  }
  return    0;
}

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

解速度