# Untitled

unknown
plain_text
7 months ago
1.7 kB
9
Indexable
Never
```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
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```