How to generate more than one list from a list, using python functions

I am trying to make a 8 puzzle problem solver using different algorithms, such as BFS,DFS, A* etc. using python. For those who are not familiar with the problem, 8 puzzle problem is a game consisting of 3 rows and 3 columns. You can move the empty tile only horizontally or vertically, 0 represents the empty tile. It looks like this (I couldn’t add the images due to my accounts reputation.):

https://miro.medium.com/max/679/1*yekmcvT48y6mB8dIcK967Q.png

initial_state = [0,1,3,4,2,5,7,8,6]
goal_state = [1,2,3,4,5,6,7,8,0]
    
def find_zero(state):
       global loc_of_zero
       loc_of_zero = (state.index(0))


def swap_positions(list, pos1, pos2):
       first = list.pop(pos1)
       second = list.pop(pos2-1)

       list.insert(pos1,second)
       list.insert(pos2,first)
       return list

 def find_new_nodes(state):
      if loc_of_zero == 0:
         right = swap_positions(initial_state,0,1)
         left = swap_positions(initial_state,0,3)
         return(right,left)




find_zero(initial_state)
print(find_new_nodes(initial_state))   

The problem I have is this, I want the function “find_new_nodes(state)” return 2 different lists, so I can choose the most promising node, depending on the algorithm) and so on. But the output of my code consists of two identical lists.

This is my output: ([4, 0, 3, 1, 2, 5, 7, 8, 6], [4, 0, 3, 1, 2, 5, 7, 8, 6])

What can I do to make it return 2 different lists? My goal is to return all possible moves depending on where the 0 is, using the find_new_nodes function. Apologies if this is an easy question, This is my first time making a project this complicated.

Answer

The problem is that swap_positions obtains a reference to the global initial_state and not a clone of it. So both calls to swap_positions mutate the same array. A solution would be to clone the array on the first call: right = swap_positions(initial_state[:],0,1)

probably a better solution for swap_positions would also be:

# please do not name variables same as builtin names
def swap_positions(lis, pos1, pos2):
       # create a new tuple of both elements and destruct it directly
       lis[pos1], lis[pos2] = lis[pos2], lis[pos1]
       return lis

see also here