#=======================================================================
# 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 )