ナイト問題がわかりません

質問

以下の3*3マスにある
a,b,cのナイトをマスa',b',c'に移動させることができるか、という問題です。
ただしaはa'に、bはb'に、cはc'に移動させます。またナイト同士が重なることや、3*3マス外に移動させることは禁止です。またこのナイトはチェスのナイトと同じ動きをします。

自分は「できない」が答えだと思うのですが、どうしてできないのか説明できません。（そもそもできるかもしれない・・・）
答えと理由を教えてくださると助かります。

________
| a | b | c |
|__|__|__|
|__|__|__|
| a'| b' | c'|
|__|__|__|

回答No.1

k_maisan · ベストアンサー

3ｘ3のマスで、aの位置のナイトを右回りで移動できる順番にあわせて
以下のようにマスに番号を付けます。中央は移動しませんので0にします。

[1][4][7]
[6][0][2]
[3][8][5]

ここでマスを作り替え、
[1][2][3][4][5][6][7][8] と並んだマス（[1]の左は[8]の右につながっている）の
上にナイトを配置し、ナイトは隣に移動できるというように考えてみます。

初期は、マスの番号 [1][4][7] にナイトa,b,cがいます。

aは[3]のマスに、bは[8]のマスに、cは[5]のマスに移動させたいのですが、
これは、a,b,cと並んでいるナイトを、a,c,bの順番並び替えることになり、
単にナイトが左右に移動するだけでは実現できません。

よって、3つのナイトを重ならないようにして a→a'、b→b'、c→c' に
移動させるのは不可能ということになります。

お礼

ありがとうございます。
なるほど、マス目を帯状にしてナイトの動きを左右に動かすということに帰着させるんですね。その発想は思いつきませんでした・・・
説明もわかりやすかったです。