class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
solutions = []
def isplaceok(board, N, col):
for i in range(N): # for each queen already placed
if (board[i] == col) or (board[i] - i == col - N) or (board[i] + i == col + N):
return False # place can be attacked
return True # no attacks; place is ok
def printsolution(board):
solutions.append(board[:]) #shallow copy
for i in range(n):
for j in range(n):
print("X" if board[i] == j else "-", end="")
print("")
print("\n")
def addqueen(board, N):
if N >= n: # all queens have been placed
printsolution(board)
else: # try place the Nth queen
for col in range(n):
if isplaceok(board, N, col):
print(board)
board[N] = col # place nth queen at column c
addqueen(board, N+1)
addqueen([-1]*n, 0)
print(solutions)
return [
["." * c + "Q" + "." * (n - c - 1) for c in sol]
for sol in solutions
]
ported from the Programming in Lua