var solveNQueens = function(n) {
if (n === 0) {
return []
}
let res = []
let board = []
for (let i = 0; i < n; i++) {
let tmp = []
for (let j = 0; j < n; j++) {
tmp.push(".")
}
board.push(tmp)
}
const valid = function(board, row, col) {
for (let i = 0; i < n; i++) {
if (board[i][col] === "Q") {
return false
}
}
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] === "Q") {
return false
}
}
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] === "Q") {
return false
}
}
return true
}
const backtrack = function(board, row) {
if (row === n) {
tmp = []
for (const item of board) {
tmp.push(item.join(""))
}
res.push(tmp)
return
}
for (let col = 0; col < n; col++) {
if (!valid(board, row, col)) {
continue
}
board[row][col] = "Q"
backtrack(board, row + 1)
board[row][col] = "."
}
}
backtrack(board, 0)
return res
};
Runtime: 68 ms, faster than 79.26% of JavaScript online submissions for N-Queens.
Memory Usage: 37.1 MB, less than 100.00% of JavaScript online submissions for N-Queens.
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
ans = []
queens = [-1]*n
columns = [True]*n+[False]
back = [True]*n*2
forward = [True]*n*2
row = col = 0
while True:
if columns[col] and back[col-row+n] and forward[col+row]:
queens[row] = col
columns[col] = back[col-row+n] = forward[col+row] = False
row += 1
col = 0
if row == n:
ans.append(['.'*q+'Q'+'.'*(n-q-1) for q in queens])
else:
if row == n or col == n:
if row == 0:
return ans
row -= 1
col = queens[row]
columns[col] = back[col-row+n] = forward[col+row] = True
col += 1
Runtime: 48 ms, faster than 98.01% of Python3 online submissions for N-Queens.
Memory Usage: 13.1 MB, less than 100.00% of Python3 online submissions for N-Queens.
n皇后2
class Solution:
def totalNQueens(self, n: int) -> int:
diag1 = set()
diag2 = set()
usedCols = set()
return self.helper(n, diag1, diag2, usedCols, 0)
def helper(self, n, diag1, diag2, usedCols, row):
if row == n:
return 1
solutions = 0
for col in range(n):
if row + col in diag1 or row - col in diag2 or col in usedCols:
continue
diag1.add(row + col)
diag2.add(row - col)
usedCols.add(col)
solutions += self.helper(n, diag1, diag2, usedCols, row + 1)
diag1.remove(row + col)
diag2.remove(row - col)
usedCols.remove(col)
return solutions
Runtime: 48 ms, faster than 87.61% of Python3 online submissions for N-Queens II.
Memory Usage: 12.7 MB, less than 100.00% of Python3 online submissions for N-Queens II.
