# Algorithm for seating Zoombinis on Captain Cajun's ferryboat?

I've been playing the rerelease of The Logical Journey of the Zoombinis recently, and trying to implement some computer algorithms that can solve the various puzzles. I'm stuck on how to approach the Captain Cajun's ferryboat puzzle.

For those unfamiliar, a Zoombini is a creature with 4 attributes: hair, eyes, nose, and feet. Each of those attributes has 5 possible values; for instance, a Zoombini's feet can be wheels, roller skates, sneakers, a spring, or a propeller. Here's an example of a Zoombini with messy hair, glasses, a green nose, and sneakers:

In the ferryboat puzzle, the task is to arrange a collection of 16 Zoombinis on the 16 seats of a ferry boat. The arrangement has to obey the rule that any two orthogonally neighboring seats must be occupied by Zoombinis that share at least one feature. If two Zoombinis have different hair, different eyes, different noses, and different feet from one another, they may not sit next to each other.

The arrangement of the seats changes by level; for concreteness, let's focus on the "Very Hard" level, in which the 16 seats are arranged in a 4-by-4 grid. Here is an example where 15 Zoombinis have been legally seated, but the final Zoombini standing on the dock cannot be placed on the last empty seat, because she would share no features with the Zoombini to her right:

There are 16! ≈ 21 trillion possible assignments of Zoombinis to seats. So simply running through every possible assignment to see if it's legal isn't going to be practical. What are some heuristics I might employ to approach this problem sensibly?

• It reminds me of sudoku, and sudoku solvers usually implement some sort of backtracking. Jul 23, 2016 at 7:24
• If you are ready and willing to dig through some more complex literature, then you can find useful info by searching for `Subgraph Isomorphism Problem`. The problem is to find one graph in another graph. In your case the subgraph would be the seating (edges are adjacencies), while the parent graph would be the zoombinis, where the connections would be the presence of a shared trait. Note that in general the problem is NP-complete and usually is done by backtracking as well, however for some special cases (of which your graph may very well be), polynomial or even linear solutions are possible. Jul 28, 2016 at 16:02
• this is a great idea, I loved zoombinis as a kid - I might just do the same thing!
– Alex
Jul 28, 2016 at 16:25

Thanks to @mattecapu for the useful Google search term of "backtracking algorithm". That gave me the food for thought I needed.

My current intuition is that it might be better to fill in the center seats—which have 4 neighbors—first, and save the corner seats—which have only 2 neighbors—for last. So I arrange the 16 empty seats into a linked-list in this order:

``````13   5   6  14

7   1   2   9

8   3   4  10

15  11  12  16
``````

Here's some pseudocode that describes the function that I wound up writing. You feed it a list containing the 16 Zoombinis and a pointer to the first seat in the linked-list.

``````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
``````

It actually runs surprisingly quickly! I was very pleased with it.

I am not totally convinced yet that I have arranged the list of seats in the best possible order. There are 24 total constraints on the problem, and the ideal order of seat-filling would confront each of those constraints as early as possible in the seat-filling process, so that the branches that aren't viable get pruned off maximally quickly.

• when you fill `8` you're only adjacent to `2`, but you could be filling `9` which is adjacent to both `7` and `3`. nice work solving it though!
– Alex
Jul 28, 2016 at 13:29
• Made that edit; still not sure whether the inside-out scheme beats just filling in row-by-row, though. Maybe I'll do some timing tests. Jul 28, 2016 at 15:28