5

私の問題は、8 クイーンズ パズルに非常によく似ています。

たとえば、次のような 2 次元配列 (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]]

それを数学的に解き、「1」のすべての位置を別の (x1,y1)<->(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 ) .......

私の問題は、斜めの衝突をチェックすることです。それを行うより良い方法はありますか???

4

4 に答える 4

20

考えられる解決策の 1 つ:

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

つまり、2 つの点が同じ水平列、同じ垂直列、または同じ対角線 (垂直距離 == 水平距離) にある場合、衝突が発生します。

于 2008-12-21T20:10:32.123 に答える
2

あなたの説明は、正確なカバー問題のインスタンスのように聞こえます。これは、Knuth がAlgorithm Xと呼ぶアルゴリズムを使用して解決できます。この手法を使用して、Javascript で数独ソルバーを実装しました。おそらく、Python でも実装を見つけることができます。

于 2008-12-21T21:06:14.163 に答える
0

実際に N 次元空間を持っていると仮定すると、おそらくそうではありませんが、この衝突検出器を使用できます。

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

任意のアリティを持つタプルのペアを渡すと、2 つの点が N 次元の対角線上にある場合に true が返されます。

于 2008-12-22T04:01:08.943 に答える
0

数学的に解かないと、はるかに高速になると思いますが、最初にすべての行で 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です。 が常に小さい場合、これは問題になりません。

于 2008-12-21T20:31:52.610 に答える