Finding surrounded groups in 2D list

Question

I wanted to de-rust my python abilities with a little project but I'm running into issues. For context, I'm trying to make a game of go in tkinter. I'm using a 2D list to represent the board and then displaying it. Black stones are represented as 1, white stone as 2 and 0 are empty space (example below). The list :

board = [[0, 0, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 2, 2, 0, 2, 0, 0, 0],
         [0, 2, 2, 1, 2, 0, 0, 0, 0],
         [2, 2, 1, 1, 1, 2, 2, 2, 0],
         [1, 1, 1, 0, 1, 1, 1, 2, 2],
         [0, 0, 0, 0, 0, 0, 2, 1, 1],
         [0, 0, 0, 0, 1, 0, 1, 0, 0],
         [0, 1, 0, 0, 0, 0, 0, 0, 0],
         [0, 0, 0, 0, 0, 0, 0, 0, 0]]

Would represent this board

The problem is, I don't know how to deal with surrounded/dead groups. For example with this board:

[[0, 2, 2, 0, 0],
 [2, 1, 1, 2, 0],
 [2, 2, 1, 2, 0],
 [0, 0, 2, 0, 0],
 [0, 0, 0, 0, 0]]

I want to get:

[[0, 2, 2, 0, 0],
 [2, 0, 0, 2, 0],
 [2, 2, 0, 2, 0],
 [0, 0, 2, 0, 0],
 [0, 0, 0, 0, 0]]

And same if 1 replaces 2 and vise versa. I thought of doing a flood fill from a random empty point to see which groups would remain, but a line of alive stones could stop the flood like so (representing flooded part with 9):

[[0, 0, 2, 9, 9],
 [0, 1, 1, 2, 9],
 [2, 2, 1, 2, 9],
 [9, 9, 2, 9, 9],
 [9, 9, 9, 9, 9]]

And we are left not knowing anything more. An idea I had would be to make the flood affect every value and running it might leave only the closed groups. It would only affect the first "layer" except if the group is open (I don't know if this makes sense). I tried fiddling with a version of this fill I had on my computer but can't get it to work. I don't have any other ideas on how to tackle this problem. Using the solution for this post leaves a bug with this board for example:

[[0, 1, 0],
 [1, 2, 1],
 [0, 2, 0]]

Gives:

[[0, 1, 0],
 [1, 3, 1],
 [0, 2, 0]]

But the middle stone is not dead...

Any help would be very welcomed !

score 0 · Accepted Answer · answered Aug 20 '23 at 23:13

One way of achieving your goal is:

from typing import List, Set, Tuple

def is_valid_coord(coord: Tuple[int, int], size: int) -> bool:
    x, y = coord
    return 0 <= x < size and 0 <= y < size

def get_neighbors(coord: Tuple[int, int]) -> List[Tuple[int, int]]:
    x, y = coord
    return [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]

def find_group(coord: Tuple[int, int], board: List[List[int]], visited: Set[Tuple[int, int]]) -> List[Tuple[int, int]]:
    group = []
    color = board[coord[0]][coord[1]]
    stack = [coord]

    while stack:
        current = stack.pop()
        if current not in visited:
            visited.add(current)
            group.append(current)
            neighbors = get_neighbors(current)
            for neighbor in neighbors:
                if is_valid_coord(neighbor, len(board)) and board[neighbor[0]][neighbor[1]] == color:
                    stack.append(neighbor)

    return group

def remove_dead_groups(board: List[List[int]]) -> List[List[int]]:
    size = len(board)
    visited = set()
    new_board = [[stone for stone in row] for row in board]

    for x in range(size):
        for y in range(size):
            coord = (x, y)
            if board[x][y] != 0 and coord not in visited:
                group = find_group(coord, board, visited)
                liberties = set()

                for stone_coord in group:
                    neighbors = get_neighbors(stone_coord)
                    for neighbor in neighbors:
                        if is_valid_coord(neighbor, size) and board[neighbor[0]][neighbor[1]] == 0:
                            liberties.add(neighbor)

                if all(is_valid_coord(neighbor, size) and board[neighbor[0]][neighbor[1]] != 0 for neighbor in liberties):
                    for stone_coord in group:
                        new_board[stone_coord[0]][stone_coord[1]] = 0

    return new_board

Then, if you were to test it like so:

board_1 = [
    [0, 2, 2, 0, 0],
    [2, 1, 1, 2, 0],
    [2, 2, 1, 2, 0],
    [0, 0, 2, 0, 0],
    [0, 0, 0, 0, 0]
]

board_2 = [
    [0, 1, 0],
    [1, 2, 1],
    [0, 2, 0]
]

new_board_1 = remove_dead_groups(board_1)
for row in new_board_1:
    print(row)

print()

new_board_2 = remove_dead_groups(board_2)
for row in new_board_2:
    print(row)

You should get following results:

[0, 2, 2, 0, 0]
[2, 0, 0, 2, 0]
[2, 2, 0, 2, 0]
[0, 0, 2, 0, 0]
[0, 0, 0, 0, 0]

[0, 1, 0]
[1, 2, 1]
[0, 2, 0]

Finding surrounded groups in 2D list

1 Answers1