# Detecting a sequence of nodes in a grid

Given the image below, I need to detect the most optimal sequence on the board (the green line). The blue/red lines represent possible, but not the best moves.

Here are the rules:

1. You can move to any tile that is the same, and is your neighbor (diagonal is valid)
2. Once you have visited a tile, you can't visit it again.

I have thought about looping through each node, and looking at its neighbors, then recursively going through. Once I find a possible move I can put it into a structure. Once all possible moves are found I just pick the move with the highest count of node. It becomes more difficult when a node has more than one neighbor that matches.

So, is there some algorithm that I can use? I was thinking some sort of flood fill, but that doesn't meet rules #2.

As requested, here is a video of similar gameplay. http://youtube.com/watch?v=eumnCTG0AE8

• It might be important to note that the 3 swords/gold are possible matches, but I just didn't include them in the image. – Joe Aug 13 '11 at 5:11
• Why are the 3 swords/gold possible matches? Do you want to find all paths that consist of at least 3 items? – bummzack Aug 13 '11 at 9:00
• yeah, that is the idea. – Joe Aug 13 '11 at 16:18

## 1 Answer

You can consider each group of linked identical symbols (and by linked I mean you can travel from one symbol to another) a separate graph. For each such graph apply a Depth First Search (DFS) starting from each node in the graph that isn't already part of the longest path for that graph. Every time you reach a dead end while applying a DFS, check to see if the path you've just traversed is longer than the global maximum that you've found so far. If it is, store it as the new longest path.

You'll notice that in the previous paragraph I mentioned applying a DFS multiple times for each graph. A single DFS ran on a graph wouldn't be enough. Consider this particular case:

    1
1 1 1
1
1
1
1


If by chance you would first run a DFS on this graph in the topmost node, you would discover the longest possible path as being the vertical line, but that wouldn't be correct. This would happen every time you start the DFS algorithm in a node that's somewhere inside the resulting path or is not part of it at all. What you need to do in this particular example is also start a DFS algorithm from the left-most node in the second line. That will find the correct path. Generally speaking, you'll need to run DFS algorithms in each node that isn't currently part of the longest path for that graph, as stated above.

The absolute worse case scenario for this algorithm would be a board filled or mostly filled with a single symbol type, however that's unlikely to happen in the game. Also, be careful how you store the longest paths for each graph. If you don't optimize this bit, you might be better off just calling a DFS for each node on the stage. Assuming that you don't work with very large boards and that speed isn't that big of an issue, this solution should be fast enough.

Technically speaking, by breaking down your board into separate graphs you end up with multiple "Longest path problem"s. As we can see from your example, you can have cycles in your graph (for example, having all of the symbols on the outside of the stage of the same type), which means that in this particular problem you need to find the longest path in several cyclic undirected graphs, which can't be done in polynomial time.

If you find that this is too slow, see this answer on StackOverflow for more details on how to optimize the individual "Longest Path Problems".