Как я могу определить, безопасна ли королева, если я ограничу диапазон атаки королевы 5 квадратами?

Question

Мне нужно разместить N фигурок на доске MxM, чтобы две королевы не атаковали друг друга.Отличие от оригинала состоит в том, что королевы могут атаковать только до 5 квадратов от их местоположения, а не весь ряд, столбец или диагональ, как в исходной задаче.

Одна идея, которую я разыгрываю в своейГолова должна разместить первую Королеву на доске у доски [i] [j], а затем также поместить ее в 5 соседних квадратов, как показано на рисунке ниже.

Ниже приведена функция isSafe из исходной задачи N-Queens.

Требуется руководство по проверкеесли размещение королевы безопасно.

def isSafe(board, row, col): 

# Check this row on left side 
for i in range(col): 
    if board[row][i] == 1: 
        return False

# Check upper diagonal on left side 
for i,j in zip(range(row,-1,-1), range(col,-1,-1)): 
    if board[i][j] == 1: 
        return False

# Check lower diagonal on left side 
for i,j in zip(range(row,N,1), range(col,-1,-1)): 
    if board[i][j] == 1: 
        return False

return True

Итак, как мне определить, безопасна ли королева, если я ограничу диапазон королевы 5 квадратами?

Answer 1

Существует два основных подхода:

1) Для каждой новой королевы проверьте, находятся ли другие в диапазоне горизонталей / вертикалей / диагоналей.Дольше проверять, быстрее добавлять / удалять

2) Помечать битые ячейки номерами: 0 для безопасной, K для ячейки, побитой K ферзями.В этом случае вы можете легко определить, является ли ячейка безопасной, увеличивать значения битых ячеек для новой королевы и уменьшать их, если вам нужно удалить королеву.Быстрее проверять, дольше добавлять / удалять.

Чтобы изменить пример кода, ограничьте диапазоны.Например, диагональ слева внизу:

for i,j in zip(range(row, max(-1, row - 5),-1), range(col, min(N, col + 5), 1)): 
    if board[i][j] == 1: 
         return False