Coders Packet

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

Download project

Reviews Report

Submitted by Tanay R Dandekar (TanayRD1904)

Download packets of source code on Coders Packet