ナイト隣接の図解
ナイト隣接とは、格子盤面での「隣り合う」の定義を縦横や縦横斜めではなく、ナイトの効き筋のマスとしたもの。
ペンシルパズルでは、2019年の5月祭のハバネロ問題などに出題例があります
❺ Bosnian Snake [chaos] 作● fff
ルール
・ このパズルでは、チェスのナイトの効き筋のマスを
「隣りあう」とします。
ナイト移動グラフ
ナイト隣接が繋いでいる点を結んでいる箇所を図解しました。
方向によって色を変えています。
https://gyazo.com/e6e4eeeed39329643d0a69d68ecc3fe0
線が多すぎてよくわからないのでグラフの一部を取り出してみます。
方向で分ける
8方向4直線のうち、4方向2直線を取り出すことで6種類の部分グラフを作ることができいます。
なす角$ θによって3パターンに分けられる
$ θ = π/2$ (90°)
https://gyazo.com/3619a5c7bf5facf1adedd6d30d475e20https://gyazo.com/0b464eced935367e9c4313b202b37eef
$ tanθ = 4/3, θ ≒ 53.13°
https://gyazo.com/3fb6c2de7a3feb9657dcabc8e3125141https://gyazo.com/3001f5557697df03421e45d71c44e21f
$ tanθ = 3/4, θ ≒ 36.87°
https://gyazo.com/81c234d1489dddeeedf29604ee1bd245https://gyazo.com/14c24628599e698ce3d578161a94995f
連結成分で分ける
まだ線が多いので、それぞれの部分グラフの連結成分(繋がっている範囲)を取り出します。
https://gyazo.com/e4c18b45f7c5a68bdc60048dfe7b35a0
この形状を5枚合わせると$ θ = π/2$ (90°)のグラフになります
なす角の同じもう一つのグラフと合わせて10枚組み合わせるとナイト隣接グラフができます
https://gyazo.com/80a03754ca8946593902d8232fc83ea9
この形状を4枚合わせると$ tanθ = 4/3, θ ≒ 53.13°のグラフになります
なす角の同じもう一つのグラフと合わせて8枚組み合わせるとナイト隣接グラフができます
https://gyazo.com/a1dd30e684b0696f997218f508a9fdc4
この形状を3枚合わせると$ tanθ = 3/4, θ ≒ 36.87°のグラフになります
なす角の同じもう一つのグラフと合わせて6枚組み合わせるとナイト隣接グラフができます
ようやく、よく見る直交、斜交座標の形になりました、
これらを6,8,10枚組み合わせることでようやくナイト隣接グラフを捉えられるかもしれません。
それぞれのグラフの連結成分の数が異なることから、1直線2方向への移動が許されなかったとしても、
ナイトは盤面のすべてを巡ることができそうです。
https://gyazo.com/048713800e3bc0e8b7337a6c20401267
▲一色を取り除いたナイト移動グラフ
参考
fff氏
utime氏
> utime
@utime1204
マス目において桂馬飛びの関係を隣接と定義するやつ、4次元空間上の格子点に適当な位相を入れたと見る方法もある。