Algorithmus zum Setzen von Zoombinis auf Captain Cajuns Fähre?

Ich habe kürzlich die Neuveröffentlichung von The Logical Journey of the Zoombinis gespielt und versucht, einige Computeralgorithmen zu implementieren, mit denen die verschiedenen Rätsel gelöst werden können. Ich bin nicht sicher, wie ich mich dem Fährenrätsel von Captain Cajun nähern soll.

Für Unbekannte ist ein Zoombini eine Kreatur mit 4 Attributen: Haar, Augen, Nase und Füße. Jedes dieser Attribute hat 5 mögliche Werte; Zum Beispiel können die Füße eines Zoombini Räder, Rollschuhe, Turnschuhe, eine Feder oder ein Propeller sein. Hier ist ein Beispiel für einen Zoombini mit unordentlichem Haar, Brille, grüner Nase und Turnschuhen:

In dem Fährenrätsel besteht die Aufgabe darin, eine Sammlung von 16 Zoombinis auf den 16 Sitzen einer Fähre zusammenzustellen. Die Anordnung muss der Regel entsprechen, dass zwei orthogonal benachbarte Sitze von Zoombinis belegt werden müssen, die mindestens ein Merkmal gemeinsam haben. Wenn zwei Zoombinis unterschiedliche Haare, unterschiedliche Augen, unterschiedliche Nasen und unterschiedliche Füße haben, sitzen sie möglicherweise nicht nebeneinander.

Die Anordnung der Sitze ändert sich je nach Ebene; Konzentrieren wir uns der Vollständigkeit halber auf die Stufe "Sehr schwer", in der die 16 Sitze in einem 4-mal-4-Raster angeordnet sind. Hier ist ein Beispiel, in dem 15 Zoombinis legal sitzen, aber der letzte auf dem Dock stehende Zoombini nicht auf dem letzten freien Platz platziert werden kann, da sie mit dem Zoombini rechts von ihr keine Funktionen teilen würde:

Es gibt 16! ≈ 21 Billionen mögliche Zuordnungen von Zoombinis zu Sitzen. Durchlaufen Sie einfach alle möglichen Aufträge, um festzustellen, ob dies legal ist. Mit welchen Heuristiken könnte ich dieses Problem sinnvoll angehen?

Vielen Dank an @mattecapu für den nützlichen Google-Suchbegriff "Backtracking-Algorithmus". Das gab mir die Denkanstöße, die ich brauchte.

Meine derzeitige Intuition ist, dass es möglicherweise besser ist, die mittleren Sitze - die 4 Nachbarn haben - zuerst auszufüllen und die Eckplätze - die nur 2 Nachbarn haben - zum Schluss aufzubewahren. Also ordne ich die 16 freien Plätze in dieser Reihenfolge in einer verknüpften Liste an:

13   5   6  14

 7   1   2   9

 8   3   4  10

15  11  12  16

Hier ist ein Pseudocode, der die Funktion beschreibt, die ich geschrieben habe. Sie geben ihm eine Liste mit den 16 Zoombinis und einem Zeiger auf den ersten Platz in der verknüpften Liste.

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

Es läuft tatsächlich überraschend schnell! Ich war sehr zufrieden damit.

Ich bin noch nicht ganz überzeugt, dass ich die Liste der Plätze in der bestmöglichen Reihenfolge angeordnet habe. Es gibt insgesamt 24 Einschränkungen für das Problem, und die ideale Reihenfolge beim Ausfüllen der Sitze würde jeder dieser Einschränkungen so früh wie möglich beim Ausfüllen der Sitze gegenüberstehen, sodass die nicht lebensfähigen Zweige maximal schnell abgeschnitten werden.