Vérification tableau 2 dimensions (comme huit reines casse-tête)

Question

Mon problème est très similaire à huit reines casse-tête.

J'ai tableau à 2 dimensions (N x N) que, par exemple, ressemble à ceci:

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

Je vérifie horizontalement, verticalement ou en diagonale pour les occurrences de 1

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

Je pense à stocker seulement le (x, y) postions de l ' "1" dans une liste

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

et résoudre mathématiquement, vérifier toutes les positions de "1" avec un autre (x1, y1) <-> (x2, y2),

si x1 == x2 ou y1 == y2 we have a collision! sinon vérifier:

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

(???)

où z est de +/- que ( x1+z in 0..N ) and ( y1+z in 0..N ) .......

Mon problème est la vérification de collision diagonale, est-il une meilleure façon de le faire ???

Answer 1

Une solution possible:

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

i.e.. il y a une collision si les deux points sont sur la même ligne horizontale, une même rangée verticale ou même diagonale (distance verticale == distance horizontale).

Answer 2

Votre description sons comme un exemple d'un problème de couverture exacte, qui peut être résolu en utilisant un algorithme Knuth appelle algorithme X . J'ai mis en place un Sudoku en Javascript en utilisant cette technique. Vous pouvez probablement trouver des implémentations en Python, aussi.

Answer 3

Je pense que ce serait beaucoup plus rapide si vous ne parvenez pas à résoudre mathématiquement, mais d'abord vérifier toutes les lignes pour plusieurs occurrences de 1s, puis toutes les colonnes et, enfin, toutes les lignes diagonales.

Voici un code pour tester les lignes diagonales de manière simple. (JavaScript de, désolé!)

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

Cette méthode aurait une complexité de O(n^2), alors que celui que vous suggérez a une complexité de O(n^2 + k^2) (k étant le nombre de 1) Si k est toujours faible cela ne devrait pas poser de problème.

Answer 4

En supposant que vous ne réellement avoir un espace à N dimensions, que vous ne probablement pas, vous pouvez utiliser ce détecteur de collision:

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

Passez une paire de tuples avec tout ce que vous aimez arité, et il retourne vrai si les deux points se trouvent sur une diagonale N dimensions.