まずチェス盤に図のように１〜９の番号をつけます。
◆石川県 マイマイプー さんからの解答。
まずチェス盤に図のように１〜９の番号をつけます。
それぞれのマス目から次のマス目への移動可能な位置は次のように表すことができます。
【問１】
上の図に最初と最後のナイトの位置を書き加えます。
ナイトを交換するためには、おのおののナイトを４つずつ右または左に移動するのが最少であることが分かります。
したがって４×４＝１６手が必要です。
【問２】
ナイトの位置は図のようになります。
ところがナイトが円周上で並んでいる順序を変えることができないことはすぐに分かります。
したがって交換は不可能です。
◆神奈川県 今村 義彦さんからの解答。
【問３】
試行錯誤的な発見的手法です。
もっと手数が短い方法があるかもしれません。
問１と２の解答に習い、桝目に以下のように番号をふる。
| １ | ５ | ９ |
| ２ | ６ | 10 |
| ３ | ７ | 11 |
| ４ | ８ | 12 |
最初に配置する駒（ナイト）の位置は黒が１，５，９、青が４，８，１２である。
また、黒をA、青をBとする。
そして、再び問１，２の解答に習い、１２個の頂点をもつグラフを以下のように作成する。
1---7---9 | | 10--8---2 | | 3---5--11 | | 12--6---4初期状態は１，５，９にAが４，８，１２にBがいる。
次に、状態を遷移させる作業を以下のように記述する。
i,j,A(or B)
但し、(1 ≦ i,j ≦ 12)であり、iは現在の駒の位置を、ｊは移動後の駒の位置を、最後のAは駒の名前をあらわすことにする。
例えば、1,10,Aとは、Aの駒が1の位置から10の位置に移動することをあらわす。
（Bの駒でも同様である。）
この考え方で試してみると、筆者は２２回でAとBの駒すべてを入れ替えることができた。
以下にその方法を示す。step-1 1,10,A
step-2 10,3,A
step-3 4,11,B
step-4 11,2,B
step-5 9,7,A
step-6 7,1,A
step-7 1,10,A
step-8 2,9,B
step-9 9,7,B
step-10 7,1,B
step-11 8,2,B
step-12 2,9,B
step-13 10,8,A
step-14 5,11,A
step-15 11,4,A
step-16 4,6,A
step-17 3,5,A
step-18 5,11,A
step-19 11,4,A
step-20 12,3,B
step-21 3,5,B
step-22 6,12,A
以上２２回です。
【コメント】
これはすごい解答ですね。
やはり見通しを持っていると解けるものですね。
私もひまを見て実際に動かせるようにプログラムを作ります。
ただし２２回は最短手数ではないようです。
いい機会ですので、東京都 合屋さんから出題時にいただいていた解答を掲載します。
【問３】
この問題は一つの輪にはなりませんが移動範囲を簡略図で表すことができます。
３つの黒のナイトを青のナイトの位置に移動することだけを考える(青のナイトの存在を無視する)と最低７手であることはすぐに判ります。
当然、青から黒への最少手数も７手です。
図にはこの移動経路の例を矢印で描き入れてあります。
この通りに移動できれば６つのナイトは１４手で交換できます。
ところが、どのナイトを動かしても、そのナイトが他のナイトの移動の邪魔をすることになるため、このままの経路では(１４手では)不可能です。
少なくとも１つのナイトについて以下のいずれかの処置が必要です。
ａ．別のルートで移動する。
ｂ．一旦邪魔にならない位置に移動しておき、後で元の位置に戻す。
ａの方法では少なくとも２手増えます。
例えば、(3)から(11)への移動を(4)経由の２手で移動から、(8)−(1)−(6)経由にすると４手になり２手増
ｂの方法では退避と復元に少なくとも２手必要です。
以上により、６つのナイトを交換には最少手数は１６手必要です。
一応、最少の交換手順の例を記しておきます。
(10)の青を(4)まで移動
(2)を(10)、(12)を(2)、(1)を(12)，(11)を(1)と移動
(4)の青を(9)に戻す。
(3)を(11)に移動。(9)から(3)に移動 で１６手です。
◆京都府の中学校３年生 大和 さんからの解答。
初めの位置を１−Ａ、３−Ａ’、７−Ｂ、９−Ｂ’、とする。
答えは次のとうり。
(1)６−Ａ、(2)８−Ａ’，(3)４−Ｂ’、(4)３−Ｂ’、
(5)Ｂ−２、(6)１−Ａ’、(7)９−Ｂ、(8)７−Ａ、
(9)６−Ａ’、(10)４−Ｂ、(11)８−Ｂ’、(12)３−Ｂ、
(13)１−Ｂ’、(14)２−Ａ、(15)７−Ａ’，(16)９−Ａ
おしまい。
答え １６回