せかいや

いまいるここを、おもしろく http://sekai-in-the-box.appspot.com/

【Ruby】【アルゴリズム】7パズルを解く。メモリ爆発Ver

7パズルとは

8つのタイルと一つのスペースがあり、それぞれに数が書いてある。
タイルを上下左右にすべらせ、最終状態にする。ただし、枠からはみ出してはいけない

[最終状態] ※9は空白を表す
9123
4567


 
この本に載ってる問題だよ↓

プログラミングの宝箱 アルゴリズムとデータ構造 第2版

プログラミングの宝箱 アルゴリズムとデータ構造 第2版



  

嵌ったところメモ

・確認した版の状態(配列)を履歴として全てキューに格納していたためメモリが爆発した
  ⇒配列を数値に変換してから格納する
・すでに確認した版も繰り返し確認していた
  ⇒状態保持キューの中に対象の版がすでに存在した場合はキューに格納しない、の実装を忘れていた


実装コード

#表示用
def show(panel)
p panel[0..3]
p panel[4..7]
puts "------"
end

class Pattern
  attr_accessor :val, :parent_idx
  def initialize (val, parent_idx)
    @val = val
    @parent_idx = parent_idx
  end
end

class PatternQue < Array
  def add_next_pattern(idx)
    blank = self[idx].val.index(9)
    if blank < 4
      copy = self[idx].val.dup
      copy[blank], copy[blank+4] = copy[blank+4], copy[blank]
      tmp = Pattern.new(copy, idx)
      self << tmp 
    end
    if blank >= 4
      copy = self[idx].val.dup
      copy[blank], copy[blank-4] = copy[blank-4], copy[blank]
      tmp = Pattern.new(copy, idx)
      self << tmp
    end
    if blank != 3 && blank != 7
      copy = self[idx].val.dup
      copy[blank], copy[blank+1] = copy[blank+1], copy[blank]
      tmp = Pattern.new(copy, idx)
      self << tmp
    end
    if blank != 0 && blank != 4
      copy = self[idx].val.dup
      copy[blank], copy[blank-1] = copy[blank-1], copy[blank]
      tmp = Pattern.new(copy, idx)
      self << tmp
    end
  end
end


def solve(val)
  pattern = Pattern.new(val, -1)
  que = PatternQue.new
  que << pattern
  return _solve(0, que)
end

def _solve(idx, que)
  i = 0
  while i < que.length
    if que[i].val == [9,1,2,3,4,5,6,7]

      #parent_idxをたどっていくことで回答への道筋が分かる
      k = i
      while k != -1
        show(que[k].val)
        k = que[k].parent_idx
      end
      return
    else
      que.add_next_pattern(i)
      i += 1
    end
  end
end

solve([1,2,9,3,4,5,6,7]) #この程度なら解ける(3手)
#solve([2, 1, 5, 9, 3, 7, 4, 6]) #メモリ爆発


 
■実行結果

[9, 1, 2, 3] #ゴール
[4, 5, 6, 7]
------
[1, 9, 2, 3]
[4, 5, 6, 7]
------
[1, 2, 9, 3]  #最初の状態
[4, 5, 6, 7]
------