「絶対左折禁止」の迷路を解く（Ruby）

ブログにスターを頂いて、上のサイトを知りました。オリジナルの様々な迷路が出題されている、すばらしくおもしろそうなブログです。皆さんも御覧になってはいかがでしょうか？

…とは別にステマでも何でもないのですが、そこで「絶対左折禁止」という迷路が出題されているのが目に止まりました。こんなのです。リンク先を御覧下さい。
とまたよくない病が…。Ruby で解いてやろうというのですね。もしかしたら作者様には失礼に当たるかもしれません。であればどうかお許しください。

ルールとしては、もちろん交差路では左折してはいけませんが（直進と右折のみ）、角でも左に曲がってはいけないというものです。さて、どう解くか。迷路を交差路と角のつながりとして抽象化しようかと思いましたが、どうも面倒で、えいテキストエディタで入力だ！　ということにしました（笑）。これがそうです。
maze_never_turn_left.txt

0000000000000000   00000000000
0   0       0  0   0    0    0
00S 0000000000000000    0    0
0       0   0      0    000000
0       0 000000   0         0
0  0000 0 0 0  0   0         0
0  0  0 0 0 0  0   0         0
0000  00000 0  0   0         0
   0  0 0   00000000000      0
   0  0 0   0  0   0  0      0
   0  0 0   0  0   0  0      0
   0000000000  0   00000000000
   0    0  0   0   0      0  0
000000  00000000   00000000000
0    0     0   0          0   
0    0     0   0          0   
0 000000000000000000  00000000
0 0  0     0   0   0  0   0  0
0 000000   0   000000000000  0
0  0   0   0       0         0
0  00000000000000000       G00
0      0   0  0    0         0
0      0   0  0    0         0
00000000   0000000000000000000

ぽちぽちと手作業で入力しました。

とりあえず迷路はデータ化しました。あとは解くだけですね。コードはこんな風に出来上がりました。何の準備もなくいきあたりばったりにコーディングしたので、途中でかなりおかしなことをしていたりしました。完成させるのに数時間もかかってしまいました。
maze_never_turn_left.rb

class SolveMaze
  open("maze_never_turn_left.txt") {|io| @@field = io.readlines}
  @@field.map! {|f| " " + f.chomp + " "}
  a = [" " * @@field[0].size]
  @@field = a + @@field + a
  
  class Position
    def initialize(x, y, dir = nil, parent = nil)
      @x, @y = x, y
      @kind = get[y][x]
      @dir = dir
      @parent = parent
    end
    attr_reader :x, :y, :dir, :parent, :kind
    
    def neighbor
       result = []
       [[0, -1], [1, 0], [0, 1], [-1, 0]].each_with_index do |step, i|
          x = @x + step[0]
          y = @y + step[1]
          result << Position.new(x, y, i, self) if get[y][x] != " "
       end
       result
    end
    
    def get
      SolveMaze.class_variable_get(:@@field)
    end
    
    def finish
      result = [[@x, @y]]
      a = parent
      field = Marshal.load(Marshal.dump(get))
      loop do
        result << [a.x, a.y]
        break if a.kind == "S"
        field[a.y][a.x] = %w(↑ → ↓ ←)[a.dir]
        a = a.parent
      end
      #puts result.reverse.flatten.join(",")    #GIF画像作成用
      field.map {|x| x.gsub!("0", " ")}
      field.each {|x| puts x}
      #exit
    end
    
    def check
      a = self
      loop do
        a = a.parent
        return true if a.kind == "S"
        return false if a.x == @x and a.y == @y and a.dir == @dir
      end
    end
  end
  
  def initialize
    n = @@field.join.index("S")
    l = @@field[0].length
    @queue = Position.new(n % l, n / l).neighbor
  end
  
  def go
    while (po = @queue.shift)
      pos = po.neighbor.reject {|a| a.dir == (po.dir + 2) % 4}   #あと戻り以外に行ける場所
      pos.each do |nxt|
        next if (po.dir - nxt.dir) % 4 == 1       #左折禁止
        if nxt.kind == "G"
          nxt.finish
        elsif nxt.kind == "0" and (pos.size < 2 or nxt.check)
          @queue << nxt
        end
      end
    end
  end
end

SolveMaze.new.go

Position クラスは現在の位置の他、場所の種類（@kind）、どちらの方向から来たのか（@dir）とひとつ前の位置（@parent）の情報を保持しています。SolveMaze#go がメインループ、Position#check は無限ループしないかチェックしています。Position#neighbor は現在位置の周囲の情報を与えます。

結果です。解くのにかかった時間は自分の環境で 0.1秒未満です。

 ↑→→→→→→→→→→→→      ↑→→→→→→→→→→ 
 ↑           ↓      ↑         ↓ 
 ←←S     ↑→→→↓→→→→→→→         ↓ 
         ↑   ↓      ↓         ↓ 
         ↑   ↓→→→   ↓         ↓ 
         ↑   ↓  ↓   ↓         ↓ 
         ↑   ↓  ↓   ↓         ↓ 
         ↑   ↓  ↓   ↓         ↓ 
         ↑   ↓←←←←←←↓→→→      ↓ 
         ↑   ↓  ↓   ↑  ↓      ↓ 
         ↑   ↓  ↓   ↑  ↓      ↓ 
         ←←←←↓  ↓   ←←←↓→→→→  ↓ 
         ↑  ↓   ↓   ↑      ↓  ↓ 
 ↑→→→→→  ←←←←←←←↓   ←←←←←←←←←←↓ 
 ↑    ↓     ↓   ↑          ↓    
 ↑    ↓     ↓   ↑          ↓    
 ↑ ↑→→↓→→→→→↓→→→→→→→→  ↑→→→↓→→→ 
 ↑ ↑  ↓     ↓   ↑   ↓  ↑   ↓  ↓ 
 ↑ ←↑→→→→   ↓   ←←←←↓  ←←←←↓  ↓ 
 ↑  ↑   ↓   ↓                 ↓ 
 ↑  ←←←←←←←←↓               G←↓ 
 ↑      ↓                       
 ↑      ↓                       
 ←←←←←←←↓

正直いってちょっとわかりにくいですね。なので GIFアニメを作ってみました。
　

　
どうでしょうか。関連するすべてのコードは Gist にあります。
絶対左折禁止の迷路を解く · GitHub
　
なお、この迷路の解はひとつだけで、複数の解はありません（意味のないループを除く。）複数解があればすべて出力します。また、任意の「絶対左折禁止」の迷路が解ける筈です。（ただし、迷路をあらわすテキストファイルは、すべての行の長さを同じにして下さい。）

左折禁止ではない、任意の迷路を解くように改変するのも容易です。左折禁止を判断している一行を削除すればよろしい。ただし、すべての解を求めるのが冗長ならば、Position#finish メソッドの終わりに exit を追加すればよいです。その際はひとつの最短ステップの解を出力して終了します。なお、いまのままだと同じ地点を通っても向きがちがえば許容されるので、同じ地点を通らないようにするには Position#check メソッドの判定条件を変える必要があります。

作者様、楽しい迷路をありがとうございました！

追記

迷路の作者様にブログで取り上げて頂きました。ありがとうございます。とてもうれしいです。

せっかくなのでアルゴリズムについて少しだけ書いておきましょう。基本的なことなので、当り前だという方はスルーして下さい。

迷路を解くにはまず解の経路をどう表現するかです。上のコードでは Position クラスが位置の情報を持っています。そして、それが tree 状の「経路」を表現しているというのは、Position クラスのインスタンスがひとつ前の位置の情報（@parent）を持っているので可能になります。@parent をずっと遡っていけば、スタート地点までたどり着くということですね。なので、探索の数だけ Position クラスのインスタンスが生成されることになります。無駄といえば無駄をしていますが、実際にこの程度ならば大した数ではないですし、コードが簡単になります。もちろん、必ずこのように経路を表現しなければならないということはありません*1。

そして、経路の「探索」ですが、一般に tree 状の探索を行うには、基本的に「深さ優先探索」と「幅優先探索」の二種類があります（これだけということではありません）。一般に、「深さ優先探索」の方が高速かつ省メモリであるとされ、tree をいきなり深く潜っていきます。それに対して「幅優先探索」は tree を探索開始地点から近い順に探索していきます。そこで迷路の探索ですが、すべての解を調べるならばいずれの方法でも同じ結果が出るのがふつうです。ただし、最短経路を探す場合は、「幅優先探索」を使うことになります。また、すべての解を調べる場合でも、「幅優先探索」を使うと経路の短い順に結果が出力されます。なので、上では「幅優先探索」で実装されています。ただし、これを「深さ優先探索」に変更するのはじつに簡単で、上のコードなら SolveMaze#go メソッドの po = @queue.shift の shift を pop に書き換えるだけなのです。以上のことはぐぐればいくらでも解説があると思います。

どうでしょうか。あと、上のコードが多少でも簡潔に書けているとすれば、僕の好きな Ruby 言語の力も大きいと思います。というか、Ruby でコーディングするのが好きで、題材を探しているようなものです。皆さんも Ruby、どうですか？（笑）

*1:例えば、迷路のマップ（上のコードなら @@field）に書き込んでいくとかは、誰でもすぐに思いつくでしょう。ただし、これだと複雑な条件をあらわすのがむずかしくなったりで、一長一短です。ちなみに上のコードでは、@@field の値は一切変更していません。