[GO] Depth-first search (non-recursive type) and lower limit pruning method (Python edition)

Continuing from previous, we implemented a depth-first search of the basic algorithm using the lower limit pruning method, using 8 puzzles as the theme.

procedure

1. Generate a start puzzle
2. Store the start puzzle on the stack
3. Get the puzzle from the top of the stack
4. Finish if the puzzle panel layout is the goal
5. Create a new puzzle when you move the puzzle up / down / left / right except for the goal
6. Check if the "Manhattan distance + history effort" in the panel layout of the puzzle is within the lower limit of 31
7. If it is above the lower limit, repeat from 5 in the next direction.
8. Check if the panel layout of the puzzle has already appeared and the history
9. If it has appeared and the history of the puzzle is larger, repeat from 5 with a puzzle in another direction.
10. Store the puzzle on the stack and store the history in the history list
11. Repeat steps 5 to 10 for puzzles in each direction
12. Continue from 3 to 11 until the stack is empty

point

--Use the stack --Speed up by pruning Manhattan distance

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
            #Calculate the difference in travel distance
            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)

            #Use Manhattan distance for lower pruning method
            #Check if the total of the current panel layout and history steps is within the maximum number of steps 31
            # -2 is the state of the start and goal panel layout_Subtract because it is included in list
            if new_puzzle.distance + len(new_puzzle.state_list) - 2 >= 31:
                continue

            #For panel arrangements that appeared in the past, compare the number of puzzles that hold the arrangement with the puzzle that is being checked.
            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()

reference

Algorithms with Python breadth-first search and iterative deepening