プログラムの実行結果は以下の通り。
発見 17 21 15 11 5 1 7 3 9 13 19 23 17 11 7 13 17
これを絵にすると以下の通り。
プログラムのソースは以下の通り。
#include "puzutl.h"
struct struct_nextpos {
int rt, lt, lb, rb; // 0〜24
int rtbox, ltbox, lbbox, rbbox; // 0〜15
} nextpos[25];
int visit[16+1]; // 訪問位置(0〜24)
int box[16+1]; // 踏んだ矩形(0〜15),初期値を-1に設定しておく
void init()
{
for( int i=0; i< 25; i++) {
nextpos[i].rt = i-5+1;
nextpos[i].lt = i-5-1;
nextpos[i].lb = i+5-1;
nextpos[i].rb = i+5+1;
nextpos[i].rtbox = i/5*4 + i%5 - 4;
nextpos[i].ltbox = i/5*4 + i%5 - 4 - 1;
nextpos[i].lbbox = i/5*4 + i%5 - 1;
nextpos[i].rbbox = i/5*4 + i%5;
}
for( i=0; i< 5; i++) {
nextpos[i].rt = -1;
nextpos[i].lt = -1;
nextpos[20+i].lb = i+5-1;
nextpos[20+i].rb = i+5+1;
}
for( i=0; i< 25; i+=5) {
nextpos[4+i].rt = -1;
nextpos[i].lt = -1;
nextpos[i].lb = -1;
nextpos[4+i].rb = -1;
}
for( i=0; i< 16; i++) {
box[i] = -1;
}
}
void find( int level, int nexti, int nextbox, int rotate)
{
visit[level] = nexti;
if( level == 16) {
// 出発点に戻ったか?
if( nexti == visit[0]) {
ps( "発見\n");
for( int k=0; k<= level; k++) {
ps( "%2d ", visit[k]);
}
ps( "\n");
}
return;
}
if( box[nextbox] >= 0) return; // このBOXは既に訪問済み
box[nextbox] = 1;
// 2:右
// 3:上
// 7:上
// 8:左
// 12:右
// 13:右
if( (level == 2 && ((rotate+3)%4) != 0) ||
(level == 3 && ((rotate+0)%4) != 0) ||
(level == 7 && ((rotate+0)%4) != 0) ||
(level == 8 && ((rotate+1)%4) != 0) ||
(level == 12 && ((rotate+3)%4) != 0) ||
(level == 13 && ((rotate+3)%4) != 0)) {
box[nextbox] = -1;
return;
}
rotate += 4- (rotate%4); // 正規化
// 右上，左上，左下，右下を順に調べる。
if( nextpos[nexti].rt != -1) find( level+1, nextpos[nexti].rt, nextpos[nexti].rtbox, rotate+0);
if( nextpos[nexti].lt != -1) find( level+1, nextpos[nexti].lt, nextpos[nexti].ltbox, rotate+1);
if( nextpos[nexti].lb != -1) find( level+1, nextpos[nexti].lb, nextpos[nexti].lbbox, rotate+2);
if( nextpos[nexti].rb != -1) find( level+1, nextpos[nexti].rb, nextpos[nexti].rbbox, rotate+3);
box[nextbox] = -1;
}
int main( int argc, cstring argv[])
{
init();
int level = 0;
for( int i=0; i< 25; i++) {
visit[level] = i;
if( nextpos[i].rt != -1) find( level+1, nextpos[i].rt, nextpos[i].rtbox, 0);
if( nextpos[i].lt != -1) find( level+1, nextpos[i].lt, nextpos[i].ltbox, 1);
if( nextpos[i].lb != -1) find( level+1, nextpos[i].lb, nextpos[i].lbbox, 2);
if( nextpos[i].rb != -1) find( level+1, nextpos[i].rb, nextpos[i].rbbox, 3);
visit[level] = -1;
}
return 0;
}
(2005.2.26)この申込み期限が2月29日って書いてあったんだけど，今日の新聞で「前回パズルの解答応募は３月１日必着です。」って書いてある。誰かがツッコミを入れたんだろうなー。2月29日ってことは3年後ですか?なんてね。私は家族に2月29日生まれがいるので，2月29日がなくても気にならない。気にすると本当に誕生日が4年に一度になってしまうので。