今更ながら「フカシギの数え方」

「フカシギの数え方」に出てくる，$n \times n$のマス目を一度通った場所を通らないように左上から右下まで移動する経路の組み合わせを数え上げる問題。この自己回避歩行（self-avoiding walk）のもっとも基本的な処理，つまりおねえさん式にすべての組み合わせをひたすら数え上げる処理をpythonで作成してみました。

ただしあくまで作成してみただけであり，動画にもある通り，マス目の数が増えると組み合わせの数は膨大になるのでこのスクリプトはまったく実用的ではありません（まともな用途にはGraphillionなどを使いましょう）。

スクリプト

def saw(n, path):
    if -1 in path[-1] \
     or n in path[-1] \
     or path[-1] in path[:-2] : return 0 

    if path[-1]==(n-1,n-1) : return 1

    return saw(n,path+[(path[-1][0]+1, path[-1][1]+0)]) \
         + saw(n,path+[(path[-1][0]-1, path[-1][1]+0)]) \
         + saw(n,path+[(path[-1][0]+0, path[-1][1]+1)]) \
         + saw(n,path+[(path[-1][0]+0, path[-1][1]-1)]) 

n = 5
print(saw(n,[(0,0)]))

出力結果

8512

saw（self-avoiding walk）関数には，縦または横のノードの数（四角形の数+1）と，起点の座標を与えます。なお，起点座標は，「起点座標のタプルを含んだリスト」の形で与えます。

saw関数の中身は，

• 最新座標（リストの最後部）が「マス目の範囲外」か「すでに通った場所（リストの中に存在する座標）」であれば0
• 最新座標（リストの最後部）が「目的地（タプル(n-1, n-1)で表される座標）」であれば1

として，最新座標をそれぞれ縦横に1つずらした座標をリストに追加しながらsawを再帰し，戻ってきた数値を合計しています。つまり目的地にたどり着いて1が返ってきた経路の数を合計値として求めていることになります。