如果讀者對于回溯算法思路解法還不是很了解，可以先點擊鏈接查閱我之前的一篇博文《算法之【回溯算法】詳解》底哗，很詳細的介紹了回溯算法求解思路及方法季二，有利于你更好的學(xué)習(xí)回溯算法讶请。
題目描述
n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上蘸吓，并且使皇后彼此之間不能相互攻擊。 給定一個整數(shù) n笛园，返回所有不同的 n 皇后問題的解決方案涂邀。每一種解法包含一個明確的 n 皇后問題的棋子放置方案瘟仿，該方案中 'Q' 和 '.' 分別代表了皇后和空位。
注：下圖為 8 皇后問題的一種解法比勉。
皇后彼此不能相互攻擊劳较，也就是說：任何兩個皇后都不能處于同一條橫行驹止、縱行或斜線上。
示例1
輸入：4 輸出：
解法 1： [".Q..", "...Q", "Q...", "..Q."],解法 2：["..Q.", "Q...", "...Q", ".Q.."]
解釋: 4 皇后問題存在兩個不同的解法观蜗。
問題分析
直接套用《算法之【回溯算法】詳解》中的回溯算法基本步驟以及回溯算法的通用框架模板臊恋。
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def backtrack(board, row):
if row >= n:
# 此處是將每一行轉(zhuǎn)換為題目要求的字符串形式,如"..Q."代表一行
cur_res = [''.join(row) for row in board]
res.append(cur_res) #保存結(jié)果
return
for i in range(n):
if isValid(row, i, board): #isValid用于判斷該位置是否合法，能夠放置皇后
board[row][i] = 'Q' #放置皇后
backtrack(board, row+1) # row+1進入下一行
board[row][i] = '.' #回溯
res = []
board = [['.'] * n for _ in range(n)] # 初始化棋盤
backtrack(board, 0) # row從0開始
return res
1. 狀態(tài)變量為行：row,每次在當前行選擇完一個可以放置的皇后位置后進入下一行row+1;
2. 遞歸結(jié)束條件:當row>=n時墓捻，row從0開始抖仅，表示前n-1所有行的皇后均已放置完成，將結(jié)果添加到res中砖第。
if row >= n:
# 此處是將每一行轉(zhuǎn)換為題目要求的字符串形式,如"..Q."代表一行
cur_res = [''.join(row) for row in board]
res.append(cur_res)
return
3. 可選擇的列表：每一行能夠選擇的位置為0到n-1撤卢，但是該位置是否能夠被選擇，需要滿足皇后彼此不能相互攻擊的條件厂画。
此處判斷是否能夠相互攻擊即判斷當前位置(row, col)所在的列凸丸，右斜線方向即左斜線方向是否已經(jīng)有皇后存在拷邢，如果有的話袱院，則當前位置不能再放皇后。
判斷是否有沖突的方式有兩種：
方法一：直接通過循環(huán)判斷
def isVaild(board,row, col):
#判斷同一列是否沖突
for i in range(len(board)):
if board[i][col] == 'Q':
return False
# 判斷左上角是否沖突
i = row -1
j = col -1
while i>=0 and j>=0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# 判斷右斜線方向是否沖突
i = row - 1
j = col + 1
while i>=0 and j < len(board):
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
方法二: 左斜線:同一斜線每個點row-col恒定; 右斜線：同一斜線每個點row+col恒定
左斜線為從左上到右下方向瞭稼，同一條斜線上的每個位置滿足行下標與列下標之差相等忽洛，例如 (0,0)和 (3,3)在同一條方向一的斜線上。因此使用行下標與列下標之差即可明確表示每一條方向一的斜線环肘。
右斜線為從右上到左下方向欲虚，同一條斜線上的每個位置滿足行下標與列下標之和相等，例如 (3,0)(3,0) 和 (1,2)(1,2) 在同一條方向二的斜線上悔雹。因此使用行下標與列下標之和即可明確表示每一條方向二的斜線复哆。
下面我們主要使用第二種方法來進行判斷所放置的位置是否合法。
def isValid(row, col):
# 判斷所放置的位置是否合法
for i in range(row):
for j in range(n):
# 注：左斜對角線上腌零，同一條斜線上的每個位置滿足行下標與列下標之差相等
# 注：右斜對角線上梯找，同一條斜線上的每個位置滿足行下標與列下標之和相等
if board[i][j] == 'Q' and (j == col or i + j == row + col or i-j == row-col):
return False
return True
最終代碼
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def isValid(row, col):
# 判斷所放置的位置是否合法
for i in range(row):
for j in range(n):
if board[i][j] == 'Q' and (j == col or i + j == row + col or i-j == row-col):
return False
return True
def backtrack(board, row):
if row >= n:
cur_res = [''.join(row) for row in board]
res.append(cur_res)
return
for i in range(n):
if isValid(row, i, board):
board[row][i] = 'Q'
backtrack(board, row+1)
board[row][i] = '.'
res = []
board = [['.'] * n for _ in range(n)]
backtrack(board,0)
return res
代碼優(yōu)化：通過集合記錄之前放置過元素的正向?qū)蔷€，負向?qū)蔷€益涧，及列锈锤，判斷當前點是否在集合中，在的話說明不滿足要求闲询，這種判斷方式速度更快久免。
def solveNQueens(self, n: int) -> List[List[str]]:
def isValid(row, col):
# 如果該點所對應(yīng)的右斜線或左斜線或列已經(jīng)放置了皇后則放回Fasle
if col in col_hash or (row + col) in pie_hash or (row-col) in na_hash:
return False
return True
def backtrack(board, row):
if row >= n:
cur_res = [''.join(row) for row in board]
res.append(cur_res)
return
for col in range(n):
if isValid(row, col, board):
board[row][col] = 'Q'
pie_hash.add(row + col)
na_hash.add(row - col)
col_hash.add(col)
backtrack(board, row+1)
board[row][col] = '.'
pie_hash.remove(row + col)
na_hash.remove(row-col)
col_hash.remove(col)
res = []
board = [['.'] * n for _ in range(n)]
pie_hash = set() # 記錄放置了皇后的右斜線
na_hash = set() # 記錄放置了皇后的左斜線
col_hash = set() # 記錄放置了皇后的列
backtrack(board,0)
return res
后續(xù)會繼續(xù)更新關(guān)于回溯算法的相關(guān)題解，歡迎持續(xù)關(guān)注扭弧！
如果喜歡作者阎姥，歡迎點贊、收藏及關(guān)注鸽捻，謝謝呼巴！
