方法マシン＠ZAIM FESTA 2009にて新作『騎士の巡歴』

●日時：2009年3／7（土）　18:00スタート
●場所：ZAIM 横浜創造界隈 別館2Fホール
●実行内容：『騎士の巡歴』
●料金：無料

『騎士の巡歴』は、有名な一筆書きパズル「騎士の巡歴（Knight's Tour）」の解答アルゴリズムを使用したパフォーマンス。 チェスボードを想定したグリッドの中をある一定のアルゴリズムに従って動き、その軌跡を示す。 ZAIM FESTA2009では5x5のグリッドにて、対角にあたる頂点の2つのマスから、2人同時に点対称に移動する形で実行。 グリッドは黒、2人の軌跡はそれぞれ赤、黄のテープで色分けされた。 示された軌跡はパフォーマンス後もZAIMの別館2Fホールにて展示された。

〜「騎士の巡歴（Knight's Tour）」とは〜

チェスの駒の一つである「ナイト」の動きのみを使用して、8x8のチェスボード上の64マスを全て一回ずつ通過させるパズル。 このパズルは古くから知られ、その起源は9世紀からあると言われている。

このパズルを解くための最もよく知られたアルゴリズムは「ワーンスドルフ法（Warnsdorff's algorithm）」というもので、1823年に H. C. Warnsdorffによって発表された。そのアルゴリズムとは、

１．今のマスから移動可能なマスを一つ見る。
２．そのマスからさらに次にいくつのマスに移動できるかを数える。
３．挙げられる全ての移動可能なマスに対して２の作業を行う。
４．２で数えた数が最小であったマスに移動する。
５．最小のマスが複数個存在する場合、それらのマスは任意に選択する。

というものである。このアルゴリズムに従うことによって、簡単に解答が得られる場合があるが、 必ずしも8x8のチェスボードで行う場合は、「５」の場合の任意の選択によっては解くことが出来ないことがある。

しかし8x8のボードではなく、5x5のボードで頂点のマスから始めれば 移動する順序を暗記することなく、アルゴリズムに従うことのみによって解答を得ることが出来る。 また5x5のみならず、9x9、13x13、17x17…と「5+4x」（xは任意の自然数）のボードではこのルールに従って 容易に解答が得られることが知られている。