提问人：M_1 提问时间：12/22/2008 最后编辑：Hubert KarioM_1 更新时间：2/6/2012 访问量：3654
检查二维数组（如八皇后拼图）
Checking 2-dimensional array (like eight queens puzzle)
问：
我的问题与八皇后谜题非常相似。
例如，我有二维数组（N x 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,\
我正在考虑在列表中仅存储“1”的 （x，y） 位置
[[4,0],[3,3]]
并用数学方法求解它，用另一个 （x1，y1）<->（x2，y2） 检查“1”的每个位置，
如果或否，请检查：x1 == x2y1 == y2we 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 ) .......
我的问题是检查对角线碰撞，有没有更好的方法???
答：
20赞
dF.
12/22/2008
#1
一种可能的解决方案：
def collision(x1, y1, x2, y2):
return x1 == x2 or y1 == y2 or abs(x1-x2) == abs(y1-y2)
即，如果两点在同一水平行、同一垂直行或同一对角线上（垂直距离 == 水平距离），则发生碰撞。
评论
0赞
strager
12/22/2008
我希望我有选票。这真是一个非常好的答案！但是，难道您不想找到 abs（dx） 和 abs（dy） 吗？
0赞
M_1
12/22/2008
谢谢你的非常好的回答！我从没想过会这么简单;)愚蠢的我......我已经设法使用您的碰撞函数编写了一个简单的蛮力检查器。现在我期待着检查另一个答案中提到的 Algoritm X。
0赞
nikhil
7/2/2012
y = mx + c对于对角线.我想知道为什么我的大脑不能工作，直到我看到这样的解决方案。m = 1
0赞
Georg Schölly
12/22/2008
#2
我认为如果你不用数学方法解决它，但首先检查所有行是否有多次出现的 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
}
}
}
这种方法的复杂度为 ，而您建议的方法的复杂度为 （k 是 1 的数量） 如果总是很小，这应该没有问题。O(n^2)O(n^2 + k^2)k
评论
0赞
strager
12/22/2008
“我的问题是检查对角线碰撞，有没有更好的方法???”——他不是在试图解决八皇后问题。他只是在检查碰撞。@dF 的方法是 O（1）。
0赞
Georg Schölly
12/22/2008
我的理解是，他检查是否至少存在一次碰撞，而不是点（x，y）是否有碰撞。dF 的方法是 O（1），但前提是您假设比较次数是静态的。
0赞
Jonathan Leffler
12/22/2008
k = N 不是吗？所以 O（n^2+k^2） = O（2n^2） = O（n^2）？当然，在 8 Queens 问题中，k = N。
0赞
Georg Schölly
12/22/2008
不，k 是数组中具有 1 的位置数，n 是数组一侧的长度。
2赞
Greg Hewgill
12/22/2008
#3
您的描述听起来像是一个精确覆盖问题的实例，可以使用 Knuth 称为算法 X 的算法来解决。我已经使用这种技术在 Javascript 中实现了一个数独求解器。您可能也可以在 Python 中找到实现。
评论
0赞
Johannes Schaub - litb
12/22/2008
+1 .这就是我首先想到的。但不确定，也没有做任何事情，所以等着一个知识渊博的人投票给他。现在发现他:p
0赞
M_1
12/22/2008
使用碰撞功能进行了简单的暴力检查。现在，检查您的方法（虽然看起来很复杂）......谢谢！
0赞
recursive
12/22/2008
#4
假设你确实有一个 N 维空间，你可能没有，你可以使用这个碰撞检测器：
def collision(t1, t2):
return len(set([abs(a-b) for a,b in zip(t1, t2)] + [0])) <= 2
用你喜欢的任何 arity 传递给它一对元组，如果这两个点位于任何 N 维对角线上，它将返回 true。
评论