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.
--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()
Algorithms with Python breadth-first search and iterative deepening
Recommended Posts