ナイト巡回問題

問題

ナイトをチェス盤のあるマス目から出発してすべてのマス目を１回ずつ通りもとに戻ってくるような道を見つめる問題です。チェス盤のように８×８のマス目だけではなく一般化してm×ｎのマス目で考えることにします。

ニューラル表現

まず、ｐ×ｐの２次元ニューロン配列を用意します。ｐはマス目の数です。ｍ×ｎの盤なら

ｐ＝ｍｎ

です。ニューロンＶｉｊが発火していれば、ｉ→ｊ（もしくは、ｊ→ｉ）への動きを表します。ただし、ｉ、ｊはマス目にふった番号。例えば、４×４の場合

にふる。また、ナイトが可能な動きを表すｐ×ｐの２次元配列ｄを用意します。ｄ（１，７）＝１だったとしたらマス１から７へ移動可能だということを示します。ｄ（２，１）＝０なら２から１へは移動できないというように可能なら１、不可能なら０とします。また、ｉ→ｊという動きが可能ならｊ→ｉという動きも可能なはずです。ということは、常に

ｄｉｊ＝ｄｊｉ　　　Ｖｉｊ＝Ｖｊｉ　　　　　　・・・・・・・・　（１）

が成り立つということになります。

動作式

今回、無意味っぽい定数なしです。
第一項は、ｉ行目のニューロンを２つ発火させるようにはたらきます。
第二項は、同じくｊ列目のニューロンを２つ発火させるようにはたらきます。
ただ単純に縦横にニューロンを発火させるのではなくｄをかけることによってナイトの可能な動きのみにニューロンを発火させることができます。なぜ、２つ発火させるのかと思うと思います。それは、ひとつのマス目をただ一回だけ通るときそのマスに一回だけ入ってきて一回だけ出て行きます。ｉ→ｊ→ｋ番目と動くとすると

Ｖｉｊ＝Ｖｋｊ＝１

です。ナイトが巡回するように動かすのだからどっち回りでも動いてもよいのであまりどこからどこへという方向にはとらわれずにただ入ってきて出ていくのに縦横２つずつ発火させると考えるととっつきやすいのではないかと思います。

ほんまにこんなんでうまくいくのかと思われる方がいると思います。そうです。うまくいかないのです。この動作式は，マス目を一度だけ通り、通り道が閉じているつまりわっか（ぐるぐる回れる）になっているれば満たします。何がいいたいかというとすべてのマスがつながっているということが抜けているのです。４×３の盤の例で示すと

ニューロン配列：

でもうこれ以上ニューロンは動かなくなります。これを実際の道におこしてみると

となり、ひとつの道ですべてのマスを通っておらず２つの道でマスを回っています。

プログラミング

今回は、たくさんの配列を用意しなければならないのでＬＳＩ　Ｃ−８６試食版のスモールモデルでは、二桁×二桁のとき領域が確保できません。だから、ほかのコンパイラでコンパイルしたものを付けときます。３２ｂｉｔ下（ＤＯＳ窓）でしか動きません。

今までは、再コンパイルしないと変数が変えられなかったが、今回は外部にコンフィグファイルを用意してみました。

knight.cfg：
NROW = 8
NCOLUMN = 8
A = 1
UTP = 3
LTP = 1
UMAX = 10
UMIN = -10
CHECKER = 1
CHECK_MAX = 600

順番を変えたり一行に二つ以上書いたりすると正常に動かなくなるので注意してください。

ナイトの移動判定ｄは、自動生成します。その他、目新しいことは何にもやっていないので説明することないです。
上のほうにある（１）をうまく利用すると確保する領域をRとすると

R=ｐ（ｐ−１）/２

で済みます。めんどっちいのでやってません。

Knight.cab (５７KB)

Knight.c　　　　　　　ソースファイル
Knight.exe　　　　　ＬＳＩ　Ｃ−８６試食版でコンパイルしたもの
Knight32.exe　　　３２ｂｉｔ下での実行ファイル
knight.cfg　　　　　　コンフィグファイル、knight.exeとknight32.exe共通　

ますの数が大きくなってくると解が出にくくなります。根気強く実行してください。

あと、1943年にＦｒｅｄ　Ｓｃｈｕｈ氏が述べたことでｍ×ｎのｍ、ｎはともに偶数でなければならないらしいです。解があるための必要条件です。また、正方形の場合は、６以上で偶数であれば解が一つは存在するようです。

戻る　インデックスへ　次へ