In this article, we are going to solve the N queen problem using the backtracking approach in python.
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.
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.
n=int(input("Enter no. of queens: ")) x=*(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)
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.
Submitted by Tanay R Dandekar (TanayRD1904)
Download packets of source code on Coders Packet