Solution of N-Queens Problem in Python

In this tutorial, we will learn the solution for the N-queen problem in Python.

Firstly we will learn what is N-Queen problem.
N-queens is the problem of arranging the N-Queens on an N*N chessboard in such a way that no two queens are arranged in the same row, the same column, or diagonal.

For example, take the 4-queen problem

The solution is [3,1,2,4].
The first queen should be placed in the 1st row 3rd column, the second queen should be placed in 2nd row 1st column, the third queen should be placed in 3rd row 2nd column and finally, the 4rth queen should be placed in 4rth row 4rth column.

point to remember.

• The input for the N-Queens problem is a positive integer{N∈N}, but the 2-Queen and the 3-Queen problem is not possible.

 

N-Queens problem in Python

import numpy as cp
from itertools import permutations
def queen(a):
for cl in permutations(range(a)):
mtrx = np.zeros(a*a).reshape(a,a)        
check =0 
  for i in range(a):
  if check != i*(i-1)/2:
     break
  for j in range(1,a):
   if i >= j:
   if cl[i] == cl[i-j]+j or cl[i] == cl[i-j]-j:
  check = 0
  break
     else:
  check += 1
    else:
   continue
    if check == a*(a-1)/2:
  for r in range(a):
     mtrx[r][cl[r]] = 1
 yield mtrx
  else:
   pass
num = int(input())
print(f"Input: {num}\a") print("solution:\a")
for m in queens(num): 
 print(m,"\a")

Input : 4 

solution : [[0.1.0.0] [0.0.0.1] [1.0.0.0] [0.0.1.0]] [[0.0.1.0] [1.0.0.0] [0.0.0.1] [0.1.0.0]]

In the above program, we solved the 4-Queens problem.
It checks all the possibilities and gives possible solutions for the 4-queens problem.
In the output 1 represents where the queen is to be placed. we will get only two solutions for the 4-queens problem . one is 2,4,1,3 and the other is 3, 1,4,2.these are the places 0f q1,q2,q3, and q4 respectively.

Finally, there are various approaches to solve the N-Queen problem, They are brute force, backtracking, and graph theory solution.

Also read: Python compile() function with examples