Rozwiązanie zagadki noworocznej

https://xpil.eu/Cb9hK 📋

Dwunastościan foremny ma 20 wierzchołków, każdy ma przypisaną unikalną liczbę pierwszą. Zadaniem było znalezienie tych liczb tak, żeby suma wierzchołków na każdej z 12 ścian wyniosła dokładnie 2025.

Zaczniemy od ustalenia górnej granicy wartości wierzchołka. Wiemy, że suma ma być 2025, a także, że żaden z wierzchołków nie może być dwójką, ponieważ suma jednej liczby parzystej i czterech nieparzystych daje w wyniku liczbę parzystą. Jeżeli więc cztery wierzchołki ponumerujemy czterema najmniejszymi nieparzystymi liczbami pierwszymi (3, 5, 7, 11), to piąty nie może być większy niż 1999. Tak więc mamy 302 dostępne liczby pierwsze, które trzeba przypisać do 20 wierzchołów.

from sympy import primerange
print(len([x for x in primerange(3, 2000)]))

Na ile sposobów można to zrobić?

Python mówi, że na 8,604,079,018,115,896,020,099,410,826,810. Osiem kwintylionów z hakiem.

from math import comb
print(comb(302, 20))

Sporo. Wariant, żeby sprawdzić wszystkie kombinacje odpada.

Po paru godzinach kombinowania jak by te kwintyliony ograniczyć (na przykład: suma ściany ma być 2025, więc średnia każdej ściany jest 405, więc trzeba szukać kombinacji z taką średnią) poddałem się i sięgnąłem do Gugla. A ten mi podsunął swoją własną bibliotekę do rozwiązywania zadań pod tytułem OR-Tools, z której pomocą można rozwiązywać najrozmaitszego rodzaju problemy optymalizacyjne. Przez chwilę przemknęła mi przed oczyma czarna tablica zapisana macierzami - opanowanie metody simplex było na studiach powodem kilku nieprzespanych nocy, a zaliczenie przedmiotu uzyskałem w trybie czterech Z - otrząsnąwszy się z niemiłych wspomnień zabrałem się za pisanie kodu:

from ortools.sat.python import cp_model
from sympy import primerange
pierwsze = list(primerange(2, 1999))
sciany = [
    [0, 1, 2, 3, 4], # górna
    [0, 5, 6, 1, 10], [1, 6, 7, 2, 11], [2, 7, 8, 3, 12], [3, 8, 9, 4, 13], [4, 9, 5, 0, 14], # pierścien góra
    [5, 14, 15, 6, 19], [6, 15, 16, 7, 10], [7, 16, 17, 8, 11], [8, 17, 18, 9, 12], [9, 18, 19, 5, 13], # pieścień dół
    [10, 11, 12, 13, 14] # dolna
]
wymagana_suma = 2025

model = cp_model.CpModel()

ile_wierzcholkow = 20
wierzcholki = [model.NewIntVarFromDomain(cp_model.Domain.FromValues(pierwsze), f'v{i}') for i in range(ile_wierzcholkow)]

model.AddAllDifferent(wierzcholki)

for sciana in sciany:
    model.Add(sum(wierzcholki[i] for i in sciana) == wymagana_suma)

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

if stan == cp_model.FEASIBLE or stan == cp_model.OPTIMAL:
    rozwiazanie = [solver.Value(wierzcholki[i]) for i in range(ile_wierzcholkow)]
    print("Rozwiązanie:", rozwiazanie)
else:
    print("Nie znaleziono.")

Gugiel może i jest Wielki i Zły, ale - pewnie właśnie ze względu na swój rozmiar - umie w optymalizację. Kod wypluwa poprawne rozwiązanie po upływie jednej sekundy:

Rozwiązanie: [1033, 401, 461, 127, 3, 131, 353, 503, 797, 241, 107, 307, 137, 857, 617, 811, 251, 167, 683, 113]

Ponieważ kontrola najwyższą formą zaufania, dodałem jeszcze sprawdzenie wyników, żeby nie było:

from ortools.sat.python import cp_model
from sympy import primerange

pierwsze = list(primerange(2, 1999))

sciany = [
    [0, 1, 2, 3, 4],  # Góra
    [0, 5, 6, 1, 10], [1, 6, 7, 2, 11], [2, 7, 8, 3, 12], [3, 8, 9, 4, 13], [4, 9, 5, 0, 14],  # Górny pierścień
    [5, 14, 15, 6, 19], [6, 15, 16, 7, 10], [7, 16, 17, 8, 11], [8, 17, 18, 9, 12], [9, 18, 19, 5, 13],  # Dolny pierścień
    [10, 11, 12, 13, 14]  # Dół
]

wymagana_suma = 2025

model = cp_model.CpModel()
ile_wierzcholkow = 20
wierzcholki = [
    model.NewIntVarFromDomain(cp_model.Domain.FromValues(pierwsze), f'v{i}') for i in range(ile_wierzcholkow)
]

model.AddAllDifferent(wierzcholki)
for sciana in sciany:
    model.Add(sum(wierzcholki[i] for i in sciana) == wymagana_suma)

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

if stan == cp_model.FEASIBLE or stan == cp_model.OPTIMAL:
    rozwiazanie = [solver.Value(wierzcholki[i]) for i in range(ile_wierzcholkow)]
    print("Rozwiązanie:", rozwiazanie)

    print("\nWeryfikacja:")

    unikalne_OK = len(set(rozwiazanie)) == len(rozwiazanie)
    print(f"Unikalność wierzchołków: {'OK' if unikalne_OK else 'BŁĄD'}")

    wszystkie_sciany_OK = True
    for idx, sciana in enumerate(sciany):
        suma_sciany = sum(rozwiazanie[i] for i in sciana)
        szczegoly_sciany = [rozwiazanie[i] for i in sciana]
        if suma_sciany == wymagana_suma:
            print(f"Ściana {idx + 1}: OK (Wartości: {szczegoly_sciany}, Suma: {suma_sciany})")
        else:
            print(f"Ściana {idx + 1}: BŁĄD (Wartości: {szczegoly_sciany}, Suma: {suma_sciany})")
            wszystkie_sciany_OK = False

    if unikalne_OK and wszystkie_sciany_OK:
        print("\nWeryfikacja zakończona sukcesem. Rozwiązanie jest poprawne.")
    else:
        print("\nWeryfikacja nie powiodła się. Rozwiązanie jest błędne.")
else:
    print("Nie znaleziono rozwiązania.")

Wynik:

Rozwiązanie: [541, 431, 227, 263, 563, 53, 401, 829, 683, 59, 599, 137, 23, 457, 809, 193, 3, 373, 887, 569]

Weryfikacja:
Unikalność wierzchołków: OK
Ściana 1: OK (Wartości: [541, 431, 227, 263, 563], Suma: 2025)
Ściana 2: OK (Wartości: [541, 53, 401, 431, 599], Suma: 2025)
Ściana 3: OK (Wartości: [431, 401, 829, 227, 137], Suma: 2025)
Ściana 4: OK (Wartości: [227, 829, 683, 263, 23], Suma: 2025)
Ściana 5: OK (Wartości: [263, 683, 59, 563, 457], Suma: 2025)
Ściana 6: OK (Wartości: [563, 59, 53, 541, 809], Suma: 2025)
Ściana 7: OK (Wartości: [53, 809, 193, 401, 569], Suma: 2025)
Ściana 8: OK (Wartości: [401, 193, 3, 829, 599], Suma: 2025)
Ściana 9: OK (Wartości: [829, 3, 373, 683, 137], Suma: 2025)
Ściana 10: OK (Wartości: [683, 373, 887, 59, 23], Suma: 2025)
Ściana 11: OK (Wartości: [59, 887, 569, 53, 457], Suma: 2025)
Ściana 12: OK (Wartości: [599, 137, 23, 457, 809], Suma: 2025)

Weryfikacja zakończona sukcesem. Rozwiązanie jest poprawne.

Zauważamy przy okazji, że podane rozwiązanie jest inne niż poprzednio, skąd wniosek, że or-tools działa probabilistycznie, a także, że odpowiedź na pytanie dodatkowe brzmi "tak". Pewnie dałoby się jakoś zmusić bibliotekę do znalezienia wszystkich rozwiązań, ale już mi się nie chciało wgryzać.

A jak Wam poszło?

Wyjątkowo skromnie tym razem. Już miałem pisać, że nie nadeszło ani jedno zgłoszenie, ale w ostatniej chwili zgłosił się Rozie, którego odpowiedź (poprawna!) sugeruje, że też używał Pythona:

https://xpil.eu/Cb9hK 📋