スライドパズルっていうおもちゃがありますよね。4×4 のマス目に空白がひとつあって(残りはコマ)、コマは空白にスライドさせて動かすしかなく、それを特定のパターンに揃えるというものです。ここではルールを少し改変して、特定のマスを別の特定のマスに移動させるのに最短で何手かかるかを考えます。
例えば 3×2 のパズルでいちばん右下のマスが空白であり、いちばん左上のマスにあるコマをいちばん右下へもってくるには、最短で 9手かかります。
●●● ● ○ ●●● ●○ ●● ●○● ● ● ●○● ●○● ● ● ●○● ●● ○● ●●● ○ ● ●●● ○● ●●● ○●● ●● 9手で終了
ただしこれは、下の方から見ていって下さい(プログラムの関係でそうなっています)。
僕が見たアルゴリズムパズルの本では、10×10 のパズルでやるのと同等な問題が与えてありました(駐車場で車を脱出させるという体裁になっていました)。これは自分の書いたプログラムだと、69手ということになります(調べたパターンの数は 8927個)。計算時間はこれだと(自分の環境で)およそ 41秒と、かなり微妙な数字になりました。瞬殺は無理でしたね。これ以上広いパズルだと、根本から考えなおさないとダメかも知れません。
コードは以下です。幅優先探索で求めています。また、既に出たパターンに逢着した場合はスキップしています。
class Parking def initialize start = Pattern.new start.car.x, start.car.y = 0, 0 start.space.x, start.space.y = Width - 1, Height - 1 @@patterns = [start] end def solve buffer = @@patterns.dup while (po = buffer.shift) [po.up, po.down, po.left, po.right].each do |i| next unless i if i[1] #true ならば終了 @@co = 0 i[0].show puts "#{@@co - 1}手で終了" puts "調べたパターン数は#{@@patterns.size}" exit end buffer << i[0] end end end end class Pattern < Parking class Car < Struct.new(:x, :y); end class Space < Struct.new(:x, :y); end def initialize @car = Car.new @space = Space.new @parent = nil end attr_accessor :car, :space, :parent def up x, y = space.x, space.y - 1 return false if y < 0 check(x, y) end def down x, y = space.x, space.y + 1 return false if y >= Height check(x, y) end def left x, y = space.x - 1, space.y return false if x < 0 check(x, y) end def right x, y = space.x + 1, space.y return false if x >= Width check(x, y) end def check(x, y) nxt = Pattern.new nxt.space.x, nxt.space.y = x, y nxt.car = (@car.x == x and @car.y == y) ? @space : @car @@patterns.each do |pa| return false if nxt.car == pa.car and nxt.space == pa.space end nxt.parent = self @@patterns << nxt [nxt, (nxt.car.x == Width - 1 and nxt.car.y == Height - 1)] end private :check def putout Height.times do |i| st = "●" * Width st[@car.x] = "○" if @car.y == i st[@space.x] = " " if @space.y == i puts st end puts end def show @@co += 1 putout @parent.show if @parent end def inspect "<Pattern:car(#{@car.x},#{@car.y}), space(#{@space.x},#{@space.y})>" end end Width = 4; Height = 4 Parking.new.solve
なお、このプログラムは Pattern#putout で String リテラルの破壊的変更を行っています。
ちなみに「15パズル(4×4)」の場合、21手で終了します。時間は約 0.1秒です。
プログラマ脳を鍛える数学パズル シンプルで高速なコードが書けるようになる70問
- 作者: 増井敏克
- 出版社/メーカー: 翔泳社
- 発売日: 2015/10/16
- メディア: Kindle版
- この商品を含むブログ (8件) を見る