Wie verwende ich die Funktionen sorted() und min() mit OR-Tools in Python? ⇐ Python

[Guest]

Ich baue einen Python-Sudoku-Löser, um die klassischen und nicht-klassischen Sudokus mithilfe des cp_model aus der ortools-Bibliothek von Google zu lösen. Konkret versuche ich, eine Methode zu schreiben, die eine Sudoku-Variante löst, bei der jede Zeile/Spalte/jedes Untergitter 9 eindeutige Zahlen zwischen 0 und 11 enthält. Wenn beispielsweise Zeile 1 des Sudokus Zahlen [1, 2, 3, 4, 5, 6, 7, 8, 9] dürfen die Zeilen 2-9 in keiner Permutation die gleichen Zahlen haben. Zeile 2 kann jedoch die Zahlen [0, 1, 2, 3, 4, 5, 6, 7, 8] enthalten, da es sich hierbei um eine eindeutige Menge von 9 Zahlen handelt. Ebenso gilt diese Unterscheidung für alle Zeilen.
Hier liegt die Herausforderung: Da jede Zeile 9 Einträge hat, gibt es für einen gegebenen Satz von 9 Zahlen 9! Verschiedene Permutationen hintereinander, damit sie angezeigt werden.
Also habe ich beschlossen, für jede Zeile eine eindeutige Signatur zu erstellen. Holen Sie sich alle Elemente einer Zeile, sortieren Sie sie in aufsteigender Reihenfolge und erstellen Sie eine 18-stellige Signatur, die für eine Zeile eindeutig ist. Beispielsweise wäre für Zeile 1 mit den Elementen [1, 2, 3, 4, 5, 6, 7, 8, 9] die eindeutige Signatur 010203040506070809. Wenn also eine andere Zeile dieselben 9 Zahlen in einer anderen Permutation hat , wird es auch die gleiche Signatur von 010203040506070809 haben. Diese Signatur unterscheidet sich nur, wenn die Zeile hat einen weiteren Satz von 9 Zahlen, unabhängig von der 9! mögliche Permutationen. Wenn ich also eine Einschränkung hinzufüge, dass alle eindeutigen Signaturen unterschiedlich sein müssen, sollte ich bekommen, was ich will.
Leider funktioniert dies seit der Methode sorted() nicht oder die Listensortierung funktioniert mit ortools nicht gut. Also musste ich einen groben Ansatz wählen und alle 9 generieren! Signaturen (mir ist bewusst, dass dies rechenintensiv ist) und wählen Sie mithilfe des folgenden Codeausschnitts die kleinste Signatur als eindeutige Signatur aus.

Code: Select all

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.")

Leider funktioniert dies auch nicht, da min() bei begrenzten linearen Ausdrücken nicht funktionieren kann.
Ich würde mich über jede Hilfe oder Hilfe freuen Anleitung zur Behebung dieses Problems. Ich würde mich sehr freuen, wenn mir jemand eine sehr effiziente Lösung nennen könnte. Vielen Dank.