algorithm - 更有效的算法来计算 N-queens 中的攻击？

Question

我正在研究针对 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) 做得更好？

Answer 1

定义数组

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。 .