Improving time complexity for Count the Islands DFS

Question

For game AI development, I am currently using a slight modification on the DFS "count the islands" problem (specification below) as a solution to the One Hive Rule for the game of Hive. This may not be the ideal solution so I am open to any other ideas if you note DFS is not the best approach. Thank you.

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

My version utilises a 2D map (matrix) which represents a hexagonal board for the game.

The differences are:

• My implementation uses hexagons so each cell has 6 neighbours, not 8
• Blanks represent 0s and anything else are 1s
• My implementation purposely stops if/when it finds more than one island/hive

My question is can the code be improved with regards to time complexity?

from insects import Blank


class HiveGraph:
    def __init__(self, board):
        self.row = board.height
        self.col = board.width
        self.visited = [[False for _ in range(self.col)] for _ in range(self.row)]
        self.graph = board.board

    # A function to check if a given hexagon can be included in DFS
    def is_safe(self, row, col):
        # row number is in range,
        # column number is in range,
        # and hexagon is Blank and not yet visited
        return (0 <= row < self.row and
                0 <= col < self.col and
                not self.visited[row][col] and
                type(self.graph[row][col]) is not Blank)

    # DFS for a 2D matrix. It only considers
    # the 6 neighbours as adjacent pieces
    def dfs(self, row, col):
        print(row, col)
        # These arrays are used to get row and
        # column numbers of 6 neighbours
        # of a given hexagon
        if col % 2 == 1:
            row_nbr = [-1,  0, 0,  1, 1, 1]
            col_nbr = [ 0, -1, 1, -1, 0, 1]
        else:
            row_nbr = [-1, -1, -1,  0, 0, 1]
            col_nbr = [-1,  0,  1, -1, 1, 0]

        # Mark this hexagon as visited
        self.visited[row][col] = True

        # Recur for all connected neighbours
        for k in range(6):
            if self.is_safe(row + row_nbr[k], col + col_nbr[k]):
                self.dfs(row + row_nbr[k], col + col_nbr[k])

    def one_hive(self):
        # Initialize count as 0 and traverse
        # through the all hexagons of given matrix
        count = 0
        for row in range(self.row):
            for col in range(self.col):
                # If a hexagon not Blank and is not visited yet,
                # then new hive found
                if not self.visited[row][col] and type(self.graph[row][col]) is not Blank:
                    # Visit all hexagons in this hive
                    # and increment hive count
                    count += 1
                    if count > 1:
                        return False
                    self.dfs(row, col)
        return True

Refer to this image for row, col matrix values for the layout of hexagons:

Answer 1

Given there are only 22-28 tiles in a Hive game, the time complexity of the check probably doesn't matter much. Nevertheless, a modified scanline fill algorithm might be faster than a DFS. This answer explains the algorithm fairly well. In this use case it might be easier to scan down the columns instead of across the rows.

From the rules of the Hive game, it seems the "one hive rule" would need to be checked when a tile is put down on the playing field and when it is picked up from the playing field (e.g., to move it). When a tile is put down, it is sufficient to make sure it touches another tile (beside or on top).

When a tile is picked up, it is necessary to make sure it's former neighbor tiles are still connected via another path. This may be trivial such as when the neighbors are adjacent, or may require searching for a path using a DFS, BFS, spanning tree, or fill/paint algorithm.

In any case, the AI should know which tile is being moved, so it shouldn't be necessary to scan the hex grid. Just start from one of the tiles neighbors.