代码之家 › 专栏 › 技术社区 › Brendan Hill

更有效的算法来计算N女王的攻击?

n-queens asymptotic-complexity big-o algorithm

Brendan Hill · 技术社区 · 10 年前

我正在研究基于DFS的N皇后问题解决方案。

我将电路板状态存储为一个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)做得更好吗?

1 回复 | 直到 10 年前

sve 10 年前

定义阵列

rows, columns, left_diagonals, right_diagonals

它们分别计算了 i -第行、第列、左对角线(全部 x 和 y 这样 x-y=c 对一些人来说 c ),右对角线(全部 x(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 .

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

1 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

1 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

1 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

1 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

1 年前