检查2维阵列（如八个皇后问题）

Question

我的问题是非常相似的八个皇后问题。

我有2维阵列（N×N）个的是，例如，如下所示：

0,0,0,0,1 y
0,0,0,0,0 |
0,0,0,0,0 V
0,0,0,1,0
0,0,0,0,0
x->

我检查水平，垂直和对角的1次出现

\,0,|,0,/
0,\,|,/,0
-,-,1,-,-
0,/,|,\,0
/,0,|,0,\

我在一个列表中考虑只存储（X，Y）的“1”的志愿服务岗位

[[4,0],[3,3]]

和数学解决它，检查与另一个（X1，Y1）的 “1” 的每一个位置< - >（X2，Y2），

如果x1 == x2或y1 == y2 we have a collision!如果不检查：

x2 == x1 + z;
y2 == y1 + z;
x2 == x1 - z;
y2 == y1 - z;

（???）

其中z是+/-该( x1+z in 0..N ) and ( y1+z in 0..N ) .......

我的问题斜向碰撞检查，有没有更好的办法做到这一点??? 的

Answer 1

一种可能的解决方案：

def collision(x1, y1, x2, y2):
    return x1 == x2 or y1 == y2 or abs(x1-x2) == abs(y1-y2)

即。存在冲突，如果两个点都在同一水平行中，相同的垂直行或同一对角线（垂直距离==水平距离）。

Answer 2

您描述听起来像一个精确覆盖问题的一个实例，其可以使用一种算法Knuth的调用来解决算法X 。我实现了一个数独在Javascript求解使用这种技术。你或许可以在Python实现了。

Answer 3

我认为这将是更快，如果你不解决这个问题，但数学首先要检查所有的行为多发的1秒，那么所有列，最后所有的对角线。

下面是一些代码来测试以简单的方式的对角线。 （它的JavaScript，对不起！）

var count = 0;
for (column = -n; column < n; column++) {
    for (row = 0; row < n; row++) {
            // conditions for which there are no valid coordinates.
            if (column + row > 6) {
                break;
            }
            if (column < 0) {
                continue;

            if (field[row][column] == 1) {
                count++;
                if (count == 2)
                    break; // collision
            }
    }
}

此方法将具有O(n^2)的复杂性，而你建议的一个具有O(n^2 + k^2)的复杂性（k是1的数量）如k总是很小，这应该是没有问题的。

Answer 4

假设你实际上有一个N维空间，其中你可能不，则可以使用该碰撞检测器：

def collision(t1, t2):
    return len(set([abs(a-b) for a,b in zip(t1, t2)] + [0])) <= 2

它传递一对与你喜欢的任何元数的元组，并且如果在两个点位于任何N维对角线它将返回true。