N Queens Problem
by Isai Damier, Android Engineer @ Google

#=======================================================================
# Author: Isai Damier
# Title: N Queens Problem
# Project: geekviewpoint
# Package: algorithms
#
# Description: This function solves the following classic
#    problem: Given an n by n chessboard, place n queens on the
#    board such that no queen is threatened.
#
# Technical Details: Since there can only be one queen per row, a
#   one dimensional array is used to represent the board. The
#   values inside the array represent the columns of the
#   chessboard. As such, each element of the array can take a
#   value between 0 and n-1.
#
#   The presented algorithm is based on the following personal
#   observation. A queen on cell (x,y) dominates all cells in
#   row x, in column y, or in any cell (j,k) where (j-k)==(x-y) or
#   (j+k)==(x+y).
#
#   Beginning with the first row (i.e. x=0), the addQueen function
#   is called recursively so as to dynamically adjust the board
#   until all n queens are placed safely.
#======================================================================= 
 def nQueenProblem( n ):
  queens = [0] * n
  addQueen( 0, queens, n )
  return queens;

def addQueen( x, queens, n ):
  i = 0
  while i < n and 0 == queens[n - 1]:
    if safeToAdd( x, i, queens ):
      queens[x] = i
      addQueen( x + 1, queens, n )
    i += 1

def safeToAdd( x, y, queens ):
  for i in range( x ):
    if y == queens[i] or ( x - y ) == ( i - queens[i] ) or ( x + y )
     == ( i + queens[i] ):
      return False
  return True

import unittest
from algorithms import numbers as algorithm

class Test( unittest.TestCase ):

  def testNQueenProblem( self ):
      n = 8
      expected = [0, 4, 7, 5, 2, 6, 1, 3]
      queens = algorithm.nQueenProblem( n )
      self.assertEquals( expected, queens )