< Back




52. N-Queens II

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.