【Ruby】【アルゴリズム】7パズルを解く。メモリ爆発Ver
7パズルとは
8つのタイルと一つのスペースがあり、それぞれに数が書いてある。
タイルを上下左右にすべらせ、最終状態にする。ただし、枠からはみ出してはいけない[最終状態] ※9は空白を表す
9123
4567
この本に載ってる問題だよ↓
- 作者: 紀平拓男,春日伸弥
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2011/03/30
- メディア: 単行本
- 購入: 15人 クリック: 255回
- この商品を含むブログ (30件) を見る
嵌ったところメモ
・確認した版の状態(配列)を履歴として全てキューに格納していたためメモリが爆発した
⇒配列を数値に変換してから格納する
・すでに確認した版も繰り返し確認していた
⇒状態保持キューの中に対象の版がすでに存在した場合はキューに格納しない、の実装を忘れていた
実装コード
#表示用 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] ------