目的
　子供の頃に迷路を描いて遊んだことがある人は少なくないのではないでしょうか？僕も小学生のとき、自由帳に無意味に迷路を描いては友達に解いてもらっていたものです。当時は難しい迷路を作ろうとして、より巨大で、より精緻な迷路を追求していました。しかし、自由帳のページのサイズも鉛筆で描ける線の太さも有限の値を取る以上、迷路の大きさと細かさには限界があります。
　では、一定の面積かつ一定の細かさでより難易度が高い迷路を作るにはどうしたらいいいのでしょうか？そして、そもそも迷路の難易度とはどのように定義するのが適切なのでしょうか？
　と、いうわけで今回は迷路の難易度の定量化と、より難しい迷路を構成するための方法について考えていこうと思います。

迷路の定義
　まず、議論の対象となる迷路をしっかりと定義しておきます。今回はサイズ以外の要素による迷路の難しさの定量化、つまり二つの同じ大きさの迷路が与えられたとき、どちらがより難しいかを比較できるようにすることが目的なので、大きさと細かさを一定に保ったまま複数の迷路が構成できる必要があります。そこで、10×10のマス目に沿って壁を配置し、異なる２マスをそれぞれスタートのマスとゴールのマスとして定めたものを迷路と呼ぶことにします。また、スタートのマスから出発して上下左右に隣接しているマスのうち、壁で仕切られていないマスへの移動を繰り返してゴールのマスまで移動することを迷路を解くと言い、それが可能な迷路を解ける迷路と呼ぶことにします。

難易度の定義
　次に迷路の難易度をどう定義するべきかを考えます。パッと思いつくのは迷路を解くのに要する移動回数の期待値ですが、この値を得るにはまず、迷路の解き方であるアルゴリズムを定めなければなりません。今回は二つのアルゴリズムを考えてみましょう。名付けて「記憶無しアルゴリズム」と「記憶ありアルゴリズム」です。
　記憶なしアルゴリズムは迷路中をランダムに歩き回るアルゴリズムです。移動するマスを移動可能なマスの中から完全にランダムで決定します。どのマスから来たかを全く考慮せずにどのマスに行くかを決定するので、行き止まりのマスでなくても引き返すことがあります。
　対する記憶ありアルゴリズムはこれまで通過してきたマスをすべて記憶した上で同じ行き止まりに２回以上到達しないようにするアルゴリズムです。行き止まりと分岐以外のマス、すなわち２辺に壁が配置され２辺が開いているマスでは移動して来たマスと反対のマスに移動するので無意味に一本道を引き返すことはしません。行き止まりに到達すると直前に通った「まだ選んでない分岐があるマス」まで引き返し、まだ選んでいない分岐の中から進む道をランダムに決定します。
　今回はこの記憶なしアルゴリズムと記憶ありアルゴリズムに従って迷路を解くのに要する移動回数の期待値をそれぞれその迷路の記憶なし難易度と記憶あり難易度と定義します。

難易度が高くない迷路とは？①複数の正解を持つ迷路
　さて、迷路とその難易度を評価する2つの尺度について定義したところで、これらの尺度における「難しい迷路」とはどんなものなのかを考えていきます。より難しい迷路を考えるにあたって、まずは「明らかに難しくない迷路」を切り捨てることを考えます。つまり、記憶あり難易度と記憶なし難易度のどちらを採用したとしても明らかにもっと難しい迷路が存在すると言える迷路とはどんな迷路なのかについて考察します。
　そのような迷路としてまず、スタートからゴールまでのルートが複数存在する迷路が考えられます。それは例えば下の図（省略）のような迷路です。この迷路はスタートからゴールまでの最短経路が２通り存在しているので、壁を追加してどちらか一方のルートを行き止まりにすることでより難しい迷路が構成できてしまうことが明らかです。また、次の図（省略）のような迷路も同様の理由で明らかに難しくない迷路です。この迷路は最短経路は一通りに定まるものの、一度も行き止まりのマスに移動することなく迷路をクリアする「2番目に短いルート」が存在しているので二つのルートのうちどちらか一方を壁で塞ぐことでより難しい迷路が構成できます。さらに、下の図（省略）のように、あるマス目の格子点から四方向すべてに壁がなく、部屋のような部分ができている迷路についても下の図（省略）のように「2番目に短いルート」が存在していると考えることができるので、「複数の正解を持つ迷路」だと解釈できます。

難易度が高くない迷路とは？②デットスペースがある迷路
　では「複数の正解を持つ迷路」の他に「明らかに難しくない迷路」にはどんなものがあるでしょうか？さっき考えた複数の正解ルートが存在する迷路は、壁を追加して正解のルートを塞いでいくことでより難しい迷路を構成できてしまう、言わば「壁が少なすぎる迷路」でした。では今度は「壁が多すぎる迷路」つまり、壁を取り除くことでより難しい迷路が構成できてしまうような迷路について考えてみましょう。

ここまでで一旦終わりです。完全版が読みたかったらいいねください！！

３いいねで継続します。