Как разрешить максимальное манхэттенское расстояние между всеми точками в группе

Question

У меня есть 2D-массив, в котором я хочу создать группы, в которых все точки в группе имеют максимальное манхэттенское расстояние между ними. Группы могут быть непересекающимися. Например, из этого начального массива (10 x 10):

      [[ 67  97  72  35  73  77  80  48  21  34]
 [ 11  30  16   1  71  68  72   1  81  23]
 [ 85  31  94  10  50  85  63  11  61  69]
 [ 64  36   8  37  36  72  96  20  91  19]
 [ 99  54  84  56   3  80  41  45   1   8]
 [ 97  88  21   8  54  55  88  45  63  82]
 [ 13  53   1  90  39  28  48  15  86   8]
 [ 26  63  36  36   3  29  33  26  54  58]
 [ 74  40  53  12  21  17   4  87  14  22]
 [ 23  98   3 100  85  12  65  21  83  97]]

Я должен быть в состоянии разделить его на разные группы.

В настоящее время у меня есть функция, которая находит возможные точки, которые я мог бы добавить в группу с начальной точкой (здесьявляется первой точкой группы):

      def possible_munips(x, y, munip, dist_manhattan_max, temp_array):
    list = []
    for i in range(y):
        for j in range(x):
            if (j, i) != munip and munipIsValid(j, i, munip, dist_manhattan_max) and temp_array[i][j] != -1:
                list.append((j, i, temp_array[i][j]))

Я перебираю 2D-массив,, в котором точки, которые уже были помещены в группу, имеют значение -1.проверяет, находится ли точка на максимальном манхэттенском расстоянии от начальной точки.

Затем я просто добавляю точки одну за другой, пока не достигну нужной длины () группы, и каждый раз, когда я добавляю новую точку в группу, я удостоверяюсь, что группа остается действительной, например:

      munips = possible_munips(x, y, munip, dist_manhattan_max, temp_array)

while len(new_group) < k:
    point = munips[0]
    new_group.append(point)
    if not groupIsValid(new_group, distManhattanMax, len(new_group)):
        new_group.remove(point)
    munips.remove(point)
    current_sol.append(new_group)

for groups in current_sol:
    for munip in groups:
        temp_array[munip[1], munip[0]] = -1

Я также попытался добавить функцию обмена, которая пытается поменять местами точки между группами, чтобы сделать их обе действительными. Но иногда это не находит решения, и я остаюсь с недействительной группой.