必ず解ける迷路 in Ruby DouKaku?

以下のルールを満たすn×mの迷路を出力するプログラムを作ってください。

1. 格子状の迷路であること。
2. 経路の幅は均等であること。
3. 迷路のある地点からの全ての地点に到達する経路が1つだけ存在すること。
   ループも認めません。
4. 出力の度にランダムな迷路であること。
   ランダムシードが同じ時に同じ迷路になってしまうのはよいです。

たとえば、n=4, m=5の迷路の出力は以下のようになります。

　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■　　　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　■　　　■　■
―■■■■■■■■■

こう言うのは、×の部分が3のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　■×■　■
―■■■　■■■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■■■　■
４■　■×××■　■
―■　■×■■■　■
５■　■×××■　■
―■■■■■■■■■

このようなループも2のルールに違反するのでダメです。
　｜１｜２｜３｜４｜
―■■■■■■■■■
１■　　　　　■　■
―■■■　■　■　■
２■　　　■　　　■
―■　■■■　■　■
３■　　　　　■　■
―■　■■■　■　■
４■　■　　　■　■
―■　■　■■■　■
５■　　　　　■　■
―■■■■■■■■■

できたプログラムを使って n=1024, m=1024 の迷路を作るのにかかった時間を教えてください。


難易度高めです。限られたメモリを使って縦方向に無限に広い迷路を
どうやって作るのかを考えると答えが見えてくると思います。
ソースコードはJavaで150行程度になりました。

棒倒し法で実装しました. 
1024 x 1024の迷路生成に約48秒 (CPU: Intel P4 Northwood 2.8 GHz) かかりました. 
mapメソッドとgen_wallメソッドの処理の1行目のコメントは, 各メソッドの1行バージョンです. 
全体をone-lineにする方法が見つからなかったのでせめてもの抵抗ということで.

see: アルゴリズム講座:棒倒し法

require 'matrix'
N, M = 5, 4
class Maze
  MARK, SPC = '*', ' '
  def initialize(n, m) #基準点を生成し, その上と左の壁の有無と真理値が対応. 
    @map = Matrix[*Array.new(@n = n){Array.new(@m = m)}].map{Array.new(2)}
    gen_maze
  end
  def map #得たマップデータを対応する記号で表現
    #Array.new(2*@n-1){|i| Array.new(2*@m-1){|j| i%2 == j%2 ? (i%2 == 1 ? MARK : SPC) : (@map[i.div(2), j.div(2)][i%2] ? MARK : SPC)}.unshift(MARK).push("#{MARK}\n")}.unshift(str = "#{MARK*(2*@m+1)}\n").push(str).join
    print "#{MARK*(2*@m+1)}\n"
    (2*@n-1).times{|i|
      print MARK
      (2*@m-1).times{|j|
        if i%2 == j%2
          print i%2 == 1 ? MARK : SPC
        else
          print @map[i.div(2), j.div(2)][i%2] ? MARK : SPC
        end
      }
      print "#{MARK}\n"
    }
    print "#{MARK*(2*@m+1)}\n"
  end
  def gen_maze #左端の列だけ4種の壁がランダムで生成. 他は3種のみ. 
    (@m-1).times{|j| (@n-1).times{|i| gen_wall(i, j, (j == 0 ? 4 : 3))}}
  end
  def gen_wall(i, j, n) #ランダムに壁を生成. もし壁がすでにあれば再帰. 
    #@map[x = i+((r=rand(n))==1 ? 1 : 0), y = j+(r==2 ? 1 : 0)][r%2] ? gen_wall(i, j, n) : @map[x, y][r%2] = true
    case rand(n)
    when 0: x, y, k = i,   j, 0 #上
    when 1: x, y, k = i+1, j, 0 #下
    when 2: x, y, k = i, j+1, 1 #右
    when 3: x, y, k = i,   j, 1 #左
    end
    @map[x, y][k] ? gen_wall(i, j, n) : @map[x, y][k] = true
  end
  private :gen_maze, :gen_wall
end
maze = Maze.new(N, M)
maze.gen_maze
maze.map

迷路がお題を満たす(全ての場所にいける&ループ無し) ための必要十分条件は
「全ての基点(マップ上で(i, j)=(偶数, 偶数)の点) が外壁と一ヶ所でだけ繋がっている」
なんじゃないかなぁと思って、
お題を満たすような迷路を全て生成し得るような方法を考えてみました。

領域量はO(mn)要ります。1024*1024で2分ぐらい。


ちなみに棒倒し法なんかだと、例えば次のようなものを生成できません。

■■■■■■■■■
■　■　　　　　■
■　■　■■■　■
■　■　■　■　■
■　■　■　■　■
■　■　　　■　■
■　■■■■■　■
■　　　　　　　■
■■■■■■■■■

class Maze
  def initialize(m, n)
    @rows = m
    @cols = n
    @field = Array.new(2*@rows+1) do |i|
      (i % 2 == 0) ? ('# ' * @cols + '#') : ('#' + ' ' * (2*@cols-1) + '#')
    end
    @field[0] = @field[-1] = '#' * (2*@cols+1)
  end

  def gen
    # number of connections to the wall
    bases = Array.new(@rows+1) do |i|
      if i == 0 || i == @rows
        Array.new(@cols+1, 1)
      else
        Array.new(@cols+1) {|j| (j == 0 || j == @cols) ? 1 : 0 }
      end
    end
    uc = []  # candidates of next selection
    (1 .. @rows-1).each {|i| uc << [i, 1] << [i, @cols-1] }
    (2 .. @cols-2).each {|j| uc << [1, j] << [@rows-1, j] }

    until uc.empty?
      y, x = uc.slice!(rand(uc.size))
      next if bases[y][x] > 0
      dirs = [[+1, 0], [-1, 0], [0, +1], [0, -1]].sort_by { rand }
      dirs.each do |mv|
        y_, x_ = y + mv[0], x + mv[1]
        if bases[y_][x_] == 1
          @field[2*y+mv[0]][2*x+mv[1]] = ?#
          bases[y][x] += 1
          break
        end
      end
      dirs.each do |mv|
        y_ , x_ = y + mv[0], x + mv[1]
        uc << [y_, x_] if bases[y_][x_] == 0
      end
    end
    self
  end

  def p
    @field.each {|row| puts row }
  end
end


M, N = 10, 10
maze = Maze.new(M, N)
#maze.p
maze.gen.p

棒倒し方では, 格子状に壁を生成し, それを起点に周
囲に1つ以上の壁を生成していきます. 
そのため, 必ず格子状に壁が存在し, かつその周辺に
1つ以上壁が存在することになり, 一部の構造の迷路
が生成できないということなんだと思います.

というわけで、通路の最小全域木を作るものを実装してみました。穴掘りです。

Pentium4/2.8GHzで1分半ほど。

class Maze
  WALL, VAC = '#', ' '
  DIRS = [[+1, 0], [-1, 0], [0, +1], [0, -1]]
  def initialize(m, n)
    @rows = m
    @cols = n
    @field = Array.new(2*@rows+1) { WALL*(2*@cols+1) }
  end

  def gen
    conn = Array.new(@rows) { Array.new(@cols, false) }
    cand = [[rand(@rows), rand(@cols), 0, 0]] # (0,0) is dummy
    until cand.empty?
      y, x, dy, dx = cand.slice!(rand(cand.size))
      next if conn[y][x]
      conn[y][x] = true
      @field[2*y+1-dy][2*x+1-dx] = VAC
      @field[2*y+1][2*x+1] = VAC
      DIRS.each do |mv|
        y_, x_ = y+mv[0], x+mv[1]
        if (0...@rows) === y_ &&
           (0...@cols) === x_ &&
           !conn[y_][x_]
          cand << [y_, x_, mv[0], mv[1]]
        end
      end
    end
    self
  end

  def p
    puts @field
  end
end

M, N = 10, 10
maze = Maze.new(M, N)
maze.gen.p

DouKaku?

必ず解ける迷路

Posted feedbacks - Ruby

Index

Feed

Other

Link

Pathtraq