朝日新聞2005年7月15日のパズル横丁問題

問題

短歌の57577の上の句の17文字，下の句の14文字，全体31文字が回文になっている。どんな短歌か？

解答への道(ヒント)

一瞬難しそうに見える問題なんだけど実は簡単という問題。

だけどプログラムで解答を出すとこれであっているの?と不安になってしまう。

17文字が回文になっているので，最初の1文字にＡを設定すると，

上の句は「Ａ□□□□□□□□□□□□□□□Ａ」となる。

全体でも回文なので，下の句と合わせると１７文字目のＡがまた別の場所の文字を決定することになる。

これをプログラムすると以下のようになる。

void decide( 位置, 値) {
  if( 位置の文字が確定しているなら) return;
  位置の文字を値に設定する。
  if( 位置が上の句) {
    decide( 上の句が回文になる新しい位置, 値);
  }
  else {
    decide( 下の句が回文になる新しい位置, 値);
  }
  decide( 全体がが回文になる新しい位置, 値);
}

この関数を以下のようなmainで呼び出す。

int main( int argc, cstring argv[])
{
  int           n = 0;          // 割り当て文字
  for( int i=0; i< 31; i++) {
    if( !a[i]) decide( i, ++n); // 文字が決まっていなければ「ア」から割り当て
  }
  for( i=0; i< 31; i++) {
    ps( "%-.2s ", "・アイウエオカキクケコサシスセソタチツテトナニヌネノハヒフヘホマミムメモヤユヨラリルレロワヲン"+a[i]*2);
  }
  return    0;
}

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

あれ?と思うような解ですね。でもパズルのタイトルが「アアア星人の短歌」だからあっているでしょう。

解速度

即