Überprüfen 2-dimensionales Array (wie Damenproblem)

Question

Mein Problem ist sehr ähnlich zu acht Damen Puzzle.

Ich habe 2-dimensionalen Array (N x N), dass zum Beispiel sieht wie folgt aus:

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->

Ich überprüfe horizontal, vertikal und diagonal nach Vorkommen von 1

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

Ich denke an nur den (x, y) postions von "1" 's in einer Liste speichern

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

und es mathematisch zu lösen, überprüft jede Position von "1" mit einem anderen (x1, y1) <-> (x2, y2),

Wenn x1 == x2 oder y1 == y2 we have a collision! wenn nicht überprüfen:

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

(???)

, wobei z +/- dass ( x1+z in 0..N ) and ( y1+z in 0..N ) .......

Mein Problem ist für diagonal Kollisionsprüfung, gibt es einen besseren Weg, es zu tun ???

Answer 1

Eine mögliche Lösung:

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

d. gibt es eine Kollision, wenn die zwei Punkte auf der gleichen horizontalen Zeile, derselben vertikalen Reihe oder derselben Diagonale (vertikale Abstand == horizontalen Abstand) sind.

Answer 2

Ihre Beschreibung klingt wie eine Instanz eines genauen Überdeckungsproblem, das einen Algorithmus Knuth ruft gelöst werden kann unter Verwendung von Algorithmus X . Ich habe einen Sudoku-Löser in Javascript mit dieser Technik. Sie können sich wahrscheinlich Implementierungen in Python finden, auch.

Answer 3

ich denke, es wäre viel schneller, wenn Sie es nicht mathematisch lösen hat, sondern zunächst alle Zeilen für mehrere Vorkommen von 1s überprüfen, dann alle Spalten und schließlich alle diagonalen Linien.

Hier ist ein Code, die diagonalen Linien auf einfache Art und Weise zu testen. (Es ist JavaScript, sorry!)

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
            }
    }
}

Dieses Verfahren würde eine Komplexität von O(n^2) hat, während diejenige, die Sie eine Komplexität von O(n^2 + k^2) hat vorgeschlagen (k die Anzahl der 1s ist) Wenn k immer klein ist, sollte dies kein Problem sein.

Answer 4

Angenommen, Sie tatsächlich einen N-dimensionalen Raum haben, die Sie wahrscheinlich nicht, können Sie diesen Kollisionsdetektor verwenden:

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

Direkt ein Paar von Tupeln mit dem, was arity Sie mögen, und es gibt true zurück, wenn die beiden Punkte auf jedem N-dimensionalen Diagonale liegen.