finding the longest road in a Settlers of Catan game algorithmically

Question

I'm writing a Settlers of Catan clone for a class. One of the extra credit features is automatically determining which player has the longest road. I've thought about it, and it seems like some slight variation on depth-first search could work, but I'm having trouble figuring out what to do with cycle detection, how to handle the joining of a player's two initial road networks, and a few other minutiae. How could I do this algorithmically?

For those unfamiliar with the game, I'll try to describe the problem concisely and abstractly: I need to find the longest possible path in an undirected cyclic graph.

Thanks!

Answer 1

What I'd do:

1. Pick a vertex with a road
2. Pick at most two roads to follow
3. Follow the the road; backtrack here if it branches, and choose that which was longer
4. If current vertex is in the visited list, backtrack to 3
5. Add the vertex to the visited list, recurse from 3
6. If there is no more road at 3, return the length
7. When you've followed at most 2 roads, add them up, note the length
8. If there were 3 roads at the initial vertex, backtrack to 2.

Sorry for the prolog-ish terminology :)

Answer 2

I would suggest a breadth-first search.

For each player:

• Set a default known maximum of 0

• Pick a starting node. Skip if it has zero or more than one connected neighbors and find all of the player's paths starting from it in a breadth-first manner. The catch: Once a node has been traversed to, it is "deactivated" for the all searches left in that turn. That is, it may no longer be traversed.

  How can this be implemented? Here's one possible breadth-first algorithm that can be used:

  1. If there are no paths from this initial node, or more than one path, mark it deactivated and skip it.
  2. Keep a queue of paths.
  3. Add a path containing only the initial dead-end node to the queue. Deactivate this node.
  4. Pop the first path out of the queue and "explode" it -- that is, find all valid paths that are the the path + 1 more step in a valid direction. By "valid", the next node must be connected to the last one by a road, and it also must be activated.
  5. Deactivate all nodes stepped to during the last step.
  6. If there are no valid "explosions" of the previous path, then compare that length of that path to the known maximum. If greater than it, it is the new maximum.
  7. Add all exploded paths, if any, back into the queue.
  8. Repeat 4-7 until the queue is empty.

• After you do this once, move onto the next activated node and start the process all over again. Stop when all nodes are deactivated.

• The maximum you have now is your longest road length, for the given player.

Note that this is slightly inefficient, but if performance doesn't matter, then this would work :)

IMPORTANT NOTE, thanks to Cameron MacFarland

• Assume all nodes with cities that do not belong to the current player automatically deactivated always.

---

Ruby pseudocode (assumes an get_neighbors function for each node)

def explode n
  exploded = n.get_neighbors             # get all neighbors
  exploded.select! { |i| i.activated? }  # we only want activated ones
  exploded.select! { |i| i.is_connected_to(n) } # we only want road-connected ones
  return exploded
end

max = 0

nodes.each do |n|                 # for each node n
  next if not n.activated?        # skip if node is deactivated
  if explode(n).empty? or explode(n).size > 1
    n.deactivate                  # deactivate and skip if
    next                          # there are no neighbors or
  end                             # more than one

  paths = [ [n] ]                 # start queue

  until paths.empty?              # do this until the queue is empty

    curr_path = paths.pop         # pop a path from the queue
    exploded = explode(curr_path) # get all of the exploded valid paths

    exploded.each { |i| i.deactivate }  # deactivate all of the exploded valid points

    if exploded.empty?                  # if no exploded paths
      max = [max,curr_path.size].max    # this is the end of the road, so compare its length to
                                        # the max
    else
      exploded.each { |i| paths.unshift(curr_path.clone + i) }  
                                        # otherwise, add the new paths to the queue
    end

  end

end

puts max

Answer 3

This should be a rather easy algorithm to implement.

To begin with, separate out the roads into distinct sets, where all the road segments in each set are somehow connected. There's various methods on doing this, but here's one:

1. Pick a random road segment, add it to a set, and mark it
2. Branch out from this segment, ie. follow connected segments in both directions that aren't marked (if they're marked, we've already been here)
3. If found road segment is not already in the set, add it, and mark it
4. Keep going from new segments until you cannot find any more unmarked segments that are connected to those currently in the set
5. If there's unmarked segments left, they're part of a new set, pick a random one and start back at 1 with another set

Note: As per the official Catan Rules, a road can be broken if another play builds a settlement on a joint between two segments. You need to detect this and not branch past the settlement.

Note, in the above, and following, steps, only consider the current players segments. You can ignore those other segments as though they weren't even on the map.

This gives you one or more sets, each containing one or more road segments.

Ok, for each set, do the following:

1. Pick a random road segment in the set that has only one connected road segment out from it (ie. you pick an endpoint)
2. If you can't do that, then the whole set is looping (one or more), so pick a random segment in this case

Now, from the segment you picked, do a recursive branching out depth-first search, keeping track of the length of the current road you've found so far. Always mark road segments as well, and don't branch into segments already marked. This will allow the algorithm to stop when it "eats its own tail".

Whenever you need to backtrack, because there are no more branches, take a note of the current length, and if it is longer than the "previous maximum", store the new length as the maximum.

Do this for all the sets, and you should have your longest road.

Answer 4

You could use Dijkstra and just change the conditions to choose the longest path instead.

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

It's efficient, but won't always find the path that in reality is shortest/longest although it will work most of the times.

Answer 5

A simple polynomial-time depth-first search is unlikely to work, since the problem is NP-hard. You will need something that takes exponential time to get an optimal solution. Since the problem is so small, that should be no problem in practice, though.

Possibly the simplest solution would be dynamic programming: keep a table T[v, l] that stores for each node v and each length l the set of paths that have length l and end in v. Clearly T[v, 1] = {[v]} and you can fill out T[v, l] for l > 1 by collecting all paths from T[w, l-1] where w is a neighbor of v that do not already contain v, and then attaching v. This is similar to Justin L.'s solution, but avoids some duplicate work.