Algorytm siedzenia Zoombinis na promie kapitana Cajuna?

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:

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?

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.