I wrote a code in python for solving 8 puzzle problem using breadth first search algorithm but I got a hashing error instead in the line 'if child.state not in visited:'.
I wrote a code in python for solving 8 puzzle problem using breadth first search algorithm but I got a hashing error instead in the line 'if child.state not in visited:'.
I wrote a code in python for solving 8 puzzle problem using breadth first search algorithm but I got a hashing error instead in the line 'if child.state not in visited:'.
class Node:
def __init__(self, state, parent):
self.state = state
self.parent = parent
def get_children(node):
children = []
for i in range(3):
for j in range(3):
if node.state[i][j] == 0:
if (i >= 0) and (i != 2): #move down
new_state = list(node.state)
new_state[i][j], new_state[i+1][j] = new_state[i+1][j], new_state[i][j]
children.append(Node(new_state, node))
if (i <= 2) and (i != 0): #move up
new_state = list(node.state)
new_state[i][j], new_state[i-1][j] = new_state[i-1][j], new_state[i][j]
children.append(Node(new_state, node))
if j >= 0 and j != 2: #move right
new_state = list(node.state)
new_state[i][j], new_state[i][j+1] = new_state[i][j+1], new_state[i][j]
children.append(Node(new_state, node))
if j <= 2 and j != 0: #move left
new_state = list(node.state)
new_state[i][j], new_state[i][j-1] = new_state[i][j-1], new_state[i][j]
children.append(Node(new_state, node))
return tuple(children)
def bfs(initial_state, goal_state):
queue = [Node(initial_state, None)]
visited = set()
while queue:
node = queue.pop(0)
if node.state == goal_state:
return node
for child in get_children(node):
if child.state not in visited:
queue.append(child)
visited.add(child.state)
return None
initial_state = [[1, 2, 3],
[4, 5, 0],
[7, 8, 6]]
goal_state = [[1, 2, 3],
[4, 5, 6],
[7, 8, 0]]
solution = bfs(initial_state, goal_state)
if solution is not None:
print("Solution found")
path = []
node = solution
while node is not None:
path.append(node.state)
node = node.parent
path.reverse()
for state in path:
print(state)
else:
print("No solution found")
output:
Traceback (most recent call last):
File "D:\algorithms\8_puzzle.py", line 63, in <module>
solution = bfs(initial_state, goal_state)
File "D:\algorithms\8_puzzle.py", line 48, in bfs
if child.state not in visited:
TypeError: unhashable type: 'list'
I found two issues in your code: the first one is the unhashable type: python lists are mutable objects, and can't be hashed. A simple workaround is converting lists to tuples. Actually you need to convert also the sublists into tuples. A simple function that does it is
def to_tuple(x):
return (tuple(row) for row in mat )
The second problem (spoiler alert if you want to solve it by your own, stop reading here) is you're passing your list and you're not properly copying it.
You used new_state = list(node.state) and this does a shallow copy of the list. Shallow copy means that the lists inside of it are just copied by reference. You want to do a deepcopy (from copy import deepcopy) which copies also the subarrays of node.state
full solution
from copy import deepcopy
class Node:
def __init__(self, state, parent):
self.state = state
self.parent = parent
def to_tuple(mat):
return (tuple(row) for row in mat )
def get_children(node):
children = []
for i in range(3):
for j in range(3):
if node.state[i][j] == 0:
if (i >= 0) and (i != 2): #move down
new_state = deepcopy(node.state)
new_state[i][j], new_state[i+1][j] = new_state[i+1][j], new_state[i][j]
children.append(Node(new_state, node))
if (i <= 2) and (i != 0): #move up
new_state = deepcopy(node.state)
new_state[i][j], new_state[i-1][j] = new_state[i-1][j], new_state[i][j]
children.append(Node(new_state, node))
if j >= 0 and j != 2: #move right
new_state = deepcopy(node.state)
new_state[i][j], new_state[i][j+1] = new_state[i][j+1], new_state[i][j]
children.append(Node(new_state, node))
if j <= 2 and j != 0: #move left
new_state = deepcopy(node.state)
new_state[i][j], new_state[i][j-1] = new_state[i][j-1], new_state[i][j]
children.append(Node(new_state, node))
return tuple(children)
def bfs(initial_state, goal_state):
queue = [Node(initial_state, None)]
visited = set()
while queue:
node = queue.pop(0)
if node.state == goal_state:
return node
for child in get_children(node):
if to_tuple(child.state) not in visited:
queue.append(child)
visited.add(to_tuple(child.state))
return None
initial_state = [[1, 2, 3],
[4, 5, 0],
[7, 8, 6]]
goal_state = [[1, 2, 3],
[4, 5, 6],
[7, 8, 0]]
solution = bfs(initial_state, goal_state)
if solution is not None:
print("Solution found")
path = []
node = solution
while node is not None:
path.append(node.state)
node = node.parent
path.reverse()
for state in path:
print(state)
else:
print("No solution found")