朝日新聞2006年10月20日のパズル横丁問題

問題

以下のように12個の飛び石がある。スタート地点(S)から2個または3個置きに左右に飛んで，全ての石を一度だけ訪問し最初の位置に戻るにはどうすれば良いか?

但し８の石は８番目に訪問すること。

解答への道(ヒント)

星２つ問題だけどプログラムだと簡単に解けてしまう問題。

ある場所nに注目するとnから次に行けるのはn+2,n+3,n-2,n-3の4点の何れか。

これをfind( )関数にすれば以下のようになる。

int visit[13];                  // 訪問しているか?履歴表示用にYesNoでなく,訪問時の歩数を設定

void find( int level, int pos)
{
  if( pos < 0 || pos > 12) return; // 右か左に行き過ぎ
  if( pos == 0) {               // Goal?
    // 他の地点を一度ずつ訪問しているか?
    for( int i=1; i< 13; i++) {
      if( !visit[i]) {
        return;
      }
    }
    ps( "Find\n");
    return;
  }
  if( visit[pos]) return;       // 既に訪問済み
  if( level == 8) {             // 8回目のジャンプ
    if( pos != 8) return;       // 8個目の石ではない
  }
  visit[pos]    = level;
  find( level+1, pos+2);        // 右に2歩
  find( level+1, pos+3);        // 右に3歩
  find( level+1, pos-2);        // 左に2歩
  find( level+1, pos-3);        // 左に3歩
  visit[pos]    = 0;
}

main( )からこれを呼び出して完了。

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

最近のインクジェットプリンタは速いのでビックリした。

私には「インクジェット＝遅い」というイメージがあったけど考えを改めねば。

解速度

即