N-Queens problem Technical Interview Question by FAANG
Dennis Maina
Dennis Maina

Published on 15th June, 2023 (3 months ago)

N-Queens problem Technical Interview Question by FAANG

(1 minute read)

You have an N by N board. Write a function that, given N, returns the number of possible arrangements of the board where N queens can be placed on the board without threatening each other, i.e. no two queens share the same row, column, or diagonal.


This is a popular question that is solved with backtracking. The following is a solution done in Python

def solve_n_queens(n):
    def is_safe(board, row, col):
        # Check if a queen can be placed at the given position without conflicting
        # with any other queens on the board
        for i in range(row):
            if board[i] == col or \
               board[i] - i == col - row or \
               board[i] + i == col + row:
                return False
        return True

    def backtrack(board, row):
        # Base case: all queens have been placed successfully
        if row == n:
            return 1

        count = 0
        for col in range(n):
            if is_safe(board, row, col):
                board[row] = col
                count += backtrack(board, row + 1)
                board[row] = -1

        return count

    # Initialize the board with empty cells
    board = [-1] * n
    return backtrack(board, 0)

n = 4
count = solve_n_queens(n)
print(f"Number of possible arrangements for {n}-queens: {count}")

Comments (0)

Dennis Maina

Dennis Maina


CEO and Founder of DentriceDev Solutions.



July '22

Joined date

Domain Name Registration & Hosting
Domain Name Registration & Hosting

HostPinnacle Kenya is the best and cheapest web hosting company in Kenya with world-class web hosting packages and affordable web design offers. Apart from that we offer free life-time SSL certificate, affordable domain registration in Kenya and free whois privacy. We have an award-winning support team available 24/7/365 to help you with your queries.

Do you want to write with us? Register and start blogging.

Register Login

Thank you for your support!

We deliver the best web products