Problem of The Day: N-Queens
Today, I continued my exploration of the Top 100 Liked List on LeetCode, where I encountered another challenging problem related to the Backtracking topic - the N-Queens. Unlike the previous Backtracking problems I’ve tackled, this one initially appeared quite daunting. However, with perseverance, I found that it’s not as difficult as it seems. Nevertheless, achieving an accepted submission on the LeetCode Judge System required meticulous logic tuning.
Honestly, despite making multiple attempts to solve this problem, I didn’t get it right on the first implementation. I had to invest a considerable amount of time fine-tuning my approach and exploring the tricks outlined in the Editorial tab, especially regarding the logic for checking diagonals and anti-diagonals. In this post, I’ll share insights into these intricacies, so stay tuned for a detailed explanation.
My Explanation and Approach
To tackle this problem, we leverage the fundamental principles of backtracking. Our goal is to explore various configurations of the chessboard, starting from the top-left cell [0, 0] or column = 0 and row = 0. As we place a queen at a particular cell, it triggers a set of restrictions. Specifically, the entire row, entire column, and both diagonals associated with this cell become off-limits for subsequent queen placements. Adhering to chess rules, placing queens on these restricted cells is prohibited, as they would be vulnerable to capture by previously positioned queens.
The logic for checking the entire row and entire column is relatively straightforward. Once a queen is situated at a specific cell, we must rule out the entire row and column linked to that cell for the next potential candidate.
In essence, our approach involves exhaustively traversing the problem space, marking forbidden regions with each queen placement. This systematic exploration allows us to identify valid solutions that satisfy the N-Queens problem constraints.
For example, if I have place the cell at [0][0], row = 0 and col = 0 are banned from picking. In addition, we ought to ban the diagonals as well.
| i | 0 | 1 | 2 |
|---|---|---|---|
| 0 | Q | x | x |
| 1 | x | x | . |
| 2 | x | . | x |
However, dealing with diagonals posed a challenge. Initially, my approach was to check four directions for each cell (North-East, North-West, South-East, South-West). While this logic was functional and managed to pass basic test cases, it felt convoluted.
Upon delving into discussions and consulting the Editorial section, I discovered a more elegant trick for diagonal checks. The key insight is that diagonals share the same values when applying a simple formula: row - col. Conversely, the anti-diagonal (or reverse diagonal) can be calculated as col - row.
To illustrate, consider the example of the chessboard below. Notably, the diagonal cells [0][1] and [1][2] share the same value, which is 1.
| i | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | -1 | 0 | 1 | 2 |
| 2 | -2 | -1 | 0 | 1 |
| 3 | -3 | -2 | -1 | 0 |
After understanding the intricacies of the diagonal and anti-diagonal checks, the next step involves invoking the backtrack function recursively. This recursive function is responsible for placing the next queen on the chessboard and verifying its validity as a candidate in order to build the final solution.
Backtracking Template
The insights I gained from LeetCode have been incredibly beneficial, especially when dealing with backtracking problems. I highly recommend memorizing and implementing the provided template for backtracking. This approach has proven to be a valuable resource, consistently aiding me in addressing various backtracking challenges. Having this template in your repertoire can be instrumental whenever you encounter similar problems in the future.
def backtrack(candidate):
if find_solution(candidate):
output(candidate)
return
# iterate all possible candidates.
for next_candidate in list_of_candidates:
if is_valid(next_candidate):
# try this partial candidate solution
place(next_candidate)
# given the candidate, explore further.
backtrack(next_candidate)
# backtrack
remove(next_candidate)
My Naive Solution
Below is my algorithm when I first attempted to solve this problem.
def print_table(state, n):
for row in range(n):
for col in range(n):
if [row, col] in state:
print('X', end=" ")
else:
print('*', end=" ")
print("")
def valid(row, col, state, n):
not_valid_cell = set()
for r, c in state:
rr, cc = r, c
while rr + 1 < n and cc + 1 < n:
rr += 1
cc += 1
not_valid_cell.add((rr, cc))
rr, cc = r, c
while rr - 1 >= 0 and cc - 1 >= 0:
rr -= 1
cc -= 1
not_valid_cell.add((rr, cc))
rr, cc = r, c
while rr - 1 >= 0 and cc + 1 < n:
rr -= 1
cc += 1
not_valid_cell.add((rr, cc))
rr, cc = r, c
while rr + 1 < n and cc - 1 >= 0:
rr += 1
cc -= 1
not_valid_cell.add((rr, cc))
for r, c in state:
for i in range(n):
not_valid_cell.add((r, i))
not_valid_cell.add((i, c))
if (row, col) in not_valid_cell:
return False
return True
def helper(n, result, row, state):
if row > n:
return
if n == len(state):
result[0] += 1
return
for col in range(n):
if valid(row, col, state, n):
state.append([row, col])
helper(n, result, row + 1, state)
state.pop()
def solve_n_queens(n):
result = [0]
helper(n, result, 0, [])
return result[0]
Brute Force Solution
Here is my brute-force solution from today’s attempt. In contrast to the convoluted code I initially wrote, I made an effort to streamline it. Despite hitting the time limit, I find this version more readable compared to my naive approach. I modularized the logic by creating distinct helper functions to facilitate implementation. Additionally, I employed auxiliary arrays to efficiently track the forbidden rows, columns, and diagonals. This optimization ensures that the algorithm doesn’t waste time repeatedly checking the validity of cells or states.
# time limit exceeded
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def check_row(c, cols):
return c not in cols
def check_col(r, rows):
return r not in rows
def check_diagonal(r, c, diagonal, rev_diagonal):
return (c - r) not in diagonal and (c + r) not in rev_diagonal
def is_valid(r, c, diagonal, rev_diagonal, cols, rows):
return check_row(c, cols) and check_col(r, rows) and check_diagonal(r, c, diagonal, rev_diagonal)
def backtrack(n, n_queens, board, result, diagonal, rev_diagonal, cols, rows):
if n_queens == 0:
candidate = ["".join(x) for x in board]
if candidate not in result:
result.append(["".join(x) for x in board])
return
for i in range(n):
for j in range(n):
if is_valid(i, j, diagonal, rev_diagonal, cols, rows):
board[i][j] = 'Q'
diagonal.append(j-i)
rev_diagonal.append(i+j)
rows.append(i)
cols.append(j)
backtrack(n, n_queens - 1, board, result, diagonal, rev_diagonal, cols, rows)
diagonal.pop()
rev_diagonal.pop()
rows.pop()
cols.pop()
board[i][j] = '.'
board = [['.'] * n for _ in range(n)] # create the board
result = []
backtrack(n, n, board, result, [], [], [], [])
return result
Attempt to optimize the Brute Force Solution
In an effort to enhance the efficiency of my brute-force solution, I sought optimization by replacing the auxiliary array or list with sets. The intention was to leverage the set() data structure, anticipating an improvement in time efficiency. However, this adjustment still resulted in the Time Limit Exceeded issue. This highlights the need for further refinement of my algorithm to achieve better performance.
# Still hitting the Time Limit Exceeded
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def check_row(c, cols):
return c not in cols
def check_col(r, rows):
return r not in rows
def check_diagonal(r, c, diagonal, rev_diagonal):
return (c - r) not in diagonal and (c + r) not in rev_diagonal
def is_valid(r, c, diagonal, rev_diagonal, cols, rows):
return check_row(c, cols) and check_col(r, rows) and check_diagonal(r, c, diagonal, rev_diagonal)
def backtrack(n, n_queens, board, result, diagonal, rev_diagonal, cols, rows):
if n_queens == 0:
candidate = tuple("".join(x) for x in board)
if candidate not in result:
result.add(candidate)
return
for i in range(n):
for j in range(n):
if is_valid(i, j, diagonal, rev_diagonal, cols, rows):
board[i][j] = 'Q'
diagonal.add(j - i)
rev_diagonal.add(i + j)
rows.add(i)
cols.add(j)
backtrack(n, n_queens - 1, board, result, diagonal, rev_diagonal, cols, rows)
diagonal.remove(j - i)
rev_diagonal.remove(i + j)
rows.remove(i)
cols.remove(j)
board[i][j] = '.'
board = [['.'] * n for _ in range(n)]
result = set()
backtrack(n, n, board, result, set(), set(), set(), set())
return [list(candidate) for candidate in result]
Optimized Solution
Based on my intuition, I recognized that I was generating the same potential candidate multiple times due to the nested for-loop. In fact, it became apparent that there was no need to iterate through the double for-loop as it would inevitably produce the same valid state of the chess board. Consequently, I refined my logic by opting to traverse through each column only, passing the row as a parameter for the subsequent backtrack function call. This adjustment significantly improved my time efficiency, eliminating the generation of duplicate states or candidates. Consequently, I could safely remove the check for the base case in the following code snippet.
if n_queens == 0:
candidate = tuple("".join(x) for x in board)
if candidate not in result: # no longer need this logic
result.add(candidate)
return
And here is my optimized solution.
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def check_row(c, cols):
return c not in cols
def check_col(r, rows):
return r not in rows
def check_diagonal(r, c, diagonal, rev_diagonal):
return (c - r) not in diagonal and (c + r) not in rev_diagonal
def is_valid(r, c, diagonal, rev_diagonal, cols, rows):
return check_row(c, cols) and check_col(r, rows) and check_diagonal(r, c, diagonal, rev_diagonal)
def backtrack(i, n, n_queens, board, result, diagonal, rev_diagonal, cols, rows):
if n_queens == 0:
candidate = tuple("".join(x) for x in board)
result.add(candidate)
return
for j in range(n):
if is_valid(i, j, diagonal, rev_diagonal, cols, rows):
board[i][j] = 'Q'
diagonal.add(j - i)
rev_diagonal.add(i + j)
rows.add(i)
cols.add(j)
backtrack(i + 1, n, n_queens - 1, board, result, diagonal, rev_diagonal, cols, rows)
diagonal.remove(j - i)
rev_diagonal.remove(i + j)
rows.remove(i)
cols.remove(j)
board[i][j] = '.'
board = [['.'] * n for _ in range(n)]
result = set()
backtrack(0, n, n, board, result, set(), set(), set(), set())
return [list(candidate) for candidate in result]
Leet Code Solution
class Solution:
def solveNQueens(self, n):
# Making use of a helper function to get the
# solutions in the correct output format
def create_board(state):
board = []
for row in state:
board.append("".join(row))
return board
def backtrack(row, diagonals, anti_diagonals, cols, state):
# Base case - N queens have been placed
if row == n:
ans.append(create_board(state))
return
for col in range(n):
curr_diagonal = row - col
curr_anti_diagonal = row + col
# If the queen is not placeable
if (col in cols
or curr_diagonal in diagonals
or curr_anti_diagonal in anti_diagonals):
continue
# "Add" the queen to the board
cols.add(col)
diagonals.add(curr_diagonal)
anti_diagonals.add(curr_anti_diagonal)
state[row][col] = "Q"
# Move on to the next row with the updated board state
backtrack(row + 1, diagonals, anti_diagonals, cols, state)
# "Remove" the queen from the board since we have already
# explored all valid paths using the above function call
cols.remove(col)
diagonals.remove(curr_diagonal)
anti_diagonals.remove(curr_anti_diagonal)
state[row][col] = "."
ans = []
empty_board = [["."] * n for _ in range(n)]
backtrack(0, set(), set(), set(), empty_board)
return ans
For Future Me
In the midst of every challenge and hardship you face today, remember that each struggle is a stepping stone toward your future achievements. Stay calm and composed in the face of adversity, for these moments of difficulty are molding you into the resilient and successful person you are destined to become. Keep pushing forward, and know that your perseverance will lead to triumph.
