52. N-Queens II
和上一题基本没什么区别
class Solution(object):
def solveNQueens(self, n):
"""
:type n: int
:rtype: List[List[str]]
"""
board = [["." for _ in range(n)] for _ in range(n)]
self.count = 0
self.dfs(board, 0)
return self.count
def dfs(self, board, i): # put chess on ith row
if i == len(board):
# print board
self.count += 1
return
for j in range(len(board[0])):
# 对于所有列
if self.valid(board, i, j):
board[i][j] = 'Q'
self.dfs(board, i+1)
board[i][j] = '.'
def valid(self, board, i, j):
# valid row
if 'x' in board[i]:
return False
# valid col
for k in range(len(board)):
if board[k][j] == 'Q':
return False
# valid diag
for k in range(len(board)):
col = k + j - i
if 0 <= col < len(board) and board[k][col] == 'Q':
return False
# valid antidiag
for k in range(len(board)):
col = i + j - k
if 0 <= col < len(board) and board[k][col] == 'Q':
return False
return True
