title: Backtracking and recursion in the n-queens problem (Python)
body: <p>I am writing a python class to find a solution to the 8 queens problem. How can I implement backtracking properly in my <code>solve</code> method? I think the recursion should work, however, the program stops after the solution is not found on the first try, and backtracking does not take place. All helper methods work properly.</p>
  
  <pre><code>EMPTY = 0
  QUEEN = 1
  RESTRICTED = 2
  
  class Board:
  
      # initializes a 8x8 array
      def __init__ (self):
          self.board = [[EMPTY for x in range(8)] for y in range(8)]
  
      # pretty prints board
      def printBoard(self):
          for row in self.board:
              print(row)
  
      # places a queen on a board
      def placeQueen(self, x, y):
          # restricts row
          self.board[y] = [RESTRICTED for i in range(8)]
  
          # restricts column
          for row in self.board:
              row[x] = RESTRICTED
  
          # places queen
          self.board[y][x] = QUEEN
  
          self.fillDiagonal(x, y, 0, 0, -1, -1)   # restricts top left diagonal
          self.fillDiagonal(x, y, 7, 0, 1, -1)    # restructs top right diagonal
          self.fillDiagonal(x, y, 0, 7, -1, 1)    # restricts bottom left diagonal
          self.fillDiagonal(x, y, 7, 7, 1, 1)     # restricts bottom right diagonal
  
      # restricts a diagonal in a specified direction
      def fillDiagonal(self, x, y, xlim, ylim, xadd, yadd):
          if x != xlim and y != ylim:
              self.board[y + yadd][x + xadd] = RESTRICTED
              self.fillDiagonal(x + xadd, y + yadd, xlim, ylim, xadd, yadd)
  
      # recursively places queens such that no queen shares a row or
      # column with another queen, or in other words, no queen sits on a
      # restricted square. Should solve by backtracking until solution is found.
      def solve(self, queens):
          if queens == 8:
              return True
  
          for i in range(8):
              if self.board[i][queens] == EMPTY:
                  self.placeQueen(queens, i)
  
                  if self.solve(queens - 1):
                      return True
  
                  self.board[i][queens] = RESTRICTED
  
          return False
  
  b1 = Board()
  b1.solve(7)
  b1.printBoard()
  </code></pre>
  
  <p>Is my problem in the lack of a deep copy of the board before adding the queen, or is it just a lack of backtracking?</p>