在
n
×
n
n \times n
n×n格的棋盘上放置彼此不受攻击的
n
n
n个皇后,按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子
n
n
n皇后问题等价于,在
n
×
n
n \times n
n×n格的棋盘上放置
n
n
n个皇后,任何
2
2
2个皇后不放在同一行或同一列或同一斜线上
回溯算法
用
n
n
n元组
x
[
1
:
n
]
x[1 : n]
x[1:n]表示
n
n
n皇后问题的解,
x
[
i
]
x[i]
x[i]表示皇后
i
i
i放在棋盘的第
i
i
i行的第
x
[
i
]
x[i]
x[i]列
如果将$n \times n $格的棋盘看做二维方阵,其行号从上到下,列号从左到右依次编号为
1
1
1,
2
2
2,
⋯
\cdots
⋯,
n
n
n,从棋盘左上角到右下角的主对角线及其平行线上,
2
2
2个下标值的差值相等,斜率为
+
1
+1
+1的每条斜线上,
2
2
2个下标值的和值相等,若
2
2
2个皇后放置的位置分别是
(
i
,
j
)
(i , j)
(i,j)和
(
k
,
l
)
(k , l)
(k,l),且
i
−
j
=
k
−
l
i - j = k - l
i−j=k−l或
i
+
j
=
k
+
l
i + j = k + l
i+j=k+l,则说明这
2
2
2个皇后处于同一斜线上,由此可知,只要
∣
i
−
k
∣
=
∣
j
−
l
∣
|i - k| = |j - l|
∣i−k∣=∣j−l∣成立,就表明
2
2
2个皇后位于同一条斜线上
用回溯法解
n
n
n皇后问题时,用完全
n
n
n叉树表示解空间
可行性约束剪去不满足行、列和斜线约束的子树
当
i
=
n
i = n
i=n时,算法搜索至叶结点,得到一个新的
n
n
n皇后互不攻击放置方案,当前已找到的可行方案数
s
u
m
sum
sum增
1
1
1
当
i
<
n
i < n
i<n时,当前扩展结点
Z
Z
Z是解空间中的内部结点,该结点有
n
n
n个儿子结点,对当前扩展结点
Z
Z
Z的每个儿子结点检查其可行性,并以深度优先的方式递归地对可行子树搜索,或剪去不可行子树
Python实现
defsolve_n_queens(n):
board =[['.']* n for _ inrange(n)]
solutions =[]defis_valid(row, col):# 检查当前位置是否可以放置皇后for i inrange(row):if board[i][col]=='Q':returnFalseif col -(row - i)>=0and board[i][col -(row - i)]=='Q':returnFalseif col +(row - i)< n and board[i][col +(row - i)]=='Q':returnFalsereturnTruedefbacktrack(row):if row == n:# 找到一个解决方案
solutions.append([''.join(row)for row in board])returnfor col inrange(n):if is_valid(row, col):
board[row][col]='Q'
backtrack(row +1)
board[row][col]='.'
backtrack(0)return solutions
n =4
solutions = solve_n_queens(n)print('-'*5)for solution in solutions:print('\n'.join(solution))print('-'*5)
作者:严祥光,StarRocks Active Contributor,StarRocks 存算分离核心研发,在社区中主要负责数据导入、跨集群同步、数据迁移和容灾等工作。 有时候,你可能会为以下需求而苦恼,苦苦搜索更好的解决方案&#x…