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.
solve 8 queens problem in Python

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

5 responses to “Solve 8 queenss problem in Python”

  1. reddyprasanna says:

    the code is very usegfull to me thannkyou sir

  2. Marsyavero Charisyah Putra says:

    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”

    • Muhammed Sinan says:

      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.

  3. summa says:

    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)

  4. Nani Kumar says:

    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..

Leave a Reply

Your email address will not be published. Required fields are marked *