Algoritma untuk tempat duduk Zoombinis di kapal feri Kapten Cajun?

Saya telah memainkan rerelease The Logical Journey of the Zoombinis baru-baru ini, dan mencoba menerapkan beberapa algoritma komputer yang dapat menyelesaikan berbagai teka-teki. Saya terjebak pada cara mendekati teka-teki kapal feri Kapten Cajun.

Bagi mereka yang tidak terbiasa, Zoombini adalah makhluk dengan 4 atribut: rambut, mata, hidung, dan kaki. Masing-masing atribut tersebut memiliki 5 nilai yang memungkinkan; misalnya, kaki Zoombini dapat berupa roda, sepatu roda, sepatu kets, pegas, atau baling-baling. Berikut adalah contoh Zoombini dengan rambut berantakan, kacamata, hidung hijau, dan sepatu kets:

Dalam puzzle kapal feri, tugasnya adalah mengatur koleksi 16 Zoombinis di 16 kursi kapal feri. Pengaturan ini harus mematuhi aturan bahwa setiap dua kursi yang bertetanggaan secara orthogonal harus ditempati oleh Zoombinis yang memiliki setidaknya satu fitur. Jika dua Zoombinis memiliki rambut yang berbeda, mata berbeda, hidung berbeda, dan kaki berbeda satu sama lain, mereka mungkin tidak duduk bersebelahan.

Susunan kursi berubah berdasarkan level; untuk konkret, mari kita fokus pada level "Sangat Keras", di mana 16 kursi diatur dalam kotak 4-oleh-4. Berikut adalah contoh di mana 15 Zoombini telah duduk secara legal, tetapi Zoombini akhir yang berdiri di dermaga tidak dapat ditempatkan di kursi kosong terakhir, karena ia tidak akan berbagi fitur dengan Zoombini di sebelah kanannya:

Ada 16! ≈ 21 triliun kemungkinan tugas Zoombinis untuk kursi. Jadi hanya menjalankan setiap tugas yang mungkin untuk melihat apakah itu legal tidak akan praktis. Apa beberapa heuristik yang mungkin saya terapkan untuk mendekati masalah ini secara masuk akal?

Terima kasih kepada @mattecapu untuk istilah pencarian Google yang berguna dari "algoritma backtracking". Itu memberi saya makanan untuk berpikir yang saya butuhkan.

Intuisi saya saat ini adalah bahwa mungkin lebih baik mengisi kursi tengah - yang memiliki 4 tetangga - pertama, dan menyimpan kursi sudut - yang hanya memiliki 2 tetangga - untuk yang terakhir. Jadi saya mengatur 16 kursi kosong menjadi daftar terkait dalam urutan ini:

13   5   6  14

 7   1   2   9

 8   3   4  10

15  11  12  16

Inilah beberapa pseudocode yang menjelaskan fungsi yang akhirnya saya tulis. Anda memberinya daftar yang berisi 16 Zoombinis dan penunjuk ke kursi pertama dalam daftar tertaut.

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

Ini sebenarnya berjalan sangat cepat! Saya sangat senang dengan itu.

Saya belum sepenuhnya yakin bahwa saya telah mengatur daftar kursi dengan urutan sebaik mungkin. Ada 24 kendala total pada masalah ini, dan urutan pengisian kursi yang ideal akan menghadapi setiap kendala tersebut sedini mungkin dalam proses pengisian kursi, sehingga cabang-cabang yang tidak layak dapat dipangkas maksimal secara cepat.