I agree with Sandman. There's really no reason to keep a list of all chains. When a tile is placed, the only possible winning chain must contain that new tile. Otherwise the game would have been won already. So, you only need to build the chain around the more recently placed tile, and check that chain each turn. Anything not part of this chain is completely irrelevant to the calculation, so why save it and check it?

http://www.cs.princeton.edu/courses/archive/spr07/cos226/lectures/01union-find.pdf

Here are some slides with a couple algorithms that would work. As shown in slide 23, Weighted Quick-Union would probably be the best choice, handling both the creation of new connections and the testing of whether nodes are connected in lg N time.

Some more details are available here: http://algs4.cs.princeton.edu/15uf/, and a Java implementation of Weighted Quick-Union can be found on that page under Creative Problems. (direct link http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionUF.java.html)

If you were choose this approach (it might be overkill?) then some tips:

• You would use 2 weighted quick-union structures, one for each player.
  
• Instead of needing to check the connectivity of every node on the left with every node on the right, you could create 2 "virtual" nodes - one on each side. You connect every node on the left to the first virtual node, and every node on the right to the second virtual node. Then you can quickly check if the player has won by checking if the 2 virtual nodes are connected.
  

Sounds like it should work, but it also sounds a bit overcomplicated, with lots of needless hunting around in lists.

You don't need to maintain giant lists of lists. If you are familiar with recursion you can write a pretty simple function to do the test.

Ropey Pseudocode:


bool ConnectsToEdge(Edge edgeToCheck, Hex currentHex, Player player)
{
for each neighbourHex
{
if(neighbourHex.IsOwnedByPlayer(player))
{
if neighbourHex.IsEdgeHex(edgeToCheck)
return true
else
if ConnectsToEdge(edgeToCheck, neighbourHex, player)
return true
}
}
return false
}


I tried to implement it and it results in an infinite loop...maybe I'm misunderstanding the psuedo-code somewhere?


private boolean checkHexConnectsToEdge(int hexEdgeIndexToCheck, int currentHexIndex)
{
killCounter++;

int[] adjHexSpaces = playHexes[currentHexIndex].getAdjacentHexes();
for(int counter = 0; counter < adjHexSpaces.length; counter++)
{
if(playHexes[adjHexSpaces[counter]].isOccupiedByPlayer1())
{
if(playHexes[adjHexSpaces[counter]].getHexNumber() == hexEdgeIndexToCheck)
return true;
else
{
if(checkHexConnectsToEdge(hexEdgeIndexToCheck, playHexes[adjHexSpaces[counter]].getHexNumber()))
return true;
}
}
}
return false;
}


I have also attached some of the code. I hate asking but if you could take time to look I would appreciate it. In the code all I'm trying to check is if the chain reaches array position 21 which is a hex on the far right side (for player 1). I'm afraid there is something small I am missing.[attachment=11168:nodesApplet.txt]