# 8 puzzle solver using bfs

Tue Sep 26 2023 07:23:35 GMT+0000 (Coordinated Universal Time)

Saved by @ronin_78 #c++

```from collections import deque

visited_states = []
total_moves = 70
expanded = 0
count = 0

class Node:
def __init__(self, state, parent, operator, depth, cost):
self.state = state
self.parent = parent
self.operator = operator
self.depth = depth
self.cost = cost

def create_node(state, parent, operator, depth, cost):
return Node(state, parent, operator, depth, cost)

def expand_node(node):
expanded_nodes = []

temp_state = move_down(node.state)
temp_node = create_node(temp_state, node, "down", node.depth + 1, node.cost + 1)
expanded_nodes.append(temp_node)

temp_state1 = move_up(node.state)
temp_node1 = create_node(temp_state1, node, "up", node.depth + 1, node.cost + 1)
expanded_nodes.append(temp_node1)

temp_state2 = move_left(node.state)
temp_node2 = create_node(temp_state2, node, "left", node.depth + 1, node.cost + 1)
expanded_nodes.append(temp_node2)

temp_state3 = move_right(node.state)
temp_node3 = create_node(temp_state3, node, "right", node.depth + 1, node.cost + 1)
expanded_nodes.append(temp_node3)

return expanded_nodes

def move_left(state):
swap = state.copy()
idx = swap.index(0)
if (idx == 0 or idx == 3 or idx == 6):
return swap
else:
swap[idx - 1], swap[idx] = swap[idx], swap[idx - 1]
return swap

def move_right(state):
swap = state.copy()
idx = swap.index(0)
if (idx == 2 or idx == 5 or idx == 8):
return swap
else:
swap[idx + 1], swap[idx] = swap[idx], swap[idx + 1]
return swap

def move_up(state):
swap = state.copy()
idx = swap.index(0)
if (idx == 0 or idx == 1 or idx == 2):
return swap
else:
swap[idx - 3], swap[idx] = swap[idx], swap[idx - 3]
return swap

def move_down(state):
swap = state.copy()
idx = swap.index(0)
if (idx == 6 or idx == 7 or idx == 8):
return swap
else:
swap[idx + 3], swap[idx] = swap[idx], swap[idx + 3]
return swap

def bfs(start, goal):
if (start == goal):
return [None]
else:
to_be_expanded = []
current_node = create_node(start, None, None, 0, 0)
to_be_expanded.append(current_node)

for i in range(total_moves):
temp_expanded = []
size = len(to_be_expanded)

for j in range(size):
if (to_be_expanded[j] in visited_states):
continue

node_array = expand_node(to_be_expanded[j])

for x in range(4):
if (node_array[x].state == goal):
count = i + 1
return node_array[x]
else:
temp_expanded.append(node_array[x])
visited_states.append(node_array[x].state)

to_be_expanded.clear()
to_be_expanded = temp_expanded.copy()
temp_expanded.clear()

return None

def main():
method = 'bfs'
length = 0
x = 0
x = x + 1

board_input = input("Enter the initial state values (comma-separated): ")
board_split = board_input.split(',')
starting_state = [int(i) for i in board_split]

goal_input = input("Enter the goal state values (comma-separated): ")
goal_split = goal_input.split(',')
goal_state = [int(i) for i in goal_split]

if (len(starting_state) == 9 and len(goal_state) == 9):
result = bfs(starting_state, goal_state)
if result == None:
print("No solution found")
elif result == [None]:
print("Start node was the goal!")
else:
print("Total number of moves needed =", result.cost)
path = []
path.append(result.state)
current = result
flag = True

while flag:
parent = current.parent
prev_state = parent.state
path.append(prev_state)
current = parent

if (prev_state == starting_state):
flag = False

path.reverse()
print("Step-wise Sequence of states from start to goal is ")
for state in path:
print(state[0], "|", state[1], "|", state[2])
print(state[3], "|", state[4], "|", state[5])
print(state[6], "|", state[7], "|", state[8])
print()
else:
print("Invalid input")

if __name__ == "__main__":
main()

```
content_copyCOPY