朝日新聞2007年1月26日パズル横丁解答

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

Find 0 1 2 8 5 3 4 6 9 7 , [5]:3 => [8]:9 => [7]:6 => [3]:8 => [1]:1 => [2]:2 => [4]:5 => [9]:7 => [6]:4 
Find 0 7 2 8 5 1 6 3 9 4 , [5]:1 => [6]:6 => [2]:2 => [4]:5 => [9]:4 => [3]:8 => [1]:7 => [8]:9 => [7]:3 

これを図にすると以下の通り。

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

#include "puzutl.h"

YesNo used[10];

void check( int istart, int a, int b, int c, int d, int e, int f)
{
  int           number[10] = { 0, a, 2, b, 5, c, d, e, 9, f};
  int           visit[10] = {0}; // 訪問した?
  int           ipos = istart;  // 最初の訪問地
  int           cnt = 0;        // 訪問回数
  while( visit[ipos] == 0) {    // 一回も訪れていない場所のみ訪問できる
    visit[ipos] = 1;            // 初訪問
    ipos        = ipos + number[ipos]; // 次の訪問地
    ipos        %= 10;          // 円の周りを回るので
    cnt++;                      // 訪問回数
    if( ipos == 0) break;       // ちょうどゴールの位置を訪問
  }
  if( ipos == 0 && cnt == 9) {  // ちょうどゴールを9回目で訪問した場合が答え
    ps( "Find ");
    for( int i=0; i< 10; i++) {
      ps( "%d ", number[i]);
    }
    ps( ", ");
    ipos        = istart;       // もう一度同じ処理を出力用に実行する
    while( number[ipos] != 0) {
      ps( "[%d]:%d ", ipos, number[ipos]);
      ipos      += number[ipos];
      ipos      %= 10;
      if( ipos != 0) ps( "=> ");
    }
    ps( "\n");
  }
}

int main( int argc, cstring argv[])
{
  used[2] = used[5] = used[9] = YES; // 2,5,9は既に盤面に配置されている
  for( int a=1; a< 10; a++) {   // 1〜9の数字を割り当てる
    if( used[a]) continue;
    used[a] = YES;
    for( int b=1; b< 10; b++) {
      if( used[b]) continue;
      used[b] = YES;
      for( int c=1; c< 10; c++) {
        if( used[c]) continue;
        used[c] = YES;
        for( int d=1; d< 10; d++) {
          if( used[d]) continue;
          used[d] = YES;
          for( int e=1; e< 10; e++) {
            if( used[e]) continue;
            used[e] = YES;
            for( int f=1; f< 10; f++) {
              if( used[f]) continue;
              used[f] = YES;
              for( int istart=1; istart<= 9; istart++) {
                check( istart, a, b, c, d, e, f); // [0]をゴールとみなし，[1]〜[9]の位置からスタートしてうまく行くか調べる
              }
              used[f] = 0;
            }
            used[e] = 0;
          }
          used[d] = 0;
        }
        used[c] = 0;
      }
      used[b] = 0;
    }
    used[a] = 0;
  }
  return    0;
}