朝日新聞2004年3月13日パズルパーク問題

博物館に縦,横4部屋ずつ16部屋ある。入り口は一つで,全16部屋を一度だけ訪問し出るには出口をどこにして,経路をどうすれば良いか。

但し順路は一つだけしかないようにする。

解答への考え方(ヒント)

16の部屋を mat[行][列] で示す。入り口は mat[3][1] となる。

虱潰しでやりましょうか。

Find関数は以下のようになる。

Find( int 行, int 列)
{
    if( 全部屋到達() ) { 解答 }
    if( 部屋が未達( 行+0, 列-1)) { Find( 行+0, 列-1) } // 左の部屋
    if( 部屋が未達( 行+0, 列+1)) { Find( 行+0, 列+1) } // 右の部屋
    if( 部屋が未達( 行-1, 列+0)) { Find( 行-1, 列+0) } // 上の部屋
    if( 部屋が未達( 行+1, 列+0)) { Find( 行+1, 列+0) } // 下の部屋
}

最初の呼び出しは Find( 3, 1)

これだと幾つも解答が見つかってしまう。順路が一通りという制約を加えるにはどうすれば良いか。

解候補が見つかる毎に1加え，Find()を全て終了後，解候補が1つしかない部屋を探す。

if( 全部屋到達() ) { 解候補数[行][列]++ }

Find 終了後は以下のように本当の解を探す。

for( row=0; row< 4; row++) {
    for( col=0; col< 4; col++) {
        if( 解候補数[row][col] == 1) { 解答 }
    }
}

Find() を再利用し解が判っているとき，順路を出力する。

解速度

即