Here is the implementation:
function solveNQueens(n):
result = []
board = n x n grid of '.'
cols = set(), diag1 = set(), diag2 = set()
backtrack(0)
return result
function backtrack(row):
if row == n:
result.append(board as string array)
return
for col from 0 to n - 1:
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
board[row][col] = 'Q'
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
backtrack(row + 1)
board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
Time is with pruning. Space is for sets and recursion.