build a perfect maze recursively in python
Question: I have this project to build a perfect maze recursively by using python. I
have a MyStack class which creates a stack to track the path that I go
through. And a Cell class which represent each square within the maze and
store some information. I think I complete the code but IDLE gives me some
error that I couldn't figure out. Here is the code.

    
    
    from random import *
    from graphics import *
    
    class MyStack:
    
        def __init__(self):
            self.S = []
    
        def push(self, item):
            self.S.insert(0, item)
    
        def pop(self):
            return self.S.pop(0)
    
        def isEmpty(self):
            return True if len(self.S) == 0 else False
    
        def size(self):
            return len(self.S)
    
    class Maze:
        def __init__(self, N):
    
            self.size = N
            self.maze = [[i for i in range(N + 2)] for i in range(N + 2)]
    
            for r in range(self.size + 2):
                for c in range(self.size + 2):
                    self.maze[r][c] = Cell()
    
        def walk(self, s, x, y):
    
            neighboor = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
    
            if s.size() == self.size**2: return
    
            else:
                new = choice(neighboor)
    
                while self.maze[new[0]][new[1]].getVisit():
    
                    while new[0] < 1 or new[1] > self.size:
    
                        new = choice(neighboor)
    
                    if neighboor != []: new = choice(neighboor.remove(new))
                    else:
                        temp = s.pop(s)
                        x, y = temp[0], temp[1]
                        self.walk(s, x, y)
    
                if new == neighboor[0]:
                    self.maze[x][y].changeNorth()
                    self.maze[new[0]][new[1]].changeSouth()
                elif new == neighboor[1]:
                    self.maze[x][y].changeSouth()
                    self.maze[new[0]][new[1]].changeNorth()
                elif new == neighboor[2]:
                    self.maze[x][y].changeEast()
                    self.maze[new[0]][new[1]].changeWest()
                elif new == neighboor[3]:
                    self.maze[x][y].changeWest()
                    self.maze[new[0]][new[1]].changeEast()
    
    
                s.push(new)
    
                self.walk(s, new[0], new[1])
    
        def search(self):
            startX, startY = randint(1, self.size), randint(1, self.size)
    
            s = MyStack()
    
            temp = (startX, startY)
    
            s.push(temp)
    
            self.maze[startX][startY].changeVisit()
    
            self.walk(s, startX, startY)
    
        def draw(self):
    
            win = GraphWin()
    
            startXY = Point(27, 27)
            start = Circle(startXY, 5)
            start.setOutline('orange')
            start.setFill('orange')
            start.draw(win)
    
            x, y = 20, 20
    
    
            for r in range(1, self.size + 1):
                for c in range(1, self.size + 1):
                    if self.maze[r][c].getNorth():
                        unit = Line(Point(x, y), Point(x + 15, y))
                        unit.draw(win)
    
                    x, y = x + 15, y
    
                x, y = 20, y + 15
    
            x, y = 20, 20
            for c in range(1, self.size + 1):
                for r in range(1, self.size + 1):
                    if self.maze[r][c].getWest():
                        #print(self.maze[r][c].getWest())
                        unit = Line(Point(x, y), Point(x, y + 15))
                        unit.draw(win)
    
                    x, y = x, y + 15
    
                x, y = x + 15, 20
    
            x, y = 20, self.size * 15 + 20
            for c in range(1, self.size + 1):
                if self.maze[self.size][c].getSouth():
                    unit = Line(Point(x, y), Point(x + 15, y))
                    unit.draw(win)
                x, y = x + 15, y
    
            x, y = self.size * 15 + 20, 20
            for r in range(1, self.size + 1):
                if self.maze[self.size][c].getEast():
                    unit = Line(Point(x, y), Point(x, y + 15))
                    unit.draw(win)
                x, y = x, y + 15
    
    class Cell:
        def __init__(self):
            #self.x = x
            #self.y = y
            self.north = True
            self.south = True
            self.east = True
            self.west = True
            self.visit = False
    
        def changeVisit(self):
            self.visit = True
    
        def changeNorth(self):
            self.north = False
    
        def changeSouth(self):
            self.south = False
    
        def changeEast(self):
            self.east = False
    
        def changeWest(self):
            self.west = False
    
        def getVisit(self):
            return self.visit
    
        def getNorth(self):
            return self.north
    
        def getSouth(self):
            return self.south
    
        def getEast(self):
            return self.east
    
        def getWest(self):
            return self.west
    

Here is the Error I got:

    
    
    >>> a = Maze(5)
    >>> a.search()
    Traceback (most recent call last):
      File "<pyshell#1>", line 1, in <module>
        a.search()
      File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 91, in search
        self.walk(s, startX, startY)
      File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk
        self.walk(s, new[0], new[1])
      File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk
        self.walk(s, new[0], new[1])
      File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk
        self.walk(s, new[0], new[1])
      File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk
        self.walk(s, new[0], new[1])
      File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk
        self.walk(s, new[0], new[1])
      File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk
        self.walk(s, new[0], new[1])
      File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk
        self.walk(s, new[0], new[1])
      File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk
        self.walk(s, new[0], new[1])
      File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 76, in walk
        self.walk(s, new[0], new[1])
      File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 48, in walk
        while self.maze[new[0]][new[1]].getVisit():
    IndexError: list index out of range
    

I'm new to programming, any help would be appreciate. Thank you~

After fix the previous one, I got an error for the line

    
    
        if len(neighboor) != 0: new = choice(neighboor.remove(new))
    

The error message is

    
    
    Traceback (most recent call last):
    
    
    File "<pyshell#11>", line 1, in <module>
        a.search()
      File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 88, in search
        self.walk(s, startX, startY)
      File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 73, in walk
        self.walk(s, new[0], new[1])
      File "C:\Users\Serena\Desktop\XAproject\Stack.py", line 52, in walk
        if len(neighboor) != 0: new = choice(neighboor.remove(new))
      File "C:\Python34\lib\random.py", line 253, in choice
        i = self._randbelow(len(seq))
    TypeError: object of type 'NoneType' has no len()
    

But I define 'neighboor' as a list, it should has a len()

Thank you so much for help! plzplz~


Answer: The problem is that you're not ensuring that the steps in your walk are valid.

The way you have it currently, `walk` could pick a `neighboor` that is out of
the bounds of the maze. For example, if a maze is 5x5, attempting to access
`maze[5][?]` or `maze[?][5]` will result in an `IndexError` like you get.

To fix this, you could define an `is_valid` method for your maze class, e.g.:

    
    
    def is_valid(self, x, y):
        return (0 <= x < self.size) and (0 <= y < self.size)
    

Then, you when you pick a `neighboor`, you ensure it's valid:

    
    
    #...
    else:
        new = choice(neighboor)
        while self.is_valid(new[0], new[1]) == False:
            new = choice(neighboor)
    
        while self.maze[new[0]][new[1]].getVisit():
    #...
    

This snippet picks a `neighboor`, then, if it's not valid, regenerates `new`
until it finds a valid one.

But this loop would be better written as:

    
    
    #...
    else:
        while True:
            new = choice(neighboor)
            if self.is_valid(new[0], new[1]): break
    
        while self.maze[new[0]][new[1]].getVisit():
    #...
    

There are more problems with your code, however, as you'll eventually see, but
this will get you past this specific one.

