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
Hey, I am having trouble printing the output. Could you please tell what the /a does? And could you maybe tell a little about the queen function as well?