以下のように円卓上に10個の丸がある。そのうち一つがゴールで残り9個は1〜9の数字が書いてある。
ある丸からスタートし，書いてある数字の数だけ時計回りに円卓上を移動する。
2,5,9は既に以下のようになっている。全ての丸を一度だけ訪れゴールに到達するには。
星3つ問題だけど，プログラムを作って解くと簡単な問題。
問題には「まずは「スタートの○がどこになるのか」から考えてみましょう」ってあるけど，プログラマは「まずはプログラムを作りましょう」だ。
考える間も無くプログラムを作れる問題なので早速プログラムを作る。
既に10個の丸のうち4個に値が設定してあるので，6個の丸に6個の数字(a〜f)を割り当てる。
数字の割り当て問題をコピーして，2,5,9は既に設定してあると考えれば以下のようになる。
YesNo used[10];
void check( int istart, int a, int b, int c, int d, int e, int f)
{
int number[10] = { 0, a, 2, b, 5, c, d, e, 9, f};
int visit[10] = {0}; // 訪問した?
int ipos = istart; // 最初の訪問地
int cnt = 0; // 訪問回数
while( visit[ipos] == 0) { // 一回も訪れていない場所のみ訪問できる
…
}
if( ipos == 0 && cnt == 9) { // ちょうどゴールを9回目で訪問した場合が答え
…見つけた…
}
}
int main( int argc, cstring argv[])
{
used[2] = used[5] = used[9] = YES; // 2,5,9は既に盤面に配置されている
for( int a=1; a< 10; a++) { // 1〜9の数字を割り当てる
if( used[a]) continue;
used[a] = YES;
for( int b=1; b< 10; b++) {
if( used[b]) continue;
used[b] = YES;
for( int c=1; c< 10; c++) {
if( used[c]) continue;
used[c] = YES;
for( int d=1; d< 10; d++) {
if( used[d]) continue;
used[d] = YES;
for( int e=1; e< 10; e++) {
if( used[e]) continue;
used[e] = YES;
for( int f=1; f< 10; f++) {
if( used[f]) continue;
used[f] = YES;
for( int istart=1; istart<= 9; istart++) {
check( istart, a, b, c, d, e, f); // [0]をゴールとみなし，[1]〜[9]の位置からスタートしてうまく行くか調べる
}
used[f] = 0;
}
used[e] = 0;
}
used[d] = 0;
}
used[c] = 0;
}
used[b] = 0;
}
used[a] = 0;
}
return 0;
}
答えは2件出力されました。
先日家に帰ったら車が無かった。車で出かけて帰りに近所のスーパーに寄ってそのまま歩いて帰ってきたから。
今日は車で出かけて帰りに良く行く別の大型スーパーに寄った。結構強い雨だったのでいつもは地上の駐車場に駐めるのを地下駐車場に駐めて，帰りに外に出る直前，外に雨が降っているのを見て気づいた。「今日は雨だから地下に駐車したんだ」。
習慣というのは恐ろしいものだ。習慣だけなら良いのだが…
解速度
即