got a hashing error while coding 8 puzzle problem using bfs in python

Question

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'

Answer 1

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")