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

プログラムの実行結果は以下の通り。プログラムはヒューリスティックな部分を削って再帰だけにしてしまった。

数字の割り当て
 6  7  1  2  3  4  1 
 5  2  1  7  6  5  2 
 4  3  6  7  1  2  3 
 3  4  5  7  6  3  4 
 2  1  1  7  5  4  5 
 6  7  2  6  3  2  6 
 5  4  3  5  4  1  7 
道順
27 28 29 30 31 32  1 
26 37 36 35 34 33  2 
25 38 41 42 43 44  3 
24 39 40 49 48 45  4 
23 22 15 14 47 46  5 
20 21 16 13 10  9  6 
19 18 17 12 11  8  7 

図にすると以下の通り。右上の1から始まり,真ん中の7で終わる。

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

#include "puzutl.h"

const int M = 7;
int mat[M][M] = {               // 初期状態
  { 6, 0, 0, 2, 0, 0, 0},
  { 0, 2, 0, 0, 6, 0, 2},
  { 0, 0, 6, 0, 0, 2, 0},
  { 0, 0, 0, 0, 6, 0, 0},
  { 2, 0, 0, 0, 0, 0, 0},
  { 6, 0, 2, 6, 0, 2, 6},
  { 0, 0, 0, 0, 0, 0, 0},
};
YesNo visit[M][M];
int history[M*M+1];             // row*M+col を記録する

YesNo exist( int row, int col)
{
  if( row < 0 || row >= M) return    NO;
  if( col < 0 || col >= M) return    NO;
  return    YES;
}

void dump()                     // 結果を出力
{
  int           row, col, val = 0;
  int           v[M][M], u[M][M];
  for( int i=0; i< M*M; i++) {
    row = history[i]/M;
    col = history[i]%M;
    v[row][col] = (val % M)+1;  // 矩形内の数字の配置
    u[row][col] = val+1;        // 道順
    val++;
  }
  ps( "数字の割り当て\n");
  for( row=0; row< M; row++) {
    for( col=0; col< M; col++) {
      ps( "%2d ", v[row][col]);
    }
    ps( "\n");
  }
  ps( "道順\n");
  for( row=0; row< M; row++) {
    for( col=0; col< M; col++) {
      ps( "%2d ", u[row][col]);
    }
    ps( "\n");
  }
}

void find( int level, int row, int col, int val)
{
  if( val > M) val = 1;         // 7より大きくなったら1に戻る
  if( !exist(row,col)) return;  // 存在しない場所を指定されたら困る
  if( visit[row][col]) return;  // 既に訪問している
  if( mat[row][col] && mat[row][col] != val) return; // 既に値が設定してある
  history[level++]= row*M+col;
  if( level >= M*M) {
    dump();
    return;
  }
  visit[row][col] = YES;
  find( level, row-1, col+0, val+1);
  find( level, row+1, col+0, val+1);
  find( level, row+0, col-1, val+1);
  find( level, row+0, col+1, val+1);
  visit[row][col] = NO;
}

int main( int argc, cstring argv[])
{
  int           row, col;
  for( row=0; row< M; row++) {
    for( col=0; col< M; col++) {
      if( !mat[row][col]) {     // 値が設定されていない場所から始める(2,6が設定されているので)
        find( 0/*level*/, row, col, 1/*val*/);
      }
    }
  }
  return    0;
}