Как использовать функции sorted() и min() с OR-Tools в Python? ⇐ Python

[Anonymous]

Я создаю решатель судоку на Python для решения классических и неклассических судоку, используя cp_model из библиотеки Google ortools. В частности, я пытаюсь написать метод, решающий вариант судоку, в котором каждая строка/столбец/подсетка содержит 9 уникальных чисел от 0 до 11. Например, если в строке 1 судоку есть числа [1, 2, 3, 4, 5, 6, 7, 8, 9], строки 2–9 не могут иметь одинаковые числа ни в одной перестановке. Однако строка 2 может содержать числа [0, 1, 2, 3, 4, 5, 6, 7, 8], поскольку это отдельный набор из 9 чисел. Аналогично, это различие применимо ко всем строкам.
Вот в чем задача: поскольку в каждой строке содержится 9 записей, для данного набора из 9 чисел их имеется 9! для их отображения разные перестановки в строке.
Итак, я решил создать уникальную подпись для каждой строки. Получите все элементы строки, отсортируйте их по возрастанию и создайте 18-значную подпись, уникальную для строки. Например, для строки 1 с элементами [1, 2, 3, 4, 5, 6, 7, 8, 9] уникальная подпись будет 010203040506070809. Итак, если какая-то другая строка имеет те же 9 чисел в какой-то другой перестановке , он также будет иметь ту же подпись 010203040506070809. Эта подпись будет отличаться только в том случае, если строка имеет еще один набор из 9 цифр независимо от 9! возможные перестановки. Следовательно, если я добавлю ограничение, согласно которому все уникальные подписи должны быть разными, я должен получить то, что хочу.
К сожалению, это не работает, поскольку метод sorted() или сортировка списка не работает с ortools. Итак, мне пришлось пойти на грубый подход и сгенерировать все 9! подписи (я знаю, что это требует больших вычислительных затрат) и выберите наименьшую подпись в качестве уникальной подписи, используя приведенный ниже фрагмент кода.

Код: Выделить всё

def DistinctRowColSubGridConstraints(self):
'''
Collect all rows, create a unique lexicographical signature for each row,
and ensure that all rows are unique.
'''

# Helper to encode a row as a lexicographical signature based on permutation indices
def encode_as_lexicographical_index(row):

# Create a list of indices: [0, 1, 2, ..., n-1] where n is the row length
n = len(row)
indices = list(range(n))

# Generate all permutations of the indices list
all_permutations = list(permutations(indices))

# Generate All Signatures
All_Signatures = []
for perm in all_permutations:
signature = 0
for idx in perm:
signature = signature * 100 + row[idx]  # Concatenate each element to form the signature
All_Signatures.append(signature)

return All_Signatures

# Collect all rows and create lexicographical signature for each
row_signatures = []
for i in range(self.Rows):

row = [self.Cells[i][j] for j in range(self.Cols)]  # Get the row
all_signatures = encode_as_lexicographical_index(row)  # Get all possible signatures

RowUniqueSingature = self.Model.NewIntVar(lb=10**17, ub=10**18-1, name=f"RowUniqueSignature_{i}")
self.Model.Add(RowUniqueSingature==min(all_signatures))

row_signatures.append(RowUniqueSingature)  # Add signature to list

# Ensure all rows have unique lexicographical signatures
self.model.AddAllDifferent(row_signatures)

print("Distinct row constraints added.")

К сожалению, это также не работает, поскольку min() не может работать с ограниченными линейными выражениями.
Я был бы признателен за любую помощь или рекомендации по устранению этой проблемы. Я был бы очень признателен, если бы кто-нибудь указал мне на более эффективное решение. Спасибо.

Подробнее здесь: https://stackoverflow.com/questions/793 ... -in-python