Algorytm siedzenia Zoombinis na promie kapitana Cajuna?

12

Niedawno grałem ponownie w The Logical Journey of the Zoombinis i próbowałem wdrożyć niektóre algorytmy komputerowe, które mogą rozwiązać różne zagadki. Utknąłem, jak podejść do układanki promowej kapitana Cajuna.

Dla nieznajomych Zoombini jest stworzeniem z 4 atrybutami: włosy, oczy, nos i stopy. Każdy z tych atrybutów ma 5 możliwych wartości; na przykład stopami Zoombini mogą być koła, wrotki, trampki, sprężyna lub śmigło. Oto przykład Zoombini z rozczochranymi włosami, okularami, zielonym nosem i trampkami:

W łamigłówce promowej zadaniem jest zorganizowanie kolekcji 16 Zoombinis na 16 siedzeniach promu. Układ musi być zgodny z zasadą, że Zoombinis, które mają co najmniej jedną cechę, muszą zajmować dowolne dwa sąsiadujące ze sobą prostopadle siedzenia. Jeśli dwa Zoombini mają różne włosy, różne oczy, różne nosy i różne stopy od siebie, mogą nie siedzieć obok siebie.

Rozmieszczenie siedzeń zmienia się w zależności od poziomu; dla konkretności skupmy się na poziomie „Very Hard”, na którym 16 miejsc jest rozmieszczonych w układzie 4 na 4. Oto przykład, w którym 15 Zoombinis zostało legalnie usadzonych, ale ostatecznego Zoombini stojącego na doku nie można umieścić na ostatnim pustym siedzeniu, ponieważ nie dzieliłaby żadnych funkcji z Zoombini po jej prawej stronie:

Przykład prawie ukończonej układanki

Jest 16! ≈ 21 bilionów możliwych przypisań Zoombinis do miejsc. Po prostu przeglądanie każdego możliwego zadania, aby sprawdzić, czy jest to zgodne z prawem, nie będzie praktyczne. Jakich heurystyk mógłbym użyć, aby rozsądnie podejść do tego problemu?

thecommexokid
źródło
2
Przypomina mi to sudoku, a solwery sudoku zwykle implementują pewien rodzaj cofania.
mattecapu,
2
Jeśli jesteś gotów i chcesz przekopać się przez bardziej złożoną literaturę, możesz znaleźć przydatne informacje, wyszukując Subgraph Isomorphism Problem. Problem polega na znalezieniu jednego wykresu na innym wykresie. W twoim przypadku podgraf byłby miejscem siedzącym (krawędzie to przylegania), podczas gdy grafem macierzystym byłby zoombinis, gdzie połączenia byłyby obecnością wspólnej cechy. Zauważ, że generalnie problem jest NP-zupełny i zwykle rozwiązuje się go również przez cofanie, jednak w niektórych szczególnych przypadkach (w przypadku których twój wykres może być bardzo dobrze) możliwe są rozwiązania wielomianowe lub nawet liniowe.
Ordous
to świetny pomysł, uwielbiałem zoombinis jako dziecko - mógłbym zrobić to samo!
AlexFoxGill

Odpowiedzi:

8

Dzięki @mattecapu za przydatny termin wyszukiwawczy Google „algorytm cofania”. To dało mi jedzenie, którego potrzebowałem.

Moją obecną intuicją jest to, że lepiej może być wypełnienie miejsc środkowych - które mają 4 sąsiadów - najpierw, i zachowanie miejsc narożnych - które mają tylko 2 sąsiadów - na koniec. Tak więc układam 16 pustych miejsc w listę połączoną w następującej kolejności:

13   5   6  14

 7   1   2   9

 8   3   4  10

15  11  12  16

Oto pseudokod opisujący funkcję, którą napisałem. Podajesz mu listę zawierającą 16 Zoombinis i wskaźnik do pierwszego miejsca na liście połączonej.

function recursively_assign_seat(zoombini_list, seat):

    if zoombini_list is empty:
        return True

    else:
        for each z in zoombini_list:

            for each n in seat.neighbors:
                if not allowed_as_neighbors(z, n):
                    next z

            seat.occupant ← z
            if recursively_assign_seat(zoombini_list.remove(z), seat.next):
                return True
            else:
                seat.occupant ← None

        return False

Działa zaskakująco szybko! Byłem z tego bardzo zadowolony.

Nie jestem jeszcze do końca przekonany, że ustawiłem listę miejsc w jak najlepszej kolejności. Problem dotyczy 24 całkowitych ograniczeń, a idealna kolejność wypełniania siedzeń stawiałaby czoła każdemu z tych ograniczeń tak wcześnie, jak to możliwe w procesie wypełniania siedzeń, dzięki czemu gałęzie, które nie są wykonalne, zostają maksymalnie przycięte.

thecommexokid
źródło
1
kiedy wypełniasz 8, sąsiadujesz tylko 2, ale możesz wypełniać, 9które sąsiadują zarówno z, jak 7i 3. fajna praca przy rozwiązywaniu tego!
AlexFoxGill
Dokonałem tej edycji; wciąż nie jestem pewien, czy schemat wywrotki bije tylko wypełnianie wiersza po rzędzie. Może zrobię testy czasu.
thecommexokid