特定の物(動物)を訪れながらGOALを目指す。朝日新聞土曜日の朝刊BeのEntertainment編に出題される(beパズル)。
ごくまれにしか出題されない。以下の問題は2004年4月24日に出題された。
実際の新聞では目の部分は表示されています。
これをコンピュータで解いてみよう。これを解くには迷路問題用に地点に番号を振って，番号間の移動を表で表現し後はコンピュータで経路を求める。プログラムは迷路の一般的な解法プログラムを利用する。
直感的に以下のように番号を振ることを考えてしまう。
しかし，実はこのような番号付けはダメで，実際は交差点に番号を振る必要がある。
各地点間の値を人:1, 鳥:2, 蛇:3, 地点間:9 とし，地点間の移動表を作成する。
例えば，1⇒2は人なので1,6⇒7は鳥なので2, 6⇒13は蛇なので3, 8⇒14は何も無いので9とする。
P[1][2]=1; P[6][7]=2; P[6][13]=3; P[8][14]=9;
この問題を解くプログラムは以下の通り。
#include <stdio.h>
#include <stdlib.h>
int s=1;
int g=25;
#define S 25
int P[S+1][S+1];
int once[S+1];
int visit[S+1];
void findGoal( int level, int p)
{
visit[level] = p;
if( once[p]) return; // 一度通った地点
if( level > 1) {
int L = level;
int nowType = P[visit[L-1]][visit[L]];
int prevType;
while( L-2 >= 0 && (prevType=P[visit[L-2]][visit[L-1]]) == 9) {
// 地点間に何も無いとき前の物を求める
L--;
}
if( nowType == 3 && prevType == 1) return; //
人の後ろは蛇はダメ
if( nowType == 1 && prevType == 2) return; //
鳥の後ろは人はダメ
if( nowType == 2 && prevType == 3) return; //
蛇の後ろは鳥はダメ
}
if( p==g) {
printf( "FindGoal\n");
for( int i=0; i<= level; i++) {
printf( "%d ", visit[i]);
}
printf( "\n");
return;
}
once[p] = 1;
for( int next=1; next<= S; next++) { // pから到達可能な全ての地点を調べる
if( !P[p][next]) {
continue; // 到達出来ない地点は無視する
}
findGoal( level+1, next);
}
once[p] = 0;
}
int main( int argc, const char* argv[])
{
P[1][2]=1;
P[1][6]=1;
P[2][3]=1;
P[2][7]=9;
P[3][4]=2;
P[3][9]=3;
P[4][5]=1;
P[4][10]=3;
P[5][12]=2;
P[6][7]=2;
P[6][13]=3;
P[7][8]=3;
P[8][9]=1;
P[8][14]=9;
P[9][10]=2;
P[10][11]=2;
P[11][12]=3;
P[11][15]=1;
P[12][18]=1;
P[13][19]=2;
P[13][22]=3;
P[14][19]=2;
P[14][15]=2;
P[15][16]=9;
P[16][17]=2;
P[16][21]=3;
P[17][18]=1;
P[18][25]=3;
P[19][20]=9;
P[20][21]=3;
P[20][22]=1;
P[21][24]=1;
P[22][23]=2;
P[23][24]=2;
P[24][25]=3;
for( int i=0; i<= S; i++) for( int j=0; j<= S; j++) if( P[i][j]) P[j][i] = P[i][j];
// 地点間の移動は双方向なので
findGoal( 0, s);
return 0;
}
プログラムを実行すると以下の結果を得る。
FindGoal
1 6 7 8 9 10 11 12 18 17 16 21 20 22 23 24 25
これを図示すると以下のようになる。問題は「出会った蛇の数」であるが，そこまでプログラムには解かせようとは思わない。21⇒20には蛇が2匹いる。これをプログラムで表現することを考えたら目で見て判断する方がずっと速い。
同じような問題が2003年11月22日にも出題されているが，そちらは3種類が，人，道具，動物で，「人⇒道具⇒動物⇒人⇒道具⇒動物…」の順に移動しなければならないという制約が付いていた。