Rockbands Rätsel mittels OR-Tools lösen

Man soll die 26 Buchstaben des Alphabets den Werten von 1 bis 16 derartig zuordnen, sodass eine Reihe von Nebenbedingungen erfüllt sind. zB soll $A + C + D + C = 45$ gelten. Anschließend ergibt sich ein Lösungswort aus der zurückübersetzen Kombination von einigen Zahlen.

https://developers.google.com/optimization

In [3]:

from IPython.display import Image
Image("rockbands.jpg")

In [4]:

from string import ascii_uppercase
ascii_uppercase

'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

CP-SAT solver: https://developers.google.com/optimization/cp/cp_solver

In [5]:

from ortools.sat.python import cp_model
model = cp_model.CpModel()

# Definition aller Buchstaben, als Integer von 1 bis 26
letters = [model.NewIntVar(1, len(ascii_uppercase), l) for l in ascii_uppercase]

# Alle müssen unterschiedlich sein – so eine Nebenbedingung ist speziell bei SAT Solvern möglich
model.AddAllDifferent(letters)

# Wir speichern jede Buchstaben-Variable global ab
for char, var in zip(ascii_uppercase, letters):
    globals()[char] = var

In [6]:

# Beispielsweise
F

F(1..26)

Nebenbedingungen

In [7]:

# Summe der Variablen nach Buchstaben + ein print zur Kontrolle

def band(chars, s):
    varsum = sum([globals()[c] for c in chars if c in ascii_uppercase])
    model.Add(varsum == s)
    print(f"{varsum} == {s}")

In [8]:

# Alle Buchstaben zusammen kennen wir auch
band(ascii_uppercase, sum(range(1, len(ascii_uppercase) + 1)))

(((((((((((((((((((((((((A + B) + C) + D) + E) + F) + G) + H) + I) + J) + K) + L) + M) + N) + O) + P) + Q) + R) + S) + T) + U) + V) + W) + X) + Y) + Z) == 351

In [9]:

# Das würde auch gehen, aber wir verwenden die band-Funktion
model.Add(A + C + D + C == 45)

<ortools.sat.python.cp_model.Constraint at 0x7fe4a376fa90>

In [10]:

band('BEATLES', 52)
band('COLDPLAY', 62)
band('DEEP PURPLE', 27)
band('DIRE STRAITS', 82)
band('EAGLES', 29)
band('GENESIS', 47)
band('JETHRO TULL', 97)
band('LED ZEPPELIN', 55)
band('LYNYRD SKYNYRD', 126)
band('METALLICA', 87)
band('NIRVANA', 75)
band('OASIS', 43)
band('PINK FLOYD', 92)
band('ROLLING STONES', 103)
band('STEPPENWOLF', 91)
band('STYX', 60)
band('URIAH HEEP', 78)
band('VAN HALEN', 88)

((((((B + E) + A) + T) + L) + E) + S) == 52
(((((((C + O) + L) + D) + P) + L) + A) + Y) == 62
(((((((((D + E) + E) + P) + P) + U) + R) + P) + L) + E) == 27
((((((((((D + I) + R) + E) + S) + T) + R) + A) + I) + T) + S) == 82
(((((E + A) + G) + L) + E) + S) == 29
((((((G + E) + N) + E) + S) + I) + S) == 47
(((((((((J + E) + T) + H) + R) + O) + T) + U) + L) + L) == 97
((((((((((L + E) + D) + Z) + E) + P) + P) + E) + L) + I) + N) == 55
((((((((((((L + Y) + N) + Y) + R) + D) + S) + K) + Y) + N) + Y) + R) + D) == 126
((((((((M + E) + T) + A) + L) + L) + I) + C) + A) == 87
((((((N + I) + R) + V) + A) + N) + A) == 75
((((O + A) + S) + I) + S) == 43
((((((((P + I) + N) + K) + F) + L) + O) + Y) + D) == 92
((((((((((((R + O) + L) + L) + I) + N) + G) + S) + T) + O) + N) + E) + S) == 103
((((((((((S + T) + E) + P) + P) + E) + N) + W) + O) + L) + F) == 91
(((S + T) + Y) + X) == 60
((((((((U + R) + I) + A) + H) + H) + E) + E) + P) == 78
(((((((V + A) + N) + H) + A) + L) + E) + N) == 88

Lösen

Status 4 ist "optimal", 3 wäre "infeasible"

In [11]:

solver = cp_model.CpSolver()
status = solver.Solve(model)
status

4

In [12]:

# Kontrolle

def check(chars):
    vals = [solver.Value(globals()[c]) for c in chars if c in ascii_uppercase]
    return sum(vals)

In [13]:

assert check("ACDC") == 45
assert check('BEATLES') == 52
assert check("STEPPENWOLF") == 91
assert check("ROLLING STONES") == 103
assert check("OASIS") == 43
assert check("VAN HALEN") == 88

Lösung

Für die Lösung übersetzen wir die Zahlen wieder zurück zu den Buchstaben. Dafür machen wir uns ein dictionary von den Lösungswert jedes Buchstabens zu dem Buchstaben (also das Invertierte!) ...

In [14]:

mapping = {solver.Value(globals()[ascii_uppercase[i]]) : ascii_uppercase[i] for i in range(len(ascii_uppercase))}
mapping

{8: 'A',
'B',
'C',
'D',
'E',
'F',
'G',
'H',
'I',
'J',
'K',
'L',
'M',
'N',
'O',
'P',
'Q',
'R',
'S',
'T',
'U',
'V',
'W',
'X',
'Y',
'Z'}

In [15]:

# bzw. der Reihe nach
{i: mapping[i] for i in sorted(mapping)}

{1: 'E',
'P',
'L',
'R',
'D',
'U',
'S',
'A',
'G',
'I',
'O',
'N',
'T',
'Y',
'Z',
'C',
'F',
'K',
'B',
'J',
'V',
'W',
'H',
'Q',
'M',
'X'}

... und übersetzen die Zahlen

In [16]:

for i in [4, 11, 26, 14, ' ', 25, 6, 7, 10, 16]:
    if type(i) == str:
        print(i, end='')
    else:
        print(mapping[i], end='')

ROXY MUSIC

CoCalc provides the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual users to large groups and classes!

Rockbands Rätsel mittels OR-Tools lösen

CP-SAT solver: https://developers.google.com/optimization/cp/cp_solver

Nebenbedingungen

Lösen

Lösung

Product

Resources

Company