List.append() changing all elements to the appended item

Question

I seem to have a problem with my maze generating program made in Python. I'm trying to randomly create a path that branches out at select points, with the points getting stored as it goes along. When the maze gets to a dead end, it will sort back through the visited points by testing the top value than popping that and going to the next one, until it gets to a spot where it isn't a dead end. However, when I try to append items to the list I'm using to save the spaces I've been to, something strange happens, I've never seen it before actually. Here's the code, and the best way to see it is to run it a through times until it goes all the way through. I haven't really found a way to counter the dead end problem, so if anyone could help me with that also, that would be great.

import random

width = 8

def check(x,y):
    """Figures out the directions that Gen can move while"""
    if x-1 == -1:
        maze[x][y][3] = 0 

    if x+1 == 8:
        maze[x][y][1] = 0

    if y+1 == 8:
        maze[x][y][2] = 0

    if y-1 == -1:
        maze[x][y][0] = 0

    if x + 1 in range(0,8) and visited[x+1][y] == False:
        maze[x][y][1] = 2

    if x - 1 in range(0,8) and visited[x-1][y] == False:
        maze[x][y][3] = 2

    if y + 1 in range(0,8) and visited[x][y+1] == False:
        maze[x][y][2] = 2

    if y - 1 in range(0,8) and visited[x][y-1] == False:
        maze[x][y][0] = 2



def Gen(x,y):
    visited[x][y] = True
    past.append(current)
    dirs = []
    check(x,y)
    print current

    if maze[x][y][0] == 2:
        dirs.append(0)
    if maze[x][y][1] == 2:
        dirs.append(1)
    if maze[x][y][2] == 2:
        dirs.append(2)
    if maze[x][y][3] == 2:
        dirs.append(3)

    pos = random.choice(dirs)

    print dirs

    maze[x][y][pos] = 1  

    if pos == 0:
        current[1] -= 1
    if pos == 1:
        current[0] += 1
    if pos == 2:
        current[1] += 1
    if pos == 3:
        current[0] -= 1

    if maze[x][y][0] == 4:
        maze[x][y][0] = 1

    if maze[x][y][1] == 4:
        maze[x][y][1] = 1

    if maze[x][y][2] == 4:
        maze[x][y][2] = 1

    if maze[x][y][3] == 4:
        maze[x][y][3] = 1

    print maze[x][y]
    print past, '\n'


#Build the initial values for the maze to be replaced later
maze = []
current = [0,0]
visited = []
past = []

#Generate empty 2d list with a value for each of the xy coordinates
for i in range(0,width):
    maze.append([])
    for q in range(0, width):
        maze[i].append([])
        for n in range(0, 4):
            maze[i][q].append(4)

#Makes a list of falses for all the non visited places
for x in range(0, width):
    visited.append([])
    for y in range(0, width):
        visited[x].append(False)

#Generates the walls
#for q in range(0, width):
#    for i in range(0, width):
#        check(q, i)

current = [0,0]

while current != [7,7]:
    Gen(current[0], current[1])
print maze

As you can see, it starts at 0,0 and then figures out the possible paths to take. It randomly selects from those and sets the value for that side of the room in 0,0 to 1, which means a passage. 2 means wall and 0 means out of bounds. 4 is just a placeholder as all values should be filled by the time the maze is completely generated.

If anyone could help me, that would be great and very appreciated. Thanks in advance.

Solution

I believe the current list is simply copied multiple times into past. So you have multiple copies of the same list.

To fix: in the line past.append(current) (two lines below def Gen(x,y):), change it to past.append(current[:]).

The notation list[:] creates a copy of the list. Technically, you are creating a slice of the whole list.

By the way, a better solution would be to not use a global current variable :)