This function solves the N Queen problem using backtracking

n-queen-problem.py

# This function solves the N Queen problem using 
# Backtracking. It mainly uses solveNQUtil() to 
# solve the problem. It returns false if queens 
# cannot be placed, otherwise return true and 
# placement of queens in the form of 1s. 
# note that there may be more than one 
# solutions, this function prints one of the 
# feasible solutions. 
def solveNQ(): 
  board = [ [0, 0, 0, 0], 
            [0, 0, 0, 0], 
            [0, 0, 0, 0], 
            [0, 0, 0, 0] ] 
  # row = 0;col=0
  # b = [row[:] for row in board]
  # placeQueen(b,row,col,0)
  # print(board)
  row = 0; 
  while row < 4:
    col = 0;
    while col < 4:
      b = [row[:] for row in board]
      if placeQueen(b,row,col,0, 4)==4:
        print("*****",b)
        # return
      # print("----",b)
      
      col = col + 1
    row = row + 1

def nextCell(row,col):
  if col+1 > 3:
    col = 0; row += 1
  else:
    col += 1
  return row,col

# This returns number of queens placed
def placeQueen(board,row,col,count,N):
  if row >3 or col >3: return count
  if count == N:return count

  # print(row,col,count,board)
  if isSafe(board,row,col):
    board[row][col] = 1
    count += 1

  # find the next cell
  row,col = nextCell(row,col)
  return placeQueen(board,row,col,count,N)
  
def isSafeHorizontal(board, y, x):
  X = x
  while X < 4: #forward
    if board[y][X] != 0 : 
      return False
    X = X+1
  X = x
  while X >= 0: #backward
    if board[y][X] != 0 :
      return False
    X=X-1
  return True

def isSafeVertical(board, y, x):
  Y = y
  while Y < 4: #forward
    if board[Y][x] != 0 : 
      return False
    Y = Y+1
  Y = y
  while Y >= 0: #backward
    if board[Y][x] != 0 :
      return False
    Y=Y-1
  return True

def isSafeDiagFwd(board, y, x): # / diagonal
  X = x
  Y = y
  while (X < 4) and (Y >= 0): #top right direction
    if board[Y][X] != 0 : 
      return False
    Y = Y-1
    X = X+1

  X = x
  Y = y
  while X >= 0 and Y < 4: #bottom left direction
    if board[Y][X] != 0 : 
      return False
    Y=Y+1
    X=X-1

  return True

def isSafeDiagBwd(board, y, x): # \ diagonal
  X = x
  Y = y
  while (X >= 0) and (Y >= 0): #top left direction
    if board[Y][X] != 0 : 
      return False
    Y = Y-1
    X = X-1

  X = x
  Y = y

  while X < 4 and Y < 4: #bottom right direction
    if board[Y][X] != 0 : 
      return False
    Y=Y+1
    X=X+1
    
  return True

# for a given index, checks if it can place a queen
def isSafe(board, y, x):
  a = isSafeHorizontal(board,y,x)
  b = isSafeVertical(board,y,x)
  c = isSafeDiagFwd(board,y,x)
  d = isSafeDiagBwd(board,y,x)

  return a and b and c and d

def test1():
  board = [ [1, 0, 0, 0], 
          [0, 0, 0, 0], 
          [0, 0, 0, 0], 
          [0, 0, 0, 0] ] 
  print(isSafeHorizontal(board,0,1))

def main():
  # test1()
  solveNQ()


if __name__ == "__main__":
  main()