hello-algo/codes/python/chapter_backtracking/n_queens.py
Yudong Jin a005c6ebd3
Some improvements (#1073)
* Update avatar's link in the landing page

* Bug fixes

* Move assets folder from overrides to docs

* Reduce figures' corner radius

* Update copyright

* Update header image

* Krahets -> krahets

* Update the landing page
2024-02-07 22:21:18 +08:00

62 lines
1.9 KiB
Python
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

"""
File: n_queens.py
Created Time: 2023-04-26
Author: krahets (krahets@163.com)
"""
def backtrack(
row: int,
n: int,
state: list[list[str]],
res: list[list[list[str]]],
cols: list[bool],
diags1: list[bool],
diags2: list[bool],
):
"""回溯算法n 皇后"""
# 当放置完所有行时,记录解
if row == n:
res.append([list(row) for row in state])
return
# 遍历所有列
for col in range(n):
# 计算该格子对应的主对角线和次对角线
diag1 = row - col + n - 1
diag2 = row + col
# 剪枝:不允许该格子所在列、主对角线、次对角线上存在皇后
if not cols[col] and not diags1[diag1] and not diags2[diag2]:
# 尝试:将皇后放置在该格子
state[row][col] = "Q"
cols[col] = diags1[diag1] = diags2[diag2] = True
# 放置下一行
backtrack(row + 1, n, state, res, cols, diags1, diags2)
# 回退:将该格子恢复为空位
state[row][col] = "#"
cols[col] = diags1[diag1] = diags2[diag2] = False
def n_queens(n: int) -> list[list[list[str]]]:
"""求解 n 皇后"""
# 初始化 n*n 大小的棋盘,其中 'Q' 代表皇后,'#' 代表空位
state = [["#" for _ in range(n)] for _ in range(n)]
cols = [False] * n # 记录列是否有皇后
diags1 = [False] * (2 * n - 1) # 记录主对角线上是否有皇后
diags2 = [False] * (2 * n - 1) # 记录次对角线上是否有皇后
res = []
backtrack(0, n, state, res, cols, diags1, diags2)
return res
"""Driver Code"""
if __name__ == "__main__":
n = 4
res = n_queens(n)
print(f"输入棋盘长宽为 {n}")
print(f"皇后放置方案共有 {len(res)}")
for state in res:
print("--------------------")
for row in state:
print(row)