Problem
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
image
Given an integer n, return all distinct solutions to the n-queens puzzle.
Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.
Example:
Input: 4
Output: [
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.
問題
n 皇后問題研究的是如何將 n 個皇后放置在 n×n 的棋盤上辐董，并且使皇后彼此之間不能相互攻擊。
image
上圖為 8 皇后問題的一種解法。
給定一個整數(shù) n，返回所有不同的 n 皇后問題的解決方案。
每一種解法包含一個明確的 n 皇后問題的棋子放置方案窒所，該方案中 'Q' 和 '.' 分別代表了皇后和空位。
示例：
輸入：4
輸出：[
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."],
["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解釋: 4 皇后問題存在兩個不同的解法。
提示：
- 皇后彼此不能相互攻擊寂祥，也就是說：任何兩個皇后都不能處于同一條橫行、縱行或斜線上七兜。
思路
回溯
回溯模板：
res = []
def backtrack(路徑, 選擇列表):
if 滿足結(jié)束條件:
result.add(路徑)
return
for 選擇 in 選擇列表:
做選擇
backtrack(路徑, 選擇列表)
撤銷選擇
Python3 代碼
from typing import List
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
# 一維列表
board = ['.' * n for _ in range(n)]
def isValid(board, row, col):
"""
檢查是否有皇后互相沖突
"""
# 檢查第 row 行 第 col 列是否可以放皇后
# 只需考慮 <= row丸凭，因為后面的棋盤是空的
for row_index in range(row):
# 判斷當(dāng)前行是否放了皇后
if row_index == row:
if 'Q' in board[row_index]:
return False
# 判斷遍歷每行時，第 col 列是否已經(jīng)放了皇后
if 'Q' == board[row_index][col]:
return False
# 判斷左上方是否放了皇后
tmp_row, tmp_col = row, col
while tmp_row > 0 and tmp_col > 0:
tmp_row -= 1
tmp_col -= 1
if 'Q' in board[tmp_row][tmp_col]:
return False
# 判斷右上方是否放了皇后
tmp_row, tmp_col = row, col
while tmp_row > 0 and tmp_col < n - 1:
tmp_row -= 1
tmp_col += 1
if 'Q' in board[tmp_row][tmp_col]:
return False
return True
def replace_char(string, char, index):
"""
構(gòu)建新的字符串進(jìn)行賦值
"""
string = list(string)
string[index] = char
return ''.join(string)
def backtrack(board, row):
# 1.結(jié)束條件
if row == len(board):
# 需要用 list 轉(zhuǎn)化一下
res.append(list(board[:]))
return
# 2.剪枝
# m = len(board[row])
for col in range(n):
# 剪枝
if not isValid(board, row, col):
continue
# 3.回溯并更新 row
board[row] = replace_char(board[row], 'Q', col)
backtrack(board, row + 1)
board[row] = replace_char(board[row], '.', col)
backtrack(board, 0)
return res
if __name__ == "__main__":
n = 4
print(Solution().solveNQueens(n))
