文章/答案/技术大牛

发布

社区首页 >问答首页 >更有效的N皇后攻击计数算法？

问更有效的N皇后攻击计数算法？
EN

Stack Overflow用户

提问于 2016-02-16 12:38:30

回答 1查看 1.6K关注 0票数 3

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

我将板状态存储为一个intN数组，表示每个列中皇后的垂直位置(例如。在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;

O(N^2)在求解N=500+时会降低性能。

在计算攻击时，有可能比O(N^2)做得更好吗？

algorithm

big-o

asymptotic-complexity

n-queens

回答 1

Stack Overflow用户

回答已采纳

发布于 2016-02-16 12:53:02

定义数组

rows, columns, left_diagonals, right_diagonals

分别计算i-th行、列、左对角线( x和y，使x-y=c表示某些c)、右对角线(all x和y表示某些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皇后问题，您不需要检查攻击的次数。你只需要检查一下是否存在攻击。

另外，如果您正在寻找问题的单一解决方案，那么就有一个非常有效的算法。

票数 3

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/35432855

复制

相似问题

问更有效的N皇后攻击计数算法？
EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问更有效的N皇后攻击计数算法？EN

回答 1

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问更有效的N皇后攻击计数算法？
EN