【Ruby】【アルゴリズム】７パズルを解く。メモリ大丈夫Ver

前に書いた実装はメモリが爆発したけど、
こちらは大丈夫なVersionです。

7パズルの説明などは 爆発Verの記事を参照ください

改善点

・オブジェクトのハッシュ化
・重複確認

コード

#表示用
def show(panel)
puts panel.to_s[0..3]
puts panel.to_s[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)
    i = 0
    while i < self.length  #<= ポイント！
      return self if self[idx].val == self[i].val && i != idx 
      i += 1
    end
    blank = _dehash(self[idx].val).index(9)
    if blank < 4
      copy = _dehash(self[idx].val).dup
      copy[blank], copy[blank+4] = copy[blank+4], copy[blank]
      tmp = Pattern.new(_hash(copy), idx)
      self << tmp 
    end
    if blank >= 4
      copy = _dehash(self[idx].val).dup
      copy[blank], copy[blank-4] = copy[blank-4], copy[blank]
      tmp = Pattern.new(_hash(copy), idx)
      self << tmp
    end
    if blank != 3 && blank != 7
      copy = _dehash(self[idx].val).dup
      copy[blank], copy[blank+1] = copy[blank+1], copy[blank]
      tmp = Pattern.new(_hash(copy), idx)
      self << tmp
    end
    if blank != 0 && blank != 4
      copy = _dehash(self[idx].val).dup
      copy[blank], copy[blank-1] = copy[blank-1], copy[blank]
      tmp = Pattern.new(_hash(copy), idx)
      self << tmp
    end
  end
end

def _hash(arr)      #<= ポイント！
  return arr.join.to_i
end
def _dehash(str)
  str.to_s.split("").map!{|ch| ch.to_i}
end
def solve(val)
  pattern = Pattern.new(_hash(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 == 91234567
      #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
  p "arimasen"
end
solve([2, 7, 4, 1, 5, 9, 3, 6])

実行結果

･･･続きは黒い画面で！
2941
5736
------
2741
5936
------

ようやくアルゴリズムが分かってきた。