朝日新聞2005年9月9日パズル横丁解答

プログラムの実行結果は以下の通り。

 1=> 1 : 183.053 秒
 1=> 2 : 184.735 秒
 1=> 3 : 189.132 秒
 1=> 4 : 183.244 秒
 1=> 5 : 183.564 秒
 1=> 6 : 187.63 秒
 1=> 7 : 191.795 秒
 1=> 8 : 189.593 秒
 1=> 9 : 185.737 秒
 1=>10 : 183.504 秒
 1=>11 : 182.853 秒
 1=>12 : 183.574 秒
 1=>13 : 183.634 秒
 1=>14 : 182.953 秒
 1=>15 : 182.803 秒
 1=>16 : 183.614 秒
 1=>17 : 183.824 秒
 1=>18 : 184.005 秒
 2=> 2 : 183.614 秒
 2=> 3 : 183.604 秒
 2=> 4 : 185.026 秒
 2=> 5 : 183.414 秒
 2=> 6 : 184.545 秒
 2=> 7 : 184.425 秒
 2=> 8 : 184.285 秒
 2=> 9 : 184.105 秒
 2=>10 : 184.585 秒
 2=>11 : 183.774 秒
 2=>12 : 184.275 秒
 2=>13 : 184.346 秒
 2=>14 : 183.994 秒
 2=>15 : 183.654 秒
 2=>16 : 187.49 秒
 2=>17 : 185.627 秒
 2=>18 : 192.997 秒
 3=> 3 : 191.345 秒
 3=> 4 : 185.327 秒
 3=> 5 : 184.345 秒
 3=> 6 : 181.671 秒
 3=> 7 : 180.69 秒
 3=> 8 : 181.361 秒
 3=> 9 : 180.67 秒
 3=>10 : 187.419 秒
 3=>11 : 181.962 秒
 3=>12 : 180.87 秒
 3=>13 : 180.66 秒
 3=>14 : 180.439 秒
 3=>15 : 180.399 秒
 3=>16 : 184.906 秒
 3=>17 : 192.277 秒
 3=>18 : 183.033 秒
 4=> 4 : 174.22 秒
 4=> 5 : 174.451 秒
 4=> 6 : 174.321 秒
 4=> 7 : 174.07 秒
 4=> 8 : 180.31 秒
 4=> 9 : 178.747 秒
 4=>10 : 179.598 秒
 4=>11 : 178.807 秒
 4=>12 : 180.68 秒
 4=>13 : 180.019 秒
 4=>14 : 178.667 秒
 4=>15 : 178.616 秒
 4=>16 : 179.859 秒
 4=>17 : 183.274 秒
 4=>18 : 177.495 秒
 5=> 5 : 131.158 秒
 5=> 6 : 122.006 秒
 5=> 7 : 128.374 秒
 5=> 8 : 122.456 秒
 5=> 9 : 126.472 秒
 5=>10 : 125.11 秒
 5=>11 : 123.678 秒
 5=>12 : 124.389 秒
 5=>13 : 129.346 秒
 5=>14 : 127.603 秒
 5=>15 : 127.173 秒
 5=>16 : 124.389 秒
 5=>17 : 132.35 秒
 5=>18 : 121.515 秒
 6=> 6 : 128.605 秒
 6=> 7 : 129.096 秒
 6=> 8 : 128.414 秒
 6=> 9 : 129.166 秒
 6=>10 : 130.658 秒
 6=>11 : 131.84 秒
 6=>12 : 134.353 秒
 6=>13 : 131.008 秒
 6=>14 : 134.171 秒
 6=>15 : 139.26 秒
 6=>16 : 129.116 秒
 6=>17 : 129.096 秒
 6=>18 : 129.186 秒
 7=> 7 : 188.16 秒
 7=> 8 : 197.294 秒
 7=> 9 : 186.558 秒
 7=>10 : 187.179 秒
 7=>11 : 186.008 秒
 7=>12 : 187.319 秒
 7=>13 : 187.48 秒
 7=>14 : 186.758 秒
 7=>15 : 190.644 秒
 7=>16 : 191.105 秒
 7=>17 : 188.241 秒
 7=>18 : 188.04 秒
 8=> 8 : 159.319 秒
 8=> 9 : 159.9 秒
 8=>10 : 160.01 秒
 8=>11 : 160.02 秒
 8=>12 : 161.172 秒
 8=>13 : 168.102 秒
 8=>14 : 168.933 秒
 8=>15 : 162.784 秒
 8=>16 : 163.956 秒
 8=>17 : 165.387 秒
 8=>18 : 169.504 秒
 9=> 9 : 128.795 秒
 9=>10 : 125.521 秒
 9=>11 : 125 秒
 9=>12 : 125.52 秒
 9=>13 : 125.39 秒
 9=>14 : 125.611 秒
 9=>15 : 124.92 秒
 9=>16 : 126.271 秒
 9=>17 : 125.14 秒
 9=>18 : 127.243 秒
10=>10 : 135.625 秒
10=>11 : 135.675 秒
10=>12 : 136.166 秒
10=>13 : 136.636 秒
10=>14 : 135.776 秒
10=>15 : 137.277 秒
10=>16 : 137.227 秒
10=>17 : 138.079 秒
10=>18 : 151.187 秒
11=>11 : 154.432 秒
11=>12 : 130.368 秒
11=>13 : 129.386 秒
11=>14 : 133.161 秒
11=>15 : 141.414 秒
11=>16 : 129.856 秒
11=>17 : 131.97 秒
11=>18 : 129.496 秒
12=>12 : 192.067 秒
12=>13 : 195.451 秒
12=>14 : 194.499 秒
12=>15 : 191.005 秒
12=>16 : 191.425 秒
12=>17 : 191.616 秒
12=>18 : 192.346 秒
13=>13 : 191.576 秒
13=>14 : 192.026 秒
13=>15 : 193.478 秒
13=>16 : 195.451 秒
13=>17 : 195.021 秒
13=>18 : 202.23 秒
14=>14 : 139.02 秒
14=>15 : 136.607 秒
14=>16 : 132.59 秒
14=>17 : 134.153 秒
14=>18 : 133.572 秒
15=>15 : 122.777 秒
15=>16 : 120.463 秒
15=>17 : 118.46 秒
15=>18 : 120.023 秒
16=>16 : 193.829 秒
34,  41 : 16 11  6  2  1  3  4  5  1  2  7 12 11 10  5  6  7 12 16 15 10  9  4  3  8 13 14  9  8 13 17 14 15 18 17 <=これが解
16=>17 : 195.271 秒
16=>18 : 194.529 秒
17=>17 : 195.331 秒
17=>18 : 195.421 秒
18=>18 : 211.254 秒
合計探索時間 : 28062 秒

34の道を通り,経路長は41,始点は16で,終点が17。これを図示すると以下のようになる。

プログラムのソースは以下の通り。

#include "puzutl.h"

int s=0;                        // 出発点
int g=0;                        // 終点
#define S 18                    // 交差点の数
int P[S+1][S+1];                // 交差点間の距離
int L[S+1][S+1];                // 道を通過した回数
int once[1000];
int visit[1000];
int minLength = 9999;

void dump( int level, int length) {
  ps( "%2d, %3d : ", level, length);
  for( int i=0; i<= level; i++) {
    ps( "%2d ", visit[i]);
  }
  ps( "\n");
}

void findGoal( int level, int p)
{
  visit[level] = p;
  
  if( once[p] > 1) return;      // 2回までは同じ地点を通るのを許す
  if( p == g && level >= 34) {  // level >= 34 は全ての道を通過してなければ条件をクリア出来ない
    YesNo ynFind = YES;
    for( int i=0; i<= S; i++) for( int j=i; j<= S; j++) if( P[i][j] && !L[i][j] && !L[j][i]) { ynFind = NO; break;}
    if( ynFind) {
      // 今までの経路より短いことを確認する。
      int length = 0;
      for( i=0; i< level; i++) {
        length += P[visit[i]][visit[i+1]];
      }
      if( length < minLength) { // 以前より短い経路のみ表示する
        dump( level, length);
        minLength = length;
      }
      return;
    }
  }
  once[p]++;                    // 通過回数
  for( int next=1; next<= S; next++) { // pから到達可能な全ての地点を調べる
    if( !P[p][next]) {
      continue; // 到達出来ない地点は無視する
    }
    if( level > 0 && visit[level-1] == next) {
      continue;                 // 直前に戻ることはしない(多分こういうルートは無いはず)
    }
    if( once[next] && P[p][next] > 1 && (L[p][next]+L[next][p]) > 0) {
      continue;                 // 長さ2以上の道は二度通らない
    }
    L[p][next]++;
    findGoal( level+1, next);
    L[p][next]--;
  }
  once[p]--;
}

int main( int argc, const char* argv[])
{
  P[1][2] = 1;                  // 交差点間の距離
  P[1][3] = 3;
  P[1][5] = 1;
  P[2][6] = 1;
  P[2][7] = 2;
  P[3][4] = 1;
  P[3][8] = 1;
  P[4][5] = 1;
  P[4][9] = 1;
  P[5][6] = 1;
  P[5][10] = 1;
  P[6][7] = 1;
  P[6][11] = 1;
  P[7][12] = 1;
  P[8][9] = 1;
  P[8][13] = 1;
  P[9][10] = 1;
  P[9][14] = 1;
  P[10][11] = 1;
  P[10][15] = 1;
  P[11][12] = 1;
  P[11][16] = 1;
  P[12][16] = 4;
  P[13][14] = 1;
  P[13][17] = 2;
  P[14][15] = 1;
  P[14][17] = 1;
  P[15][16] = 1;
  P[15][18] = 1;
  P[17][18] = 1;
  for( int i=0; i<= S; i++) for( int j=0; j<= S; j++) if( P[i][j]) P[j][i] = P[i][j];
  double totalTime = 0;         // 合計処理時間
  for( s=1; s<= S; s++) {       // 全ての始点,終点の組合せを試す
    for( g=s; g<= S; g++) {     // 終点→始点は始点→終点で求まっているはず
      ProcTime pt; pt.start();  // 各組合わせの処理時間
      findGoal( 0, s);
      pt.end();
      ps( "%2d=>%2d : %g 秒\n", s, g, pt.sec());
      totalTime += pt.sec();
    }
  }
  ps( "合計探索時間 : %g 秒\n", totalTime);
  return 0;
}