Solving a logic puzzle

I want to share a little algorithm I wrote to solve a puzzle. It's fairly basic computer science, but I feel a bit proud of it because I worked through it methodically, rather than just "hacking it out".

Here's the puzzle:

A man needs to get three items across a river: a goose, a big bag of beans, and a fox. If left alone unsupervised with the beans, the goose will eat the beans. If left alone unsupervised with the goose, the fox will eat the goose. Only the man and up to one other item can fit in the boat. Can the man get across the river with their goose, beans, and fox?

It's a fairly common brain teaser. You might know it, or not. You could probably solve it with some hard thinking and maybe a hint, but let's proceed.

I first saw this puzzle as a youngster, but I came across it again while doing a Brilliant.org lesson on graphs. (I use Brilliant to brush up my logic, maths, and CS basics. It's great.) They talked about how one way to solve this is by framing it as a graph problem.

States

With this graph approach, the nodes of the graph are the different possible states of the characters, while the edges connect states that can be reached from one another. For instance, the initial state is man, goose, beans, fox all on one riverbank. Let's represent this as:

Bank 1: M, B, G, F
Boat: <empty>
Bank 2: <empty>

If the man decides to take the goose with him into the boat, the next state will be:

Bank 1: B, F
Boat: M, G
Bank 2: <empty>

And so on.

Some other possible states:

• An invalid state (it's forbidden for anything to be in the boat without the man):

Bank 1: M, B, G
Boat: F
Bank 2: <empty>

• A valid state, but one that isn't directly connected to our initial state:

Bank 1: M, F
Boat: <empty>
Bank 2: B, F

• The final state we want to end up in:

Bank 1: <empty>
Boat: <empty>
Bank 2: M, B, G, F

If we can represent all the possible states as a graph, then we can solve this puzzle by seeing if there is any path from the initial state to the final state.

First off, is it realistic to represent every possible state? Let's see: there are four characters (M, B, F, G), and three possible slots (bank 1, river, bank 2). Let's try to calculate the number of possible states. To make it easier, we'll ignore the validity rules, and assume each slot can have up to all 4 items. To get the possible states, we can pretend we start out with all 4 items in one slot, then pick items and distribute them across the other slots. There are 4 distinct distributions, which can be arranged in different ways or use different items:

The first possible distribution is 4 items in one slot, and 0 in the other two. There are 3 ways this can happen (slot A has all 4 OR slot B has all 4 OR slot C has all 4). So that's 3 arrangements ([4, 0, 0], [0, 4, 0], [0, 0, 4]).

The next is 3 in one slot, 1 in another, and 0 in the last. Since we have 4 items, there are 4 ways to pick the 1 item that gets moved into the new slot. Also, we can have 6 possible arrangements for the slots ([3, 1, 0], [3, 0, 1], [1, 3, 0], [1, 0, 3], [0, 1, 3], [0, 3, 1]). So we have 4 * 6 = 24 possibilities.

The next distribution is [2, 2, 0]. Again, since we have 4 items, there are 6 ways to pick the 2 items that get moved into the new slot. Also, we can have 3 possible arrangements for the slots ([2, 2, 0], [2, 0, 2], [0, 2, 2]). So we have 6 * 3 = 18 possibilities.

The final distribution is [2, 1, 1]. Again, there are 6 ways to pick the 2 items that get moved into the new slot, and we can have 3 possible arrangements for the slots ([2, 1, 1], [1, 2, 1], [1, 1, 2]). However, each of these arrangements can have 2 possibilities: supposing the two items we're moving are the man and the goose. For the arrangement [2, 1, 1], we could put either man or goose first, two different arrangements. (In the previous distribution, [2, 2, 0], it's only one arrangement, because both items are in the same slot.). So we actually have 6 * 3 * 2 = 36 possibilities.

Altogether, this gives 3 + 24 + 18 + 36 = 81 possibilities.

That's good! 81 is a very small number for a computer. We can easily store 81 states in memory and traverse them inside a second. Also, if we filter for valid states, it will probably be much less than 81.

Okay, implementation. I'll try to go through this in the order I implemented it.

Representation

I started with an empty Graph class and a State struct, to represent the state of the game. This is where OOP shines; using custom classes for states and data structures instead of just hashes and arrays is a great form of abstraction that makes it easy to follow.

class Graph
end

State = Struct.new(:bank_1, :boat, :bank_2)

These classes are empty because I was using a top-down approach—implementing the details based on how the classes end up being used. So the next thing I did was write some (not working) code for how I expected to use them. First, initialize:

initial_state = State[
  bank_1: Set[:man, :goose, :beans, :fox], boat: Set[], bank_2: Set[]
]
graph = Graph.new

Next, generating all possible valid states and populating the graph with them. My desired approach here was to do it in "layers":

• first layer: start at the root (initial_state) and generate the next states. These will form the second layer.
• second layer: for each of the previously generated states, generates the next states. They will be the third layer.

And so on. For each set of states, find all next possible states, then repeat for this set.

Finally, we have to make sure this iteration ends, by keeping track of all states we've previously visited, and don't traverse them if they come up again (otherwise we'll keep going in circles). Eventually, we'll get to a point where there are no unseen valid states left, and that's where we end.

I believe this is a case of "breadth-first traversal".

visited_states = Set[initial_state]
layer_to_traverse = [initial_state]

until layer_to_traverse.empty?
  layer_to_traverse = layer_to_traverse.flat_map do |current_state|
    current_state.possible_transitions.map do |next_state|
      next nil if next_state.invalid?

      graph.link(current_state, next_state)

      next nil if visited_states.include? next_state

      visited_states << next_state
      next_state
    end.compact
  end
end

Nice. (Obviously, this wasn't the exact API I came up with at first, but it's close.)

This looks alright, so what's left is to implement the methods being called: possible_transitions, invalid?. and link.

I started with the State#invalid? method, because it was the easiest (just translate the puzzle constraints):

State = Struct.new(:bank_1, :boat, :bank_2) do
  def valid?
    # Boat must be empty or have man + one other thing
    return false if boat.size > 2
    return false if !boat.empty? && !boat.include?(:man)

    # (fox + goose) AND (goose + beans) are not allowed anywhere without man
    [:bank_1, :bank_2].each do |position|
      location = self[position]
      return false if location.include?(:goose) &&
        location.include?(:fox) && !location.include?(:man)
      return false if location.include?(:beans) &&
        location.include?(:goose) && !location.include?(:man)
    end
  end

  def invalid? = !valid?
end

Then I skipped over to Graph#link. All this method does is keep a record that one state can be reached from the other. We can do this with a connections hash:

class Graph
  def initialize
    @connections = Hash.new { |h, k| h[k] = Set[] } # syntax sugar to make unset elements return an empty set instead of null.
  end

  def link(a, b)
    @connections[a] << b
    @connections[b] << a
  end
end

And now, to State#possible_transitions. This was tricky at first, but I realized I could just manually check the current positions of items and build up the next state manually. Remember that the man is the main character; nothing else can move without him, so we just need to compute his possible movements.

State = Struct.new(:bank_1, :boat, :bank_2) do
  # ...

  def possible_transitions
    transitions = []

    if bank_1.include?(:man)
      # If he was on a bank, only place he can go is the boat
      other_items = bank_1 - Set[:man]
      # If the man went to the boat alone
      transitions << State[
        bank_1: other_items, boat: Set[:man], bank_2: bank_2.dup
      ]
      # If he took someone with him
      other_items.each do |item|
        transitions << State[
          bank_1: other_items - Set[item], boat: Set[:man, item], bank_2: bank_2.dup
        ]
      end
    elsif bank_2.include?(:man)
      other_items = bank_2 - Set[:man]
      transitions << State[
        bank_1: bank_1.dup, boat: Set[:man], bank_2: other_items
      ]
      other_items.each do |item|
        transitions << State[
          bank_1: bank_1.dup, boat: Set[:man, item], bank_2: other_items - Set[item]
        ]
      end
    else # man was on boat, crosses to one of the banks
        transitions << State[
          bank_1: bank_1 + boat, boat: Set[], bank_2: bank_2.dup
        ]
        transitions << State[
          bank_1: bank_1.dup, boat: Set[], bank_2: bank_2 + boat
        ]
    end

    transitions
  end
end

There's probably a cleaner way to do this, but eh.

That's somewhat surprisingly all that was needed to generate the graph. But of course, I had to verify this visually, so I added custom to-string methods on the State and Graph to produce cleaner output.

State = Struct.new(:bank_1, :boat, :bank_2) do
  # ...

  def to_s
    print = ->(set) { set.to_a.map { _1.to_s[0].upcase }.sort.join(',') }
    "{bank_1=#{print.(bank_1)}, boat=#{print.(boat)}, bank_2=#{print.(bank_2)}}"
  end

  alias inspect to_s
end

For the graph class, it was a bit tough to do printing on the console based on the connections hash, so I added another set to just keep track of the edges and print based on that.

class Graph
  def initialize
    @edges = Set[]
    @connections = Hash.new { |h, k| h[k] = Set[] }
  end

  def link(a, b)
    @edges << Set[a, b]
    @connections[a] << b
    @connections[b] << a
  end

  def inspect
    @edges.map do |a_b|
      a, b = a_b.to_a
      "#{a} ----> #{b}"
    end.join("\n")
  end
end

Okay, cool. With this, I could print the generated graph:

p graph

{bank_1=B,F,G,M, boat=, bank_2=} ----> {bank_1=B,F, boat=G,M, bank_2=}
{bank_1=B,F, boat=G,M, bank_2=} ----> {bank_1=B,F, boat=, bank_2=G,M}
{bank_1=B,F, boat=, bank_2=G,M} ----> {bank_1=B,F, boat=M, bank_2=G}
{bank_1=B,F, boat=M, bank_2=G} ----> {bank_1=B,F,M, boat=, bank_2=G}
{bank_1=B,F,M, boat=, bank_2=G} ----> {bank_1=F, boat=B,M, bank_2=G}
{bank_1=B,F,M, boat=, bank_2=G} ----> {bank_1=B, boat=F,M, bank_2=G}
{bank_1=F, boat=B,M, bank_2=G} ----> {bank_1=F, boat=, bank_2=B,G,M}
{bank_1=B, boat=F,M, bank_2=G} ----> {bank_1=B, boat=, bank_2=F,G,M}
{bank_1=F, boat=, bank_2=B,G,M} ----> {bank_1=F, boat=G,M, bank_2=B}
{bank_1=B, boat=, bank_2=F,G,M} ----> {bank_1=B, boat=G,M, bank_2=F}
{bank_1=F, boat=G,M, bank_2=B} ----> {bank_1=F,G,M, boat=, bank_2=B}
{bank_1=B, boat=G,M, bank_2=F} ----> {bank_1=B,G,M, boat=, bank_2=F}
{bank_1=F,G,M, boat=, bank_2=B} ----> {bank_1=G, boat=F,M, bank_2=B}
{bank_1=B,G,M, boat=, bank_2=F} ----> {bank_1=G, boat=B,M, bank_2=F}
{bank_1=G, boat=F,M, bank_2=B} ----> {bank_1=G, boat=, bank_2=B,F,M}
{bank_1=G, boat=B,M, bank_2=F} ----> {bank_1=G, boat=, bank_2=B,F,M}
{bank_1=G, boat=, bank_2=B,F,M} ----> {bank_1=G, boat=M, bank_2=B,F}
{bank_1=G, boat=M, bank_2=B,F} ----> {bank_1=G,M, boat=, bank_2=B,F}
{bank_1=G,M, boat=, bank_2=B,F} ----> {bank_1=, boat=G,M, bank_2=B,F}
{bank_1=, boat=G,M, bank_2=B,F} ----> {bank_1=, boat=, bank_2=B,F,G,M}

It's not the best view of a graph, but this game's graph is a relatively small one, so it's okay. The important thing is that we can see the different ways the man and his things can move across riverbanks.

Just to check, let's see how many valid states are there:

p visited_states.size # => 20

Pathfinding

Okay, now, we've got the representation down. Now, over to the solution part. Here, from the outside, we simply ask the graph to find us a path from the initial state to the desired end state (all four on the other bank). So something like this:

graph.find_path(
  from: initial_state,
  to: State[bank_1: Set[], boat: Set[], bank_2: Set[:man, :fox, :goose, :beans]]
)

Implementing:

class Graph
  # ...

  def find_path(from:, to:, traversed: Set[from])
    @connections[from].
      reject { |node| traversed.include?(node) }.
      each do |node|
      return [to] if node == to

      traversed << node
      path = find_path(from: node, to:, traversed:)

      return [node] + path if path
    end

    nil
  end
end

This find_path implementation uses a recursive approach, which you might already be familiar with. The algorithm is basically:

• Look at all the nodes directly connected to the current from node.
• Pick one of those nodes and try to find a path to the desired end (to).
• If there's no path to the end, come back and try the next neighbour
• If you do find a path, return it.

The recursion here lies in the from. We keep the to constant, but call find_path again with the new from. So, essentially:

• find_path from: A, to: Z calls
• find_path from: B, to: Z,, which calls
• find_path from: C, to: Z, and so on.

I love how elegant recursion can be, although sometimes it takes my brain a few minutes to realise what's going on Also, this is a depth-first search, since we go all the way down one node to look for the destination, before checking its neighbour.

So that's all. I'll just make a little adjustment to the caller:

path = [initial_state] + graph.find_path(
  from: initial_state,
  to: State[bank_1: Set[], boat: Set[], bank_2: Set[:man, :fox, :goose, :beans]]
)

puts path.join("\n-->")

And here we go!

{bank_1=B,F,G,M, boat=, bank_2=}
-->{bank_1=B,F, boat=G,M, bank_2=}
-->{bank_1=B,F, boat=, bank_2=G,M}
-->{bank_1=B,F, boat=M, bank_2=G}
-->{bank_1=B,F,M, boat=, bank_2=G}
-->{bank_1=F, boat=B,M, bank_2=G}
-->{bank_1=F, boat=, bank_2=B,G,M}
-->{bank_1=F, boat=G,M, bank_2=B}
-->{bank_1=F,G,M, boat=, bank_2=B}
-->{bank_1=G, boat=F,M, bank_2=B}
-->{bank_1=G, boat=, bank_2=B,F,M}
-->{bank_1=G, boat=M, bank_2=B,F}
-->{bank_1=G,M, boat=, bank_2=B,F}
-->{bank_1=, boat=G,M, bank_2=B,F}
-->{bank_1=, boat=, bank_2=B,F,G,M}

Eureka!

You can run it through in your head and verify that it's indeed the correct solution (it is). The man takes the goose first, leaving the fox and beans behind (since fox won't eat beans), comes back and brings the beans too, then takes the goose back to the original riverbank, then takes the fox over, and then comes back for the goose one final time.

Here's the full code.

So...that was pretty cool (I lie, it was exciting). Some observations (from myself and Brilliant):

• You can solve some other puzzles and games like this.
• But should you? Chess, for instance, has millions of possible states, so there's no way you'd be able to efficiently generate or traverse them all.
• This is of course not the only way of solving this. I can't think of any others right now, beyond the old hackin' it, but it'd be fun to try.
• There's no guarantee that this algorithm gives the optimal solution, btw. find_path simply looked for the first path that led to our destination, and in this case, that happened to be the only one.