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.
CodePudding user response：
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
CodePudding user response：
You don't really have "two identical list", you only have one list object that you're returning twice. To avoid modifying the original list and also two work with different lists, you should pass copies around.
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(states, pos1, pos2):
first = states.pop(pos1)
second = states.pop(pos2-1)
states.insert(pos1,second)
states.insert(pos2,first)
return states
def find_new_nodes(states):
if loc_of_zero == 0:
right = swap_positions(states.copy(),0,1) # pass around a copy
left = swap_positions(states.copy(),0,3) # pass around a copy
return(right,left)
find_zero(initial_state)
print(find_new_nodes(initial_state))
Side note 1: I have renamed your vairable list to states, otherwise it would shadow the built in list function
Side note 2: find_new_nodes did not work with the parameter, instead it used the global list. I changed that, too.
Side note 3: There are different ways to create a copy of your (shallow) list. I think list.copy() is the most verbose one. You could also use the copy module, use [:] or something else.
Output:
([1, 0, 3, 4, 2, 5, 7, 8, 6], [4, 1, 3, 0, 2, 5, 7, 8, 6])
CodePudding user response：
Ok, first of all, some thoughts...
Try to not use "list" as a variable, it's a Python identifier for "list" type. It seems that you are redefining the term.
Usually, it's a bad idea to use global vars such as loc_of_zero.
About your problem:
I believe that the problem is that you are getting a lot of references of the same variable. Try to avoid it. One idea:
from copy import deepcopy
def swap_positions(list0, pos1, pos2):
list1 = deepcopy(list0)
first = list1.pop(pos1)
second = list1.pop(pos2-1)
list1.insert(pos1,second)
list1.insert(pos2,first)
return list1