Verificando matriz de 2 dimensões (como problema das oito damas)

Question

O meu problema é muito semelhante ao problema das oito damas.

Eu tenho matriz de 2 dimensões (N x N) que, por exemplo, esta aparência:

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

Estou verificando horizontal, vertical e diagonal para ocorrências de 1

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

Estou pensando em armazenar apenas os (x, y) postions de "1" está em uma lista

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

e resolvê-lo matematicamente, verificar cada posição "1" com outro (x1, y1) <-> (x2, y2),

Se x1 == x2 ou y1 == y2 we have a collision! se não verificar:

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

(???)

em que Z é de +/- que ( x1+z in 0..N ) and ( y1+z in 0..N ) .......

Meu problema é a verificação de colisão diagonal, há uma maneira melhor de fazer isso ???

Answer 1

Uma possível solução:

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

i. existe uma colisão, se os dois pontos estão na mesma linha horizontal, mesma linha vertical ou diagonal mesma (distância vertical == distância horizontal).

Answer 2

A sua descrição soa como uma instância de um problema de cobertura exata, que podem ser resolvidos usando um algoritmo Knuth chama algoritmo X . Eu tenho implementado um Sudoku solver em Javascript usando esta técnica. Você provavelmente pode encontrar implementações em Python, também.

Answer 3

Eu acho que seria muito mais rápido se você não resolvê-lo matematicamente, mas verifique primeiro todas as linhas para várias ocorrências de 1s, então todas as colunas e, finalmente, todas as linhas diagonais.

Aqui está um código para testar as linhas diagonais em uma maneira simples. (É 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
            }
    }
}

Este método teria uma complexidade de O(n^2), enquanto que o que você sugeriu tem uma complexidade de O(n^2 + k^2) (k sendo o número de 1s) Se k é sempre pequeno este não deve ser problema.

Answer 4

Assumindo que você realmente tem um espaço N-dimensional, que você provavelmente não, você pode usar este detector de colisão:

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

Passe um par de tuplas com o que quer que arity você gosta, e ele irá retornar true se os dois pontos ficam em qualquer diagonal N-dimensional.