51. N-Queens
Category: /leetcodeLeetcode Link | Backtrack template
The n-queens puzzle is the problem of placing n queens on an n x 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 1:
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
Example 2:
Input: n = 1
Output: [["Q"]]
Solution:
- Backtrack, Time: O(N!), Space: O(N)
def solveNQueens(self, n: int) -> List[List[str]]:
def is_valid(row, col):
if cols[col] or diag_l[row + col] \
or diag_r[col - row + n - 1]:
return False
return True
def make_solution(grid):
res = []
for row in grid:
res.append("".join(row))
return res
def backtrack(row):
if row == n:
# print(f"found a result: {grid}")
result.append(make_solution(grid))
return
for col in range(len(grid[row])):
if is_valid(row, col):
# set new path
cols[col] = True
diag_l[row + col] = True
diag_r[col - row + n - 1] = True
grid[row][col] = "Q"
backtrack(row + 1)
# undo change
grid[row][col] = "."
cols[col] = False
diag_l[row + col] = False
diag_r[col - row + n - 1] = False
result = []
grid = [['.'] * n for _ in range(n)]
cols = [False] * n
m = n * 2 - 1
diag_l = [False] * m
diag_r = [False] * m
backtrack(0)
return result
