Проверка двумерного массива (например, головоломка с восемью королевами)
Вопрос
Моя проблема очень похожа на головоломку с восемью королевами.
У меня есть двумерный массив (N x N), который, например, выглядит так:
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->
Я проверяю по горизонтали, вертикали и диагонали наличие 1.
\,0,|,0,/
0,\,|,/,0
-,-,1,-,-
0,/,|,\,0
/,0,|,0,\
Я думаю о сохранении в списке только позиций (x,y) цифр «1».
[[4,0],[3,3]]
и решив его математически, проверьте каждую позицию «1» с другой (x1,y1)<->(x2,y2),
если x1 == x2
или y1 == y2
we have a collision!
если нет, проверьте:
x2 == x1 + z;
y2 == y1 + z;
x2 == x1 - z;
y2 == y1 - z;
(???)
где z +/- это ( x1+z in 0..N ) and ( y1+z in 0..N ) .......
Моя проблема заключается в проверке диагонального столкновения, есть ли лучший способ сделать это???
Решение
Одно из возможных решений:
def collision(x1, y1, x2, y2):
return x1 == x2 or y1 == y2 or abs(x1-x2) == abs(y1-y2)
то естьСтолкновение имеет место, если две точки находятся в одном горизонтальном ряду, одном вертикальном ряду или одной диагонали (вертикальное расстояние == горизонтальное расстояние).
Другие советы
Ваше описание звучит как пример точной задачи о прикрытии, которую можно решить с помощью алгоритма, который называет Кнут. Алгоритм X.Я реализовал Решатель судоку на Javascript используя эту технику.Вероятно, вы также можете найти реализации на Python.
Я думаю, было бы намного быстрее, если бы вы не решали это математически, а сначала проверяли все строки на наличие нескольких единиц, затем все столбцы и, наконец, все диагональные линии.
Вот код для простой проверки диагональных линий.(Это JavaScript, извините!)
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
}
}
}
Этот метод будет иметь сложность O(n^2)
, тогда как тот, который вы предложили, имеет сложность O(n^2 + k^2)
(k — количество единиц), если k
всегда мал, это не должно быть проблемой.
Предполагая, что у вас действительно есть N-мерное пространство, которого у вас, вероятно, нет, вы можете использовать этот детектор столкновений:
def collision(t1, t2):
return len(set([abs(a-b) for a,b in zip(t1, t2)] + [0])) <= 2
Передайте ему пару кортежей с любой желаемой арностью, и он вернет true, если две точки лежат на любой N-мерной диагонали.