回溯法是一种搜索算法,常用于解决组合优化问题和枚举问题等。以下是关于回溯法的详细介绍:
def isLineAvailable(arr, i, j, idx, idy):
x, y = i, j
avail = True
while 0 <= x < len(arr[i]) and 0 <= y < len(arr[i]):
if x != i and y != j and arr[x][y] == "Q":
avail = False
x += idx
y += idy
return avail
def isNodeAvailable(arr, i, j):
available = True
for (idx, item) in enumerate(arr[i]):
if item == "Q" and idx != j:
available = False
for idx in range(len(arr[i])):
if idx != i and arr[idx][j] == "Q":
available = False
for idx, idy in [(-1, -1), (1, 1), (-1, 1), (1, -1)]:
if not isLineAvailable(arr, i, j, idx, idy):
available = False
break
return available
def doRecord(arr):
res = []
for line in arr:
res.append("".join(line))
return res
def placeQ(arr, i, result):
if i == len(arr):
result.append(doRecord(arr))
return
for j in range(len(arr)):
if isNodeAvailable(arr, i, j):
arr[i][j] = "Q"
placeQ(arr, i + 1, result)
arr[i][j] = "."
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
arr = [["." for i in range(n)] for j in range(n)]
result = []
placeQ(arr, 0, result)
return result