1.
Introduction
2.
Python Program for N Queen Problem | Backtracking-3
2.1.
Python
3.
Implementation
3.1.
Starting Point
3.2.
Placing the First Queen
3.3.
Moving On
3.4.
Backtracking Magic
3.5.
Solution Found
4.
Time Complexity
5.
5.1.
Can the N Queens problem be solved for any size of the chessboard?
5.2.
Why do we use backtracking for the N Queens problem?
5.3.
Is there only one solution to the N Queens problem?
6.
Conclusion
Last Updated: Mar 30, 2024
Easy

N Queens Problem in Python

Rahul Singh
0 upvote

Introduction

The N Queens problem is a classic example of a puzzle that has fascinated both computer scientists and students for years. It's all about placing N queens on an NĂ—N chessboard in such a way that no two queens threaten each other. This means no two queens can share the same row, column, or diagonal. The beauty of this problem lies in its simplicity & the complexity of its solutions.

In this article, we're looking into the Python solution for the N Queens problem, exploring how backtrackingâ€”a fundamental concept in computer scienceâ€”plays a crucial role.

Python Program for N Queen Problem | Backtracking-3

Now, we're going to tackle the N Queens problem using Python, focusing on a method called backtracking. Think of backtracking as a way to make decisions, step by step, and if you hit a dead end, you just step back and try a different path. It's like navigating a maze where you choose a route, and if you face a wall, you backtrack to the last decision point and take a different turn.

Here's a simple Python program that solves the N Queen problem using backtracking. The program defines a board using a 2D list, where zeros represent empty spaces and ones represent queens. The solution involves placing a queen on the board and then checking for conflicts. If a conflict is found, the queen is removed, and a new position is tried.

• Python

Python

``def isSafe(board, row, col, n):    # Check this row on left side    for i in range(col):        if board[row][i] == 1:            return False    # Check upper diagonal on left side    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):        if board[i][j] == 1:            return False    # Check lower diagonal on left side    for i, j in zip(range(row, n, 1), range(col, -1, -1)):        if board[i][j] == 1:            return False    return Truedef solveNQUtil(board, col, n):    # base case: If all queens are placed    if col >= n:        return True    # Consider this column and try placing this queen in all rows one by one    for i in range(n):        if isSafe(board, i, col, n):            # Place this queen in board[i][col]            board[i][col] = 1            # recur to place rest of the queens            if solveNQUtil(board, col + 1, n) == True:                return True            # If placing queen in board[i][col] doesn't lead to a solution, then remove queen from board[i][col]            board[i][col] = 0  # BACKTRACK    # If the queen cannot be placed in any row in this column, return False    return Falsedef solveNQ(n):    board = [[0] * n for _ in range(n)]    if solveNQUtil(board, 0, n) == False:        print("Solution does not exist")        return False    # A utility function to print solution    for i in board:        print(i)    return True# Driver Coden = 4solveNQ(n)``

Output

``````[0, 0, 1, 0]
[1, 0, 0, 0]
[0, 0, 0, 1]
[0, 1, 0, 0]``````

In this code:

• isSafe() checks if a queen can be placed on the board without any conflicts.

• solveNQUtil() is where backtracking happens, trying to place queens column by column.

• solveNQ() sets up the board and starts the process by calling solveNQUtil().

• Run this code with n = 4 (or any number you like), and it will print a solution to the N Queens problem, with 1s representing the queens.

• Remember, this is just one of the many solutions, and backtracking ensures we find one that works.

Implementation

Starting Point

The program kicks off by creating a chessboard. It's a square grid (like 4x4, 8x8, depending on n) filled with zeros. These zeros mean the spots are empty.

Placing the First Queen

It tries to place the first queen in the first row and column. If this spot is safe (no conflicts with other queens), the queen is placed (we mark it as 1).

Moving On

Once the first queen is placed, the program moves to the next column. It tries to place another queen in a safe spot. If it finds a safe spot, the queen is placed. If not, it moves the queen in the previous column to a new spot and tries again.

Backtracking Magic

Here's where backtracking shines. If there's a point where the queen can't be placed in any row of a column, the program goes back (backtracks) to the previous column and moves the queen there to a different row. This step is repeated until all queens are placed safely.

Solution Found

When all queens are placed such that none of them can attack each other, the program prints the board with the queens' positions.

This methodical approach allows the program to explore all possible board configurations until it finds a solution. It's like solving a puzzle piece by piece, where you might have to backtrack and rearrange some pieces to get everything to fit.

Time Complexity

When we talk about time complexity, we're looking at how long a program takes to run as the size of its input changes. For the N Queens problem, understanding time complexity is important because it helps set expectations on how quickly a solution can be found.

The time complexity of the backtracking solution for the N Queens problem is O(N!), where N is the number of queens (or the size of the chessboard). Now, O(N!) might sound scary because factorial growth is really fast. This means that as the number of queens increases, the time it takes to find a solution increases super quickly.

Here's a simpler way to think about it: For the first queen, there are N possible rows to choose from. For the second queen, there are, at most, N-1 positions, because one row is already taken by the first queen, and so on. So, the total number of operations needed in the worst case is N * (N-1) * (N-2) * ... * 1, which is N!.

The beauty of backtracking is that it doesn't blindly try every single possibility. It "backtracks" as soon as it realizes a current path won't lead to a solution. This cuts down a lot of unnecessary work, making the algorithm more efficient than it might first appear.

In practice, this means that for smaller numbers of N, like 4 or 8 (which are common sizes for chessboards), the program can find a solution pretty quickly. But as N grows, the time taken grows very fast, making it impractical for very large N.

Can the N Queens problem be solved for any size of the chessboard?

Yes, the N Queens problem can be theoretically solved for any N, but the time it takes to find a solution increases sharply with larger N due to the O(N!) time complexity.

Why do we use backtracking for the N Queens problem?

Backtracking is ideal for the N Queens problem because it allows us to explore potential solutions systematically and backtrack as soon as we detect a conflict, making the process more efficient.

Is there only one solution to the N Queens problem?

No, there are usually multiple solutions to the N Queens problem, especially as N increases. The backtracking algorithm finds one valid solution, but by tweaking the algorithm, you can explore other possible solutions.

Conclusion

In this article, we looked into the exciting N Queens problem, a classic puzzle that challenges us to think creatively & systematically. We started with a basic understanding of the problem & then created a Python program that uses backtracking to find a solution. We understood each step of the process, and discussed the time complexity also.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Live masterclass