訪問順は以下の通り。
プログラムの実行結果は以下の通り。
1 2 8 9 12 15 11 7 5 3 16 6 10 4 13 14
プログラムのソースは以下の通り。
#include "puzutl.h"
int P[4][4] = { // 進むべき方向を示す,1:東,2:東南東,3:南,4:南南西,...
{ 1, 3, 1, 4},
{ 2, 2, 5, 6},
{ 1, 3, 6, 7},
{ 8, 6, 1, 6},
};
int once[4][4]; // 訪問順を記録する,訪問済みかどうかの判定にも利用する
YesNo exist( int row, int col) // [row,col]が有効なマスか?
{
if( row < 0) return NO;
if( row >= 4) return NO;
if( col < 0) return NO;
if( col >= 4) return NO;
return YES;
}
void goal()
{
for( int row=0; row<4; row++) {
for( int col=0; col< 4; col++) {
ps( "%3d ", once[row][col]);
}
ps( "\n");
}
}
void find( int level, int row, int col)
{
if( !exist(row,col)) return; // 無くても良い
if( row == 0 && col == 0 && level == 17) { goal(); return;} // level+1しながら全ての点を通過してきた?
if( once[row][col]) return; // この位置は既に訪問済み?
once[row][col] = level; // 訪問したぞ
int tmprow = row, tmpcol = col, drow, dcol;
switch( P[row][col]) { // 次に進む方向を決める
case 1:drow = 0; dcol = 1; break;
case 2:drow = 1; dcol = 1; break;
case 3:drow = 1; dcol = 0; break;
case 4:drow = 1; dcol =-1; break;
case 5:drow = 0; dcol =-1; break;
case 6:drow =-1; dcol =-1; break;
case 7:drow =-1; dcol = 0; break;
case 8:drow =-1; dcol = 1; break;
default:
pe( "Program Error\n");exit(16);
}
tmprow += drow; // 次の訪問位置
tmpcol += dcol;
while( exist(tmprow,tmpcol)) { // 次の訪問位置が存在するか?
find( level+1, tmprow, tmpcol); // その位置を試してみる
tmprow += drow;
tmpcol += dcol;
}
once[row][col] = 0; // 訪問を取り消す
}
int main( int argc, const char* argv[])
{
find( 1/*level*/, 0/*row*/, 0/*col*/);
return 0;
}