Implemented breadth-first search and bidirectional search of the basic algorithm based on 8 puzzles
--Record the panel layout that has already appeared --Keep the panel arrangement that you have passed through in the puzzle object
class Queue:
'''
Queue class for storing puzzle objects
'''
def __init__(self, puzzle):
self.puzzle_list = []
self.puzzle_list.append(puzzle)
#Add puzzle to the end of the list
def enqueue(self, puzzle):
self.puzzle_list.append(puzzle)
#Get the puzzle from the top of the list
def dequeue(self):
return self.puzzle_list.pop(0)
#Check if the puzzle list is empty
def is_empty(self):
return len(self.puzzle_list) == 0
class Puzzle:
'''
Puzzle class with current panel layout, list of checked panel layouts, puzzle size
'''
def __init__(self, panel_list, state_list, size):
self.panel_list = panel_list
#A list that holds the state of the panel arrangement that you have passed through
self.state_list = state_list
self.state_list.append(panel_list)
self.size = size
#Generator that returns the panel layout when 0 on the panel is moved left, right, up and down
def gene_next_panel(self, puzzle):
zero_pos = puzzle.panel_list.index(0)
col = zero_pos // self.size
raw = zero_pos % self.size
def __get_next_panel():
panel_list = puzzle.panel_list[:]
n = panel_list[next_pos]
panel_list[next_pos] = 0
panel_list[zero_pos] = n
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 breadth_first(size, goal, panel_list):
puzzle = Puzzle(panel_list, [], size)
queue = Queue(puzzle)
checked_dict = {}
while queue.is_empty() is False:
puzzle = queue.dequeue()
for next_panel in puzzle.gene_next_panel(puzzle):
next_puzzle = Puzzle(list(next_panel), puzzle.state_list[:], size)
if next_panel in checked_dict:
continue
if list(next_panel) == goal:
return next_puzzle
#Record the panel layout that has already appeared
checked_dict[next_panel] = True
queue.enqueue(next_puzzle)
if __name__ == '__main__':
size = 3
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
panel_list = [5, 4, 2, 6, 7, 0, 8, 1, 3]
puzzle = breadth_first(size, goal, panel_list)
puzzle.result_print()
--Store the puzzle object in the confirmation dictionary --When the same panel layout appears in the past, you can check the passage record of the puzzle object that possessed the panel layout.
class Queue:
'''
Queue class for storing puzzle objects
'''
def __init__(self, puzzle):
self.puzzle_list = []
self.puzzle_list.append(puzzle)
#Add puzzle to the end of the list
def enqueue(self, puzzle):
self.puzzle_list.append(puzzle)
#Get the puzzle from the top of the list
def dequeue(self):
return self.puzzle_list.pop(0)
#Check if the puzzle list is empty
def is_empty(self):
return len(self.puzzle_list) == 0
class Puzzle:
'''
Puzzle class with current panel layout, list of checked panel layouts, puzzle size
'''
def __init__(self, panel_list, state_list, size, direction):
self.panel_list = panel_list
self.state_list = state_list
self.state_list.append(panel_list)
self.size = size
self.direction = direction
def gene_next_panel(self, puzzle):
zero_pos = puzzle.panel_list.index(0)
col = zero_pos // self.size
raw = zero_pos % self.size
def __get_next_panel():
panel_list = puzzle.panel_list[:]
n = panel_list[next_pos]
panel_list[next_pos] = 0
panel_list[zero_pos] = n
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 back_result_print(self):
for s in self.state_list[::-1]:
print(s)
def bidirectional_search(size, goal, panel_list):
start_puzzle = Puzzle(panel_list, [], size, 'S')
queue = Queue(start_puzzle)
goal_puzzle = Puzzle(goal, [], size, 'G')
queue.enqueue(goal_puzzle)
checked_dict = {}
checked_dict[tuple(panel_list)] = start_puzzle
checked_dict[tuple(goal)] = goal_puzzle
while queue.is_empty() is False:
puzzle = queue.dequeue()
for next_panel in puzzle.gene_next_panel(puzzle):
if next_panel in checked_dict:
checked_puzzle = checked_dict[next_panel]
if checked_puzzle.direction != puzzle.direction:
return puzzle, checked_puzzle
else:
new_puzzle = Puzzle(list(next_panel), puzzle.state_list[:], size, puzzle.direction)
#Store the puzzle in the confirmation dictionary
checked_dict[next_panel] = new_puzzle
queue.enqueue(new_puzzle)
if __name__ == '__main__':
size = 3
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
panel_list = [5, 4, 2, 6, 7, 0, 8, 1, 3]
front_puzzle, back_puzzle = bidirectional_search(size, goal, panel_list)
front_puzzle.result_print()
back_puzzle.back_result_print()
-Algorithms with Python / Breadth-first search and iterative deepening
Recommended Posts