深さ優先探索（非再帰型）と下限値枝刈り法（Python編）

[前回](http://qiita.com/masashi0127/items/63d4f5b52895af939fca)に引き続き、8パズルを題材にして、基本アルゴリズムの深さ優先探索を、下限値枝刈り法を使って実装

# 手順
1. 開始パズルを生成
2. 開始パズルをスタックに格納
3. スタックの先頭からパズルを取得
4. パズルのパネル配置がゴールなら終了
5. ゴール以外なら、パズルを上下左右に移動させたときのパズルを新規作成
6. そのパズルのパネル配置の「マンハッタン距離 + 履歴手数」が下限値31以内であるか確認
7. 下限値以上であれば次の方角で5から繰り返す
8. そのパズルのパネル配置が出現済みかどうかと履歴手数を確認
9. 出現済みかつ、そのパズルの履歴手数の方が大きければ、別の方角のパズルで5から繰り返す
10. スタックにパズルを格納し、履歴リストに履歴を格納
11. 5 から 10 までを、各方角のパズルに対して繰り返す
12. 3 から 11 までを、スタックが空になるまで続ける

# ポイント
- スタックを使用する
- マンハッタン距離の枝刈りで高速化

```py
class Stack:

    def __init__(self, puzzle):
        self.puzzle_list = []

        self.puzzle_list.append(puzzle)

    def push(self, puzzle):
        self.puzzle_list.insert(0, puzzle)

    def pop(self):
        return self.puzzle_list.pop(0)

    def is_empty(self):
        return len(self.puzzle_list) == 0

class Puzzle():

    def __init__(self, panel_list, state_list, size):
        self.panel_list = panel_list
        self.state_list = state_list
        self.state_list.append(panel_list)
        self.size = size
        self.distance = 0

        def manhattan():
            for d, panel in enumerate(self.panel_list):

                if panel > 0:
                    self.distance += abs((panel - 1) // 3 - d // 3 + (panel - 1) % 3 - d % 3)

        manhattan()

    def gene_next_panel(self):
        zero_pos = self.panel_list.index(0)

        col = zero_pos // self.size
        raw = zero_pos % self.size

        def get_next_panel():
            panel_list = self.panel_list[:]
            n = panel_list[next_pos]
            panel_list[next_pos] = 0
            panel_list[zero_pos] = n
            # 移動距離の差分を計算
            self.distance += zero_pos // 3 - next_pos // 3 + zero_pos % 3 - next_pos % 3
            return panel_list

        if self.size > col + 1:
            next_pos = (col + 1) * self.size + raw
            panel_list = get_next_panel()
            yield tuple(panel_list)

        if col - 1 >= 0:
            next_pos = (col - 1) * self.size + raw
            panel_list = get_next_panel()
            yield tuple(panel_list)

        if self.size > raw + 1:
            next_pos = col * self.size + raw + 1
            panel_list = get_next_panel()
            yield tuple(panel_list)

        if raw - 1 >= 0:
            next_pos = col * self.size + raw - 1
            panel_list = get_next_panel()
            yield tuple(panel_list)

    def result_print(self):

        for s in self.state_list:
            print(s)


def depth_first(panel_list, goal, size):
    puzzle = Puzzle(panel_list, [], size)
    stack = Stack(puzzle)
    checked_dict = {}
    cnt = 0

    while stack.is_empty() is False:
        next_puzzle = stack.pop()

        if next_panel.panel_list == goal:
            return next_puzzle

        for new_panel in next_puzzle.gene_next_panel():
            new_puzzle = Puzzle(list(new_panel), next_puzzle.state_list[:], size)

            # 下限枝刈り法にマンハッタン距離を使用
            # 現在のパネル配置と履歴手数の合計が最長手数31以内かチェック
            # -2 はスタートとゴールのパネル配置が state_list に含まれているため減算
            if new_puzzle.distance + len(new_puzzle.state_list) - 2 >= 31:
                continue

            # 過去に出現したパネル配置の場合、その配置を保持するパズルとチェック中のパズルの手数を比較
            if new_panel in checked_dict and len(new_puzzle.state_list) > checked_dict[new_panel]:
                continue

            checked_dict[new_panel] = len(new_puzzle.state_list)
            stack.push(new_puzzle)

    return False


if __name__ == '__main__':
    panel_list = [5, 4, 2, 6, 7, 0, 8, 1, 3]
    goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
    size = 3

    puzzle = depth_first(panel_list, goal, size)

    if puzzle is not False:
        puzzle.result_print()
```

# 参考
[Algorithms with Python幅優先探索と反復深化](http://www.geocities.jp/m_hiroi/light/pyalgo27.html)