Comprobando una matriz bidimensional (como un rompecabezas de ocho reinas)

Question

Mi problema es muy similar al rompecabezas de las ocho reinas.

Tengo una matriz bidimensional (N x N) que, por ejemplo, se ve así:

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

Estoy comprobando horizontal, vertical y diagonalmente si hay apariciones de 1

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

Estoy pensando en almacenar sólo las posiciones (x,y) de "1" en una lista

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

y resolviéndolo matemáticamente, verifica cada posición de "1" con otro (x1,y1)<->(x2,y2),

si x1 == x2 o y1 == y2 we have a collision! si no, marque:

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

(???)

donde z es +/- eso ( x1+z in 0..N ) and ( y1+z in 0..N ) .......

Mi problema es comprobar si hay una colisión diagonal, ¿hay alguna forma mejor de hacerlo?

Answer 1

Una posible solución:

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

es decir. hay una colisión si los dos puntos están en la misma fila horizontal, misma fila vertical o misma (distancia vertical == distancia horizontal) diagonal.

Answer 2

Su descripción suena como una instancia de un problema de cobertura exacta, que puede resolverse mediante un algoritmo de Knuth llama algoritmo X . He implementado un Sudoku en Javascript usando esta técnica. Usted probablemente puede encontrar implementaciones en Python, también.

Answer 3

Creo que sería mucho más rápido si no ha solucionado matemáticamente pero primero comprueba todas las filas de múltiples ocurrencias de 1s, entonces todas las columnas y en fin todas las líneas diagonales.

Aquí hay un código para probar las líneas diagonales de una manera sencilla. (Es de JavaScript, lo siento!)

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

Este método tendría una complejidad de O(n^2), mientras que el que sugirió tiene una complejidad de O(n^2 + k^2) (siendo k el número de 1s) Si k es siempre pequeña esto no debería ser un problema.

Answer 4

Suponiendo que en realidad tienen un espacio N-dimensional, que es probable que no, puede utilizar este detector de colisiones:

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

Pase un par de tuplas con lo aridad te gusta, y que devolverá true si los dos puntos se encuentran en cualquier diagonal de N dimensiones.