6 min read · May 30, 2023
One of the most classic and intriguing problems in computer science is the N-Queens problem. It hails from the world of chess, but instead of emphasizing strategic victories, it focuses on peaceful coexistence. Its real value is not just in chess, but as a classic problem in computer science that provides a gateway to understanding backtracking algorithms and recursive problem solving. Today, we will dive deep into the problem, comprehend its solution, and see it in action using Python.
The N-Queens problem challenges you to place N chess queens on an N×N chessboard so that no two queens threaten each other. That means no two queens can share the same row, column, or diagonal. The 8-Queens problem is the most popular variant, but the problem can be extended to any number of queens on a board of corresponding size.
A naive solution would be to place the queens one by one, from the first row to the last. However, without a strategic approach, this would involve a significant amount of backtracking since queens placed earlier could conflict with those placed later.
A more effective solution uses the concept of backtracking. Backtracking is a general algorithm for finding all (or some) solutions to computational problems, notably constraint satisfaction problems. It incrementally places queens on the board, checks for any conflict (if any queen threatens another), and then decides to keep or remove the queen based on the conflict result. If no placement is conflict-free, we go back (hence, “backtrack”) and change the previous queen’s position.
In backtracking, we start from the first row and proceed to the next only when we have found a valid position in the current row. If no valid position is found, we return false, signaling that the current configuration leads to no solution. We then go back to the previous row (backtrack), change the queen’s position, and start again.
Before we begin, we initialize a board with n rows and n columns. In our Python code, we represent the board as a 1D array, board = [0] * n, where the index represents the row number, and the value at that index represents the column number.
We start placing queens one by one, starting from the first row. If we find a valid place in the current row, we proceed to the next row. Otherwise, we return false, which is a signal to go back to the previous row and change the queen’s position.
The placement is done in the function place_queens(n, row), where n is the number of queens and row is the current row we're trying to place a queen in.
For each potential position, we check if it’s safe to place a queen there. The could_place(row, col) function does this by ensuring that no other queens exist in the same column, the two diagonals (the left-top to right-bottom diagonal and the right-top to left-bottom diagonal), or the row.
If we cannot find a valid position for a queen in the current row, we have to go back to the previous row (backtrack) and change the queen’s position. If we’ve exhausted all positions in the first row, it means we’ve found all valid placements.
Once we have a valid configuration (a valid position in every row), we append it to our results. This is done in place_queens(n, row) when row == n, indicating that we've successfully placed queens in all rows. We then convert the configuration from the form of column indices to the string representation for final output.
One important aspect is the recursive call to place_queens(n, row + 1). This attempts to place a queen in the next row after successfully placing one in the current row. If a valid position isn't found in the subsequent rows, this call will eventually return, and we will then try the next position in the current row.
This approach ensures that we explore all potential configurations. The algorithm is efficient and elegant, demonstrating the power of recursive backtracking.
Now, let’s transform this understanding into Python code.
def solveNQueens(n):
def could_place(row, col):
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 place_queens(n, row):
if row == n:
result.append(board[:])
return
for col in range(n):
if could_place(row, col):
board[row] = col
place_queens(n, row + 1)
board[row] = 0
result = []
board = [0] * n
place_queens(n, 0)
return [["." * i + "Q" + "." * (n - i - 1) for i in sol] for sol in result]
Let’s understand what’s happening here:
- could_place(row, col): This function checks if a queen can be placed in a given cell. It checks the current column, the two diagonals, and decides whether placing a queen here would cause a conflict.
- place_queens(n, row): This recursive function places a queen on the
rowand calls itself for the next row. It backtracks (removes the queen and tries the next column) if no place is found. - solveNQueens(n): This function initializes the process. We first initialize an empty chess board as a list of zeros. The index of the list represents the row number and the value at each index represents the column number. We then call
place_queens(n, 0)to start placing queens from the 0th row. In the end, we construct the final chessboard configurations from the results and return them.
When you run solveNQueens(n), it returns all the possible configurations for placing n queens on an n x n chessboard, ensuring no two queens share the same row, column, or diagonal.
The N-Queens problem’s complexity analysis involves a bit of nuance. Because we’re dealing with a combinatorial problem, it’s not entirely straightforward.
Time Complexity:
The time complexity of this problem is O(N!) in the worst-case scenario.
This may not be immediately obvious, but let’s break it down:
- On the first row, we have N choices to place a queen, and for each choice, we have N-1 choices on the next row, and for each of these, we have N-2 on the next, and so on. This gives us a time complexity of N * (N-1) * (N-2) * … * 1, which equals N!. This means that in the worst-case scenario, we will end up exploring N! permutations.
- However, this is a bit misleading because the algorithm has several mechanisms to stop going down a path as soon as a violation is detected, which prevents the exploration of all permutations. As a result, the effective time complexity is generally much less than O(N!).
Space Complexity:
The space complexity of the solution is O(N).
This is because we’re storing each solution in an array of size N (our ‘board’), where each value represents the column index where the queen is located in that particular row. This is done for all N queens. So, the space complexity is O(N).
It’s important to note that if you choose to store all of the solutions (all valid configurations), the space complexity could increase, depending on the number of valid solutions, but each solution would still be represented as a list of length N. In other words, the space requirement scales linearly with the problem size.
In conclusion, the N-Queens problem showcases the efficiency of the backtracking technique, and while it may have a high worst-case time complexity, it effectively handles the search space to find solutions to the problem.
The N-Queens problem is a classic problem showcasing the power of backtracking algorithms. By methodically placing each queen and backtracking whenever we detect a conflict, we can find all valid arrangements for the queens. Python’s simple syntax and powerful list comprehension capabilities make it a perfect language for implementing this elegant solution. I hope this deep dive empowers you to approach similar problems with newfound confidence and understanding!
