Solve 8 queenss problem in Python
Fellow coders, in this tutorial we are going to learn about 8 queens problem and write a python program to solve it with the help of backtracking.
What is the 8 queens problem?
The 8 queens problem is a problem in swhich we figure out a way to put 8 queens on an 8×8 chessboard in such a way that no queen should attack the other. For basic info about the queen in a chess game, you should know that a queen can move in any direction ( vertically, horizontally, and diagonally) and to any number of places. In the figure below you can see how to place 4 queens on a 4×4 chessboard.
Similarly, we have to place 8 queens on an 8×8 chessboard. We will use backtracking to solve this interesting problem(puzzle).
What is Backtracking?
Backtracking the solution of the problem depends on the previous steps taken. We take a step and then analyze it that whether it will give the correct answer or not? and if not, then we move back and change the previous step.
How to solve 8 queens problem in Python
# Taking number of queens as input from user print ("Enter the number of queens") N = int(input()) # here we create a chessboard # NxN matrix with all elements set to 0 board = [[0]*N for _ in range(N)] def attack(i, j): #checking vertically and horizontally for k in range(0,N): if board[i][k]==1 or board[k][j]==1: return True #checking diagonally for k in range(0,N): for l in range(0,N): if (k+l==i+j) or (k-l==i-j): if board[k][l]==1: return True return False def N_queens(n): if n==0: return True for i in range(0,N): for j in range(0,N): if (not(attack(i,j))) and (board[i][j]!=1): board[i][j] = 1 if N_queens(n-1)==True: return True board[i][j] = 0 return False N_queens(N) for i in board: print (i)
Result:
Enter the number of queens 8
Output:
[1, 0, 0, 0, 0, 0, 0, 0] [0, 0, 0, 0, 1, 0, 0, 0] [0, 0, 0, 0, 0, 0, 0, 1] [0, 0, 0, 0, 0, 1, 0, 0] [0, 0, 1, 0, 0, 0, 0, 0] [0, 0, 0, 0, 0, 0, 1, 0] [0, 1, 0, 0, 0, 0, 0, 0] [0, 0, 0, 1, 0, 0, 0, 0]
Also read: Using Stacks to solve Desert Crossing Problem in Python
the code is very usegfull to me thannkyou sir
can i ask you whats this function is for
“def N_queens(n):
if n==0:
return True
for i in range(0,N):
for j in range(0,N):
if (not(attack(i,j))) and (board[i][j]!=1):
board[i][j] = 1
if N_queens(n-1)==True:
return True
board[i][j] = 0”