|
5×5 のマス目の中央 (図の ● の位置) に，チェスのナイトの駒がおいてあります。
ここから出発して，左上隅のマス目 (図の ● の位置) に最短経路で進みたいのですが，
(1) 何手で到達できますか。
(2) また，その手数で進む最短経路は何通りありますか。
注意: ナイトの駒の動きは，将棋での桂馬の動きを上下左右にひろげたものです。すなわち，1 手目は図の ● の位置 (8 ヶ所) のいずれかに動かせます。
|
| ▼ 解説 |
|
次のように，マス目に番号をつける。
| 1 | 2 | 3 | 4 | 5 |
| 6 | 7 | 8 | 9 | 10 |
| 11 | 12 | 13 | 14 | 15 |
| 16 | 17 | 18 | 19 | 20 |
| 21 | 22 | 23 | 24 | 25 |
(1) まず，出発点である 13 のマス目に "0" と書く。
次に，13 から 1 手で進めるマス目 (8 ヶ所) に "1" と書く。
そして，"1" と書かれたマス目から次の 1 手で進めるマス目 (8 ヶ所) に "2" と書く。ただし，すでに手数の書き込んであるマス目はのぞく。
さらに進めていくと，3 手で行けるマス目は 4 ヶ所あり，4 ヶ所ある四隅には 4 手目に到達できる。(手数を書き込んだ図は下の通り)
| 4 | 1 | 2 | 1 | 4 |
| 1 | 2 | 3 | 2 | 1 |
| 2 | 3 | 0 | 3 | 2 |
| 1 | 2 | 3 | 2 | 1 |
| 4 | 1 | 2 | 1 | 4 |
(2) (1) で書き込んだ図を利用して考えると，次の 16 通りある。
13−2−9−12−1，13−2−11−8−1，13−4−15−8−1，
13−6−3−12−1，13−6−17−8−1，13−10−3−12−1，
13−10−19−8−1，13−10−19−12−1，13−16−23−12−1，
13−20−9−12−1，13−20−23−12−1，13−22−11−8−1，
13−22−19−8−1，13−22−19−12−1，13−24−15−8−1，
13−24−17−8−1
|
|
|
|
