Un algorithme pour placer Zoombinis sur le ferry du capitaine Cajun?

J'ai joué récemment la réédition de The Logical Journey of the Zoombinis et j'ai essayé d'implémenter des algorithmes informatiques capables de résoudre les différents puzzles. Je suis coincé sur la façon d'aborder le puzzle du ferry du capitaine Cajun.

Pour ceux qui ne le connaissent pas, un Zoombini est une créature avec 4 attributs: cheveux, yeux, nez et pieds. Chacun de ces attributs a 5 valeurs possibles; par exemple, les pieds d'un Zoombini peuvent être des roues, des patins à roulettes, des baskets, un ressort ou une hélice. Voici un exemple d'un Zoombini avec des cheveux en désordre, des lunettes, un nez vert et des baskets:

Dans le puzzle du ferry, la tâche consiste à organiser une collection de 16 Zoombinis sur les 16 sièges d'un ferry. L'arrangement doit respecter la règle selon laquelle deux sièges voisins orthogonalement doivent être occupés par des Zoombinis qui partagent au moins une caractéristique. Si deux Zoombinis ont des cheveux différents, des yeux différents, un nez différent et des pieds différents l'un de l'autre, ils ne peuvent pas s'asseoir l'un à côté de l'autre.

La disposition des sièges change par niveau; pour le concret, concentrons-nous sur le niveau "Très difficile", dans lequel les 16 sièges sont disposés dans une grille de 4 par 4. Voici un exemple où 15 Zoombinis ont été légalement assis, mais le dernier Zoombini debout sur le quai ne peut pas être placé sur le dernier siège vide, car elle ne partagerait aucune fonction avec le Zoombini à sa droite:

Il y en a 16! ≈ 21 billions d'affectations possibles de Zoombinis aux sièges. Donc, simplement parcourir toutes les missions possibles pour voir si c'est légal ne sera pas pratique. Quelles sont les heuristiques que je pourrais utiliser pour aborder ce problème de manière sensible?

Merci à @mattecapu pour le terme de recherche Google utile "d'algorithme de retour en arrière". Cela m'a donné matière à réflexion dont j'avais besoin.

Mon intuition actuelle est qu'il serait peut-être préférable de remplir d'abord les sièges centraux - qui ont 4 voisins - et de conserver les sièges d'angle - qui n'ont que 2 voisins - pour la fin. J'organise donc les 16 sièges vides dans une liste chaînée dans cet ordre:

13   5   6  14

 7   1   2   9

 8   3   4  10

15  11  12  16

Voici un pseudocode qui décrit la fonction que j'ai fini par écrire. Vous lui donnez une liste contenant les 16 Zoombinis et un pointeur vers le premier siège de la liste chaînée.

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

Il fonctionne en fait étonnamment rapidement! J'en ai été très content.

Je ne suis pas encore totalement convaincu d'avoir organisé la liste des sièges dans le meilleur ordre possible. Il y a 24 contraintes totales sur le problème, et l'ordre idéal de remplissage des sièges confronterait chacune de ces contraintes le plus tôt possible dans le processus de remplissage des sièges, de sorte que les branches qui ne sont pas viables soient élaguées au maximum rapidement.