title: N-queen backtracking in Python: how to return solutions instead of printing them?
body: <pre><code>def solve(n):
      #prepare a board
      board = [[0 for x in range(n)] for x in range(n)]
      #set initial positions
      place_queen(board, 0, 0)
  
  def place_queen(board, row, column):
      """place a queen that satisfies all the conditions"""
      #base case
      if row &gt; len(board)-1:
          print board
      #check every column of the current row if its safe to place a queen
      while column &lt; len(board):
          if is_safe(board, row, column):
              #place a queen
              board[row][column] = 1
              #place the next queen with an updated board
              return place_queen(board, row+1, 0)
          else:
              column += 1
      #there is no column that satisfies the conditions. Backtrack
      for c in range(len(board)):
          if board[row-1][c] == 1:
              #remove this queen
              board[row-1][c] = 0
              #go back to the previous row and start from the last unchecked column
              return place_queen(board, row-1, c+1)
  
  def is_safe(board, row, column):
      """ if no other queens threaten a queen at (row, queen) return True """
      queens = []
      for r in range(len(board)):
          for c in range(len(board)):
              if board[r][c] == 1:
                  queen = (r,c)
                  queens.append(queen)
      for queen in queens:
          qr, qc = queen
          #check if the pos is in the same column or row
          if row == qr or column == qc:
              return False
          #check diagonals
          if (row + column) == (qr+qc) or (column-row) == (qc-qr):
              return False
      return True
  
  solve(4)
  </code></pre>
  
  <p>I wrote Python code for N-queen problem and it prints every possible solution whenever it's found. However, I would like to modify this code so that it returns a list of all the solutions(board configurations) instead of printing them. I tried modifying the code like following:</p>
  
  <pre><code>def solve(n):
      #prepare a board
      board = [[0 for x in range(n)] for x in range(n)]
      #set initial positions
      solutions = []
      place_queen(board, 0, 0, solutions)
  
  def place_queen(board, row, column, solutions):
      """place a queen that satisfies all the conditions"""
      #base case
      if row &gt; len(board)-1:
          solutions.append(board)
          return solutions
      #check every column of the current row if its safe to place a queen
      while column &lt; len(board):
          if is_safe(board, row, column):
              #place a queen
              board[row][column] = 1
              #place the next queen with an updated board
              return place_queen(board, row+1, 0, solutions)
          else:
              column += 1
      #there is no column that satisfies the conditions. Backtrack
      for c in range(len(board)):
          if board[row-1][c] == 1:
              #remove this queen
              board[row-1][c] = 0
              #go back to the previous row and start from the last unchecked column
              return place_queen(board, row-1, c+1, solutions)
  </code></pre>
  
  <p>However, this returns as soon as the first solution is found, so <code>solutions</code> only consists of one possible board configuration. Since <em>print vs. return</em> has been confusing to me for backtracking algorithms, I would very much appreciate it if someone could show me how to modify the above code, and how to approach similar problems in future.</p>
  
  <p><em>I assume using a global variable would work, but I learned from somewhere that using global variables for such problem is discouraged. Could someone explain this too?</em></p>
  
  <p><strong>EDIT:</strong> </p>
  
  <pre><code>def solve(n):
      #prepare a board
      board = [[0 for x in range(n)] for x in range(n)]
      #set initial positions
      solutions = list()
      place_queen(board, 0, 0, solutions)
      return solutions
  
  def place_queen(board, row, column, solutions):
      """place a queen that satisfies all the conditions"""
      #base case
      if row &gt; len(board)-1:
          #print board
          solutions.append(deepcopy(board)) #Q1
      #check every column of the current row if its safe to place a queen
      while column &lt; len(board):
          if is_safe(board, row, column):
              #place a queen
              board[row][column] = 1
              #place the next queen with an updated board
              return place_queen(board, row+1, 0, solutions) #Q2
          else:
              column += 1
      #there is no column that satisfies the conditions. Backtrack
      for c in range(len(board)):
          if board[row-1][c] == 1:
              #remove this queen
              board[row-1][c] = 0
              #go back to the previous row and start from the last unchecked column
              return place_queen(board, row-1, c+1, solutions) #Q3
  </code></pre>
  
  <p>The above returns all the found solutions instead of printing them. I have a few more questions (related parts are marked Q1 and Q2 in above code)</p>
  
  <ol>
  <li>Why do we need to <code>solutions.append(deepcopy(board))</code>? In other words, what exactly is happening when we do <code>solutions.append(board)</code> and why does this lead to appending the initial board which is <code>[[0,0,0,0] ...]</code>?</li>
  <li>Why do we run into a problem when <code>return place_queen(board, row+1, 0)</code> is replaced by <code>place_queen(board, row+1, 0)</code>? We are not actually returning anything (or <code>None</code>), but without <code>return</code> the list goes out of index.</li>
  </ol>