We’re asked to determine, for an n x n chessboard, the number distinct solutions to the n-queens puzzle. Basically, the n-queens puzzle means there are n queens for an n x n chessboard and none can attack each other.
We sole this using backtracking, and we treat our solution like a graph as we traverse through ways we can place the queens. Starting with rows, we know we’ve succeeded if we reach row == n, essentially because we’re ruling out other combinations prior to getting to this point.
For columns, we iterate through each column and store the column that a queen we’ve selected is on. In future iterations of our traversal, we check to see if the column we want to use is already selected - if so, we skip it.
Finally diagonals - you’re not going to solve this problem unless you know this random trick. Diagonals are the same for an n x n graph when you take the difference of the row and column. A similar pattern occurs for anti-diagonals when you sum the row and column. So we just use our row and column we select to find out what diagonal / anti-diagonal the queen is on and place it into a set.
As we traverse through the graph, eventually we’ll find combinations of rows, columns, diagonals, and anti-diagonals that satisfy the n-queens puzzle. We increment our count and return it at the end.
The solution is as follows:
class Solution:
def totalNQueens(self, n: int) -> int:
self.ans = 0
def backtrack(row: int, cols: set, diags: set, antidiags: set) -> None:
if row == n:
self.ans += 1
return
for col in range(n):
diag = row - col
antidiag = row + col
if col in cols or diag in diags or antidiag in antidiags:
continue
cols.add(col)
diags.add(diag)
antidiags.add(antidiag)
backtrack(row + 1, cols, diags, antidiags)
cols.discard(col)
diags.discard(diag)
antidiags.discard(antidiag)
backtrack(0, set(), set(), set())
return self.ans_ Time Complexity:
O(n!) - n is the number of rows and columns.
_ Space Complexity:
O(n) - The recursion stack will have at most n frames.