プログラムの実行結果は以下の通り。プログラムはヒューリスティックな部分を削って再帰だけにしてしまった。
数字の割り当て 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; }