# N Queens Problemby 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 =  * 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 )
```