Implementation of N-queen Problem in Python

By Tanay R Dandekar

In this article, we are going to solve the N queen problem using the backtracking approach in python.

About N queen problem:

Given the value of N, our goal is to place the N number of queens in a NxN chessboard such that no two queens can attack each other or in other words, we have to place N number of queens such that no two queens can be in the same row, column or diagonally.

Solution:

This problem can be solved using the backtracking approach. We will start by placing queens one by one. While placing a queen, check whether it is safe which means it does not with another queen in a row, column, or diagonal way; if it is safe, we will mark this as our solution; otherwise, move to the next cell.

Code:

n=int(input("Enter no. of queens: "))
x=[0]*(n+1)

# checking whether the placement of queen is safe or not.
def feasible(k,j):
  for i in range(1,k):
    if ((x[i]==j) or (abs(j-x[i])==abs(k-i))):
      return False
  return True

def recur_nqueens(k,n):
  for x[k] in range(1,n+1):
    if feasible(k,x[k]):
      if k==n:
        res=x[1:]
        print(res)
      else:
        recur_nqueens(k+1,n)


print("Possible no. of ways queens placed in each row is:")
recur_nqueens(1,n)

Output:

Enter no. of queens: 4
Possible no. of ways queens placed in each row is:
[2, 4, 1, 3]
[3, 1, 4, 2]

In the output, it shows all possible solutions, i.e., all possible arrangements of queens in chessboard, and each solution is represented by a list as i-th element of the list represents the column number in which the queen is placed in i-th row.

Thank you