# LeetCode 51. N-Queens

## Description

https://leetcode.com/problems/n-queens/

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where `'Q'` and `'.'` both indicate a queen and an empty space respectively.

Example:

```Input: 4
Output: [
[".Q..",  // Solution 1
"...Q",
"Q...",
"..Q."],

["..Q.",  // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
```

## Explanation

start from each column do backtracking

## Python Solution

``````class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
results = []

board_assignment = {
'rows': {},
'columns': {},
'sum': {},
'diff': {}
}

board = [["." for j in range(0, n)] for i in range(0, n)]
self.helper(n, 0, board, board_assignment, results)

return results

def output_result_format(self, board):
result = []

for i in range(0, len(board)):
row = ""
for j in range(0, len(board)):
row += board[i][j]
result.append(row)

return result

def helper(self, n, column_index, board, board_assignment, results):
if column_index == n:
results.append(self.output_result_format(board))

return

for i in range(0, n):
if not self.is_valid_assignment(i, column_index, board_assignment):
continue

board[i][column_index] = "Q"

board_assignment['rows'][i] = True
board_assignment['columns'][column_index] = True
board_assignment['diff'][(i - column_index)] = True
board_assignment['sum'][(i + column_index)] = True

self.helper(n, column_index + 1, board, board_assignment, results)

board[i][column_index] = "."
del board_assignment['rows'][i]
del board_assignment['columns'][column_index]
del board_assignment['diff'][(i - column_index)]
del board_assignment['sum'][(i + column_index)]

def is_valid_assignment(self, row_index, column_index, board_assignment):
if row_index in board_assignment['rows']:
return False

if column_index in board_assignment['columns']:
return False

if (row_index - column_index) in board_assignment['diff']:
return False

if (row_index + column_index) in board_assignment['sum']:
return False

return True

``````
• Time complexity: O(N!).
• Space complexity: O(N!).