アーシの毎日インプット

毎日1つ以上学習する。学習した内容を公開する。を目標に自分のスキルアップを目指します。

八方桂(ナイトツアー)をどのマスから始めても解けることを証明しました

スポンサードリンク

前回からの続きです。

 

前回は、八方桂(ナイトツアー)を解いてみました。

 

 

解き方、ルールは前回の記事を参照ください。

arsinput.hatenablog.jp

 

 

今回は、八方桂(ナイトツアー)はどこのマスから始めても解くことができるのか?

というのを証明していきます。

 

照明する方法としては以下の2種類の方法があると思います。

 

1.下記の10マスから10通り解いてみる

f:id:arshii:20190819060309p:plain

上の図の黄色い10マスから解けることを確認したら、どのマスから始めても解けることを証明できます。

残りの54マスについては解いてみた10マスと点対称・線対称の関係になっているため、解けることを確認する必要はありません。

 

 

2.ループできる解答を見つける

f:id:arshii:20190819061124p:plain

上の図のように、ゴールとなる64手目を、1手目と桂馬飛びとなるような位置に設定し、解くことでどのマスから始めても解けることを証明できます。

 

ループしているということはその手順の何番目から始めても解けるということです。

 

 

 

今回は「2.ループできる解答を見つける」の方針で解いてみました。

 

解いてみた結果はこちら

f:id:arshii:20190819062228p:plain

なんとか解くことができましたが、この解答にいきつくまでに結構苦労をしました。

普通に解こうとするとどうしても抜けができたり、64に帰ってこれなかったりと、いくらやっても駄目でした。

 

 

そこで、この問題を簡単に考える方法を検討してみました。

f:id:arshii:20190819062541p:plain

まず、周り2マスを4色で塗り分けました。

 

各色はループしています。

ということはその色に侵入し、その色の隣のマスからでてくることで、4辺を回って出てくることができます。

 

ということは、内部の白い部分、4×4を途中に何回か外側に出ながら解くことができれば、ループする解答を得られると考えました。

 

私が上の方法で解法を考えた結果がこちらです。

f:id:arshii:20190819063810p:plain

64手の問題を26手の問題に簡略化できました。

 

 

よって、八方桂(ナイトツアー)でループする解答を見つけ出すことができ、どのマスから始めても解けることを証明できました。

 

 

最後に、私が八方桂(ナイトツアー)を知ったきっかけのブログを載せておきます。

tn198403s.hatenablog.jp

【アーシの原点】

【頭を鍛える迷路集】


スポンサードリンク