N Queens problem implementation in Python

What is N Queens Problem?

The N Queens problem is:

How can N queens be placed on an NxN chessboard so that no two of them attack each other?

The eight queens puzzle is the problem of placing eight chess queens on an n x n chessboard so that no two queens threaten each other.

Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens problem of placing n non-attacking queens on an n×n chessboard, for which solutions exist for all natural numbers n with the exception of n=2 and n=3.

A possible solution for N Queens problem is:

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

Let us know in comments in case of any suggestions.

Also check: N Queens problem using backtracking in C