我正在研究针对 N 皇后问题的基于 DFS 的解决方案。
我将棋盘状态存储为一个 int[N] 数组,表示每列中皇后的垂直位置(例如,将皇后沿对角线向下放置 6x6 棋盘为 state = { 0, 1, 2, 3, 4 , 5 }), 其中-1代表“本列无皇后”。
我当前计算给定状态配置中的皇后攻击的算法具有 O(n^2) 的复杂度:
function count_attacks(state)
attack_count = 0
for each column index c1
if state[c1] == -1 continue
for each column index c2 further along than c1
if state[c2] == -1 continue
// Lined up horizontally?
if state[c1] == state[c2] attack_count++
// Lined up diagonally?
else if (c2 - c1) == abs(state[c2] - state[c1]) attack_count++
// No need to check lined up vertically as impossible with this state representation
return attack_count;
在求解 N=500+ 时,O(N^2) 会降低性能。
在计算攻击方面是否有可能比 O(N^2) 做得更好?
最佳答案
定义数组
rows, columns, left_diagonals, right_diagonals
分别计算第 i
行、列、左对角线中的皇后数(所有 x
和 y
使得 x-y=c
对于某些 c
),右对角线(所有 x
和 y
使得 x+y =c
对于某些 c
)。该算法将是:
Intialize rows, columns, left_diagonals, right_diagonals with zero values
attacks = 0
for queen in queens
attacks += rows[queen.row];
attacks += columns[queen.column];
attacks += left_diagonals[queen.left_diagonal];
attacks += right_diagonals[queen.right_diagonal];
rows[queen.row]++;
columns[queen.column]++;
left_diagonals[queen.left_diagonal]++;
right_diagonals[queen.right_diagonal]++;
但是,要解决N
皇后问题,您不需要检查攻击次数。您只需要检查是否存在攻击。
此外,如果您正在寻找问题的单一解决方案,可以使用very efficient algorithm。 .
关于algorithm - 更有效的算法来计算 N-queens 中的攻击?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35432855/