木の立方体パズルの全探索
→ 
帰りのロマンスカーで書いた。最初最中限オンラインにAIを追加しようと思ったのだけど時間がかかりそうだったからやめてこっちにした。簡単だと思ったので。
PUZZLE = [3, 3, 3, 3, 2, 2, 2, 3, 3, 2, 2, 3, 2, 3, 2, 2, 3] START = (0, 0, 0) INIT_DIR = (0, 0, 1) def get_candidate(dir): cs = [(0, 1), (1, 0), (0, -1), (-1, 0)] if dir[0]: return [(0, x, y) for x, y in cs] if dir[1]: return [(y, 0, x) for x, y in cs] if dir[2]: return [(x, y, 0) for x, y in cs] def recur(pos=START, dir=INIT_DIR, idx=0, stack=[], used=[START], max_bound=[0] * 3, min_bound=[0] * 3): for i in range(PUZZLE[idx] - 1): pos = tuple(pos[x] + dir[x] for x in range(3)) if pos in used: return # conflict for x in range(3): if max_bound[x] < pos[x]: max_bound[x] = pos[x] if min_bound[x] > pos[x]: min_bound[x] = pos[x] if max_bound[x] - min_bound[x] > 2: return # out of bound used.append(pos) stack.append(dir) if idx == len(PUZZLE) - 1: print stack return for cdir in get_candidate(dir): recur(pos, cdir, idx + 1, stack[:], used[:], max_bound[:], min_bound[:]) recur()
出力は8つ出る。これは視点と最初の辺の方向を固定しているので「2本目の辺が4方向のどちらに出るか4通り」×「その2本の辺が貼る平面から最初に外れるときにどちら側に出るか2通り」の8通り。最初の解だけ表示してみる。
[(0, 0, 1), (0, 1, 0), (0, 0, -1), (1, 0, 0), (0, 0, 1), (-1, 0, 0), (0, 0, 1), (0, -1, 0), (0, 0, -1), (1, 0, 0), (0, 1, 0), (-1, 0, 0), (0, 0, 1), (1, 0, 0), (0, -1, 0), (0, 0, 1), (0, 1, 0)]
半分くらいまで実際のパズルと見比べてみたら正しかった。子を探索するときにコピーして渡しているの遅いかなと思いつつ走らせてみたら0.09秒で結果が出た。余裕すぎる。パズルの記述はめんどくさいので修正しなかったけど辺のブロックの個数で3とか2とか書くより、ブロックを点と見た場合の辺の長さで2とか1とかにする方がコードが奇麗だったな。あと終了条件は「usedが27個であること」でもいいね。大差ないけど。変数名を書き換えるとしたらstackはdirs、get_candidateはget_next_dirs、cdirはnext_dirにするな。
id:tokorotenと話していた「状態空間としては4 ** 16だから単純に全探索して余裕だし、枝刈りがバリバリ刈れるからもっと速いだろう」という話の検証。
dirs.append(dir) idx += 1 print "+" * idx if idx == len(PUZZLE): print dirs # finished return if idx == 1: next_dirs = [(0, 1, 0)] elif idx == 2: next_dirs = [(0, 0, -1), (1, 0, 0)] elif idx == 3: next_dirs = [(1, 0, 0)] else: next_dirs = get_next_dirs(dir) for next_dir in next_dirs: recur(pos, next_dir, idx, dirs[:], used[:], max_bound[:], min_bound[:])
って感じに書き換えて走らせてみる。
+ ++ +++ ++++ +++++ ++++++ +++++++ +++++++ +++++++ ++++++++ ++++++ +++++++ ++++++++ +++++++++ ++++++++++ +++++++++++ ++++++++++++ +++++++++++++ +++++++++++++ ++++++++++++++ +++++++++++ +++++++++++ ++++++++++ +++++++++++ +++++++++++ ++++++++++++ +++++++++++++ +++++++++++++ ++++++++++++ +++++++++++++ ++++++++++++++ +++++++++++++++ ++++++++++++++++ ++++++++++++++++ +++++++++++++++ ++++++++++++++++ +++++++++++++++++ [(0, 0, 1), (0, 1, 0), (0, 0, -1), (1, 0, 0), (0, 0, 1), (-1, 0, 0), (0, 0, 1), (0, -1, 0), (0, 0, -1), (1, 0, 0), (0, 1, 0), (-1, 0, 0), (0, 0, 1), (1, 0, 0), (0, -1, 0), (0, 0, 1), (0, 1, 0)] +++++++ +++++ ++++++ +++++++ +++++++ +++++++ ++++++ +++++++ +++++++ ++++++++ +++++++++ ++++++++++ +++++++++++ ++++++++++++ +++++++++++++ +++++++++++++ +++++++++++ ++++++++++ +++++++++++ ++++++++++++ +++++++++++++ ++++++++++++++ +++++++++++++ +++++++++++ +++
うは、めちゃくちゃ木が小さいじゃんww
書いてから気づいたけどもidx == 3の時にはもう2通りあるので更に3倍あるとしても、この70個くらい×大体3倍×可能な次の4方向でせいぜい1000個も探索すれば十分回答が出るだろうというレベル。簡単すぎる。
