昔の感覚を思い出すために、格子上の道の通り方を数えるプログラムを組んでみました。4×4が限界だし論文とか読んでアルゴリズムを導入しないとダメかな···

面白そうですね!! 条件は、全ての角・交差点をただ一度だけ通る?? 限界の理由は何ですか??

同じ道なだけで、全部通らなくても大丈夫です！ 10×10までは処理できるようにしているのですが、5×5の時の答えは4×4の150倍になるので待つと半日かかりそうなんですよね...

同じ角・交差点を一度以上通ることなくSからGまで、ですね?? 限界は時間ですかー

まさしくその通りです。遠回りしてもいいけれど同じ角を通らないで左上から右下まで移動する方法...となります。 単純なのですが、マスが1つ大きくなると計算量が何千倍にも何万倍にもなってしまうんのでそれだけ時間がかかるんですよね..

PC で C でバックトラックで書いたけど 4x4(8512)で 0.00秒 5x5(1262816)で 0.65秒 6x6(575780564)で 389.02秒 でした。 これって組み合わせ爆発おねえさん問題ですね?? 賢いアルゴリズムがあるらしいけど???

まさしく「おねえさんの問題」ですね。ただの総当たりだと高々4^(n^2)通り調べないといけないので、こちらも簡単なバックトラック法で書かせていただきました あれから、おねえさんの問題のプロジェクトをされていた方の著書で、アルゴリズムの流れはおおよそ理解できましたが、プログラミングに不馴れで未だにそれを再現できておりません…