Solve 8 queenss problem in Python
By Shubham Kumar SinghFellow 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”
The ‘N_queens’ function is the recursive function that solves the problem by placing queens on the board, one by one. It first checks if all the queens are placed and return True if yes, otherwise it loops through each position on the board, checks if it is under attack, and if not, place a queen on that position, then calls itself with n-1. If this call returns False, which means it is not possible to place n-1 queens on the remaining board, it unplaces the queen and backtracks to try the next position.
The final version of the board will be printed out in the last for loop.
vanakkam da mapla
# 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)
In line 9 , def attack(i,j): the value for parameters i,j are not assigned and also in entire code.please explain about that..