Python program to implement N Queens problem

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.”.

Leave a Comment