title: 8 queens puzzle - recursion using python
body: <p>I’m trying to solve the <a href="http://en.wikipedia.org/wiki/Eight_queens_puzzle" rel="nofollow">8-queens puzzle</a>, also known as n-queens algorithm.</p>
  
  <p>My function should count how many legal ways are there to place N queens on NxN board.</p>
  
  <p>I almost got it, but had to do some ugly patch to make it work.
  Can you help me fix it?</p>
  
  <p>A brief on What I did:
  Trying to find out how many legal ways are there to set N queens in NxN table, 
  I was trying to solve using recursion on a (N-1)xN case (Removing first column)
  As for the fact no two queens are allowed on the same column, I use a list length of N. 
  Each cell represents a column and in each column I set the row number of where the queen is set.</p>
  
  <p>For example, </p>
  
  <pre><code>[0, 4, 7, 5, 2, 6, 1, 3]
  </code></pre>
  
  <p>Means that:</p>
  
  <ul>
  <li>Column 0 – queen placed in row 0</li>
  <li>Column 1 – queen placed in row 4</li>
  <li>Column 2 – queen placed in row 7</li>
  <li>Column 3 – queen placed in row 5</li>
  <li>Column 4 – queen placed in row 2</li>
  <li>Column 5 – queen placed in row 6</li>
  <li>Column 6 – queen placed in row 1</li>
  <li>Column 7 – queen placed in row 3</li>
  </ul>
  
  <p>The thing that bothers me is that I have no idea how to omit the illegal queen placing.
  So to make it work, I uses a global variable named <code>sum</code>, increment it only when recursion reaches a fully placed arrangement of queens which is legal.</p>
  
  <pre><code>def is_available(n, table, column, N):
      return not any(t in (n, n - i, n + i)
                     for t, i in zip(table, range(column, 0, -1)))
  
  def queens_sum(N):
      table = [0]*N
      global sum
      sum = 0
      solve(N, table, 0, len(table))
      return sum
  
  def solve(N, table, column, end):
  
      global sum
  
      if column == end:
          sum += 1
          return None
  
      for n in range(N):
          # if no other queen can attack here, place a queen in this row 
          if is_available(n, table, column, N):
              table[column] = n
              # Omit the current column at the start
              solve(N, table, column+1, end)
          #else: we can't place queen here, we should abort this direction
              # do nothing
  </code></pre>
  
  <p>For <code>N = 8</code> I get <code>sum = 92</code>.. therefore I know it works, but I want to avoid this global counter.</p>
  
  <p>can you help?</p>