Solution to classic "Blockbuster" problem

Answer 1

A straightforward graphics algorithm called Flood fill can do this.

It can also be done in a simple multi-pass approach - the blockbuster board is so small that I don't think that visiting each cell many times will have any noticeable performance impact at all - so I'd advocate this approach be tried first:

For each player, loop through all the cells; if the cell is owned by the player, and is adjacent on one if it's six sides to a cell 'marked' by this fill routine, then the cell gets marked too. Loop again through all the cells, and again until no cells get marked to the current player. Here's some pseudo-code:

for player in players:
  # those on the starting edge that the player owns get 'marked'
  for cells in cells.start_edge(player):
    if cell.owner = player:
      cell.mark = player
  do:
    count = 0
    for cell in cells:
      if cell.mark == None && cell.owner == player:
        for adjacent in cell.neighbours:
          if adjacent.mark == player
            cell.owner = player
            count += 1
            break
  while count
  for cell in cells.stop_edge(player):
     if cell.mark == player
       player won!!

At this point, if any of the cells on the appropriate side of the board belong to the player, the player reached that side of the board.

Answer 2

Your problem translates to whether two nodes are connected in a graph.

• You can look at the board as a non-directed "graph". Nodes are the cells and they have edges if they are adjacent cells.
• The sides are also nodes in the graph, and those have edges to the cells adjacent to them
• Take the sub-graph of nodes you can use (including top and bottom if checking for that player)
• Check if the top and bottom are connected using DFS