「ぶどうの房パズル」というものを知っているだろうか? どういうものかを説明するには解答例を出してしまうのがてっとりばやいだろう。 まずは以下の図を見て欲しい。
9 | 3 | 10 | 8 | |||
6 | 7 | 2 | ||||
1 | 5 | |||||
4 |
左右に隣りあう数値の差の絶対値が下にある数値になっていることがわかる。 また、 1 から 10 までの数値を全て一回づつ使っている。
5 段の場合で考えると解答はこうなる。
6 | 14 | 15 | 3 | 13 | ||||
8 | 1 | 12 | 10 | |||||
7 | 11 | 2 | ||||||
4 | 9 | |||||||
5 |
つまり、段の数を N とすると 1 から (N+1)*N/2 までの数値を使うことになる。
私が学生の頃 (10年くらい前) にどういうわけか、このパズルの解を導くプログラムを書くのが周囲で流行した。
パズルを考案したジョージ・シチェルマンは 6, 7, 8 段の場合には解が無いことを確認したそうだが、私は PC を使って 9, 10, 11, 12, 13 段の場合にも解が無いことを確認した。 13 段の場合を確認するのに 4 日くらいかかったと思う。 (学校にあった PC なので詳細なスペックは忘れたがクロックは 1GHz だったように記憶している。) 最近の上等なパソコンなら 1 日あれば終わるだろう。
この話に結論はない。 ただの思い出だが、初心者がプログラミングの練習をするネタくらいにはなるだろう。
Document ID: d4bf738a6282e912d15198f938d89af8