Python program to implement N Queens problem:
def isSafe(board, row, col, n): # check if there is a queen in the same row for i in range(col): if board[row][i] == 1: return False # check if there is a queen in the upper diagonal on the left side for i, j in zip(range(row, -1, -1), range(col, -1, -1)): if board[i][j] == 1: return False # check if there is a queen in the lower diagonal on the left side for i, j in zip(range(row, n), range(col, -1, -1)): if board[i][j] == 1: return False return True def solveNQueenUtil(board, col, n): # base case: all queens are placed if col == n: return True # try placing a queen in each row in the current column for i in range(n): if isSafe(board, i, col, n): board[i][col] = 1 # recursively place the rest of the queens if solveNQueenUtil(board, col + 1, n): return True # backtrack and remove the queen from the current position board[i][col] = 0 # no safe placement found in this column return False def solveNQueen(n): # create a n x n chess board board = [[0 for x in range(n)] for y in range(n)] if solveNQueenUtil(board, 0, n) == False: print("No solution exists.") return False # print the solution for i in range(n): for j in range(n): print(board[i][j], end=' ') print() return True
To solve the n-queen problem, you can call the solveNQueen
function with the desired value of n. For example, to solve the problem for n=4, you can call solveNQueen(4)
. The program will print the solution if one exists, otherwise it will print “No solution exists.”.