2次元配列のチェック（8つのクイーンパズルのような）

Question

私の問題は、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 ) .......

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

Answer 1

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

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

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

Answer 2

あなたの説明はクヌースは呼び出すアルゴリズムを使用して解決することができ、正確な被覆問題のインスタンス、のように聞こえますアルゴリズム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
            }
    }
}

あなたが示唆した1が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

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