Controllo dell'array bidimensionale (come il puzzle delle otto regine)

Question

Il mio problema è molto simile al puzzle delle otto regine.

Ho un array bidimensionale (N x N) che, ad esempio, assomiglia a questo:

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

Sto controllando orizzontalmente, verticalmente e diagonalmente le occorrenze di 1

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

Sto pensando di memorizzare solo le posizioni (x,y) di "1" in un elenco

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

e risolvendolo matematicamente, controlla ogni posizione di "1" con un'altra (x1,y1)<->(x2,y2),

Se x1 == x2 O y1 == y2 we have a collision! in caso contrario controlla:

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

(???)

dove z è +/- quello ( x1+z in 0..N ) and ( y1+z in 0..N ) .......

Il mio problema è verificare la collisione diagonale, esiste un modo migliore per farlo???

Answer 1

Una possibile soluzione:

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

cioè.si verifica una collisione se i due punti si trovano sulla stessa riga orizzontale, sulla stessa riga verticale o sulla stessa diagonale (distanza verticale == distanza orizzontale).

Answer 2

La tua descrizione sembra un'istanza di un problema di copertura esatto, che può essere risolto utilizzando un algoritmo chiamato da Knuth Algoritmo X.Ho implementato a Risolutore di Sudoku in Javascript utilizzando questa tecnica.Probabilmente puoi trovare implementazioni anche in Python.

Answer 3

Penso che sarebbe molto più veloce se non lo risolvessi matematicamente ma prima controllassi tutte le righe per più occorrenze di 1, poi tutte le colonne e infine tutte le linee diagonali.

Ecco del codice per testare le linee diagonali in modo semplice.(È JavaScript, scusa!)

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

Questo metodo avrebbe una complessità di O(n^2), mentre quello da te suggerito ha una complessità di O(n^2 + k^2) (k è il numero di 1) Se k è sempre piccolo, questo non dovrebbe essere un problema.

Answer 4

Supponendo che tu abbia effettivamente uno spazio N-dimensionale, cosa che probabilmente non è così, puoi utilizzare questo rilevatore di collisioni:

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

Passagli una coppia di tuple con l'arietà che preferisci e restituirà vero se i due punti giacciono su una qualsiasi diagonale N-dimensionale.