title: Finding longest non-repeating path through connected nodes
body: <p>I've been working on this for a couple of days now without success. Basically, I have a bunch of nodes arranged in a 2D matrix. Every node has four neighbors, except for the nodes on the sides and corners of the matrix, which have 3 and 2 neighbors, respectively. Imagine a bunch of square cards laid out side by side in a rectangular area--the project is actually simulating a sort of card/board game.</p>
  
  <p>Each node may or may not be connected to the nodes around it. Each node has a function (get_connections()), that returns the nodes immediately around it that it is connected to (so anywhere from 0 to 4 nodes are returned). Each node also has an "index" property, that contains it's position on the board matrix (eg '1, 4' -> row 1, col 4). What I am trying to do is find the longest non-repeating path of connected nodes given a particular "start" node. </p>
  
  <p>I've uploaded a couple of images that should give a good idea of what I'm trying to do:</p>
  
  <p><a href="https://i.stack.imgur.com/GgUYz.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/GgUYz.jpg" alt="www.necessarygames.com/junk/10-days-problem-01.jpg"></a><br>
  (source: <a href="http://www.necessarygames.com/junk/10-days-problem-01.jpg" rel="nofollow noreferrer">necessarygames.com</a>)  </p>
  
  <p><a href="https://i.stack.imgur.com/JqByc.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/JqByc.jpg" alt="www.necessarygames.com/junk/10-days-problem-02.jpg"></a><br>
  (source: <a href="http://www.necessarygames.com/junk/10-days-problem-02.jpg" rel="nofollow noreferrer">necessarygames.com</a>)  </p>
  
  <p>In both images, the highlighted red cards are supposedly the longest path of connected cards containing the most upper-left card. However, you can see in both images that a couple of cards that should be in the path have been left out (Romania and Maldova in the first image, Greece and Turkey in the second)</p>
  
  <p>Here's the recursive function that I am using currently to find the longest path, given a starting node/card:</p>
  
  <pre><code>def get_longest_trip(self, board, processed_connections = list(), 
                       processed_countries = list()):
      #Append this country to the processed countries list,
      #so we don't re-double over it
      processed_countries.append(self)
      possible_trips = dict()
      if self.get_connections(board):
          for i, card in enumerate(self.get_connections(board)):
              if card not in processed_countries:
                  processed_connections.append((self, card))
                  possible_trips[i] = card.get_longest_trip(board, 
                                                            processed_connections, 
                                                            processed_countries)
          if possible_trips:       
              longest_trip = []
              for i, trip in possible_trips.iteritems(): 
                  trip_length = len(trip)
                  if trip_length &gt; len(longest_trip):
                      longest_trip = trip
              longest_trip.append(self)         
              return longest_trip
          else:
              print
              card_list = []
              card_list.append(self)
              return card_list
      else:
          #If no connections from start_card, just return the start card 
          #as the longest trip
          card_list = []
          card_list.append(board.start_card)
          return card_list
  </code></pre>
  
  <p>The problem here has to do with the processed_countries list: if you look at my first screenshot, you can see that what has happened is that when Ukraine came around, it looked at its two possible choices for longest path (Maldova-Romania, or Turkey, Bulgaria), saw that they were both equal, and chose one indiscriminantly. Now when Hungary comes around, it can't attempt to make a path through Romania (where the longest path would actually be), because Romania has been added to the processed_countries list by Ukraine. </p>
  
  <p>Any help on this is EXTREMELY appreciated. If you can find me a solution to this, recursive or not, I'd be happy to donate some $$ to you.</p>
  
  <p>I've uploaded my full source code (Python 2.6, Pygame 1.9 required) to:</p>
  
  <p><a href="http://www.necessarygames.com/junk/planes_trains.zip" rel="nofollow noreferrer">http://www.necessarygames.com/junk/planes_trains.zip</a></p>
  
  <p>The relevant code is in src/main.py, which is all set to run.</p>