Determining whether a given point would create an island-CodePudding

I'm currently working on porting the game Hitori, aka Singles to the Game Boy in C using GBDK. One of the rules of this game is that no area of the board can be completely closed off from other areas. For example, if the current state of the board is:

00100
01000
00000
00000
00000

the solution cannot contain a 1 at (0,0) or (0,2). The board generation function needs to be able to detect this and not place a black tile there. I'm currently using a non-recursive depth-first search, which works, but is very slow on larger boards. Every other implementation of this game I can find on the internet uses DFS. The Game Boy is just too slow.

What I need is an algorithm that, when given a coordinate, can tell whether or not a 1 can be placed at that location without dividing the board. I've looked into scanline-based filling algorithms, but I'm not sure how much faster they'll be since boards rarely have long horizontal lines in them. I also thought of using an algorithm to follow along an edge, but I think that would fail if the edge wasn't connected to the side of the board:

00000
00100
01010
00100
00000

Are there any other types of algorithm that can do this efficiently?

CodePudding user response：

I looked at another generator code, and it repeatedly chooses a tile to consider blackening, doing so if that doesn’t lead to an invalid board. If your generator works the same way, we can exploit the relatedness of the connectivity queries. The resulting algorithm will require O(n²)-time initialization and then process each update in amortized O(log n) time (actually inverse Ackermann if you implement balanced disjoint set merges). The constants should be OK as algorithms go, though n = 15 is small.

Treating the board as a subset of the grid graph with the black tiles removed, we need to detect when the number of connected components would increase from 1. To borrow an idea from my colleague Jakub Łącki and Piotr Sankowski (“Optimal Decremental Connectivity in Planar Graphs”, Lemma 2), we can use Euler characteristic and planar duality to help accomplish this.

Let me draw an empty board (with numbered tiles) and its grid graph.

 - - - 
|1|2|3|
 - - - 
|4|5|6|
 - - - 
|7|8|9|
 - - - 

1-2-3
|a|b|
4-5-6
|c|d|
7-8-9 i

In the graph I have lettered the faces (finite faces a, b, c, d and the infinite face i). A planar graph satisfies the formula V − E F = 2 if and only if it is connected and nonempty. You can verify that this one indeed does, with V = 9 vertices and E = 12 edges and F = 5 faces.

By blackening a tile, we remove its vertex and the neighboring edges from the graph. The interesting thing here is what happens to the faces. If we remove the edge 2-5, for example, then we connect face a with face b. This is planar duality at work. We’ve turned a difficult decremental problem in the primal into an incremental problem in the dual! This incremental problem can be solved the same way as it is in Kruskal’s algorithm, via the disjoint set data structure.

To show how this works, suppose we blacken 6. Then the graph would look like this:

1-2-3
|a|
4-5
|c|
7-8-9 i

This graph has V = 8 and E = 9 and F = 3, so V − E F = 2. If we were to remove 2, then vertex 3 is disconnected. The resulting graph would have V = 7 and E = 6 and F = 2 (c and i), but V − E F = 3 ≠ 2.

Just to make sure I didn’t miss anything, here’s a tested implementation in Python. I have aimed for readability over speed since you’re going to be translating it into C and optimizing it.

import random


# Represents a board with black and non-black tiles.
class Board:
    # Constructs an n x n board.
    def __init__(self, n):
        self._n = n
        self._black = [[False] * n for i in range(n)]
        self._faces = [[Face() for j in range(n - 1)] for i in range(n - 1)]
        self._infinite_face = Face()

    # Blackens the tile at row i, column j if possible. Returns True if
    # successful.
    def blacken(self, i, j):
        neighbors = list(self._neighbors(i, j))
        if self._black[i][j] or any(self._black[ni][nj] for (ni, nj) in neighbors):
            return False
        incident_faces = self._incident_faces(i, j)
        delta_V = -1
        delta_E = -len(neighbors)
        delta_F = 1 - len(incident_faces)
        if delta_V - delta_E   delta_F != 2 - 2:
            return False
        self._black[i][j] = True
        f = incident_faces.pop()
        for g in incident_faces:
            f.merge(g)
        return True

    # Returns the coordinates of the tiles adjacent to row i, column j.
    def _neighbors(self, i, j):
        if i > 0:
            yield i - 1, j
        if j > 0:
            yield i, j - 1
        if j < self._n - 1:
            yield i, j   1
        if i < self._n - 1:
            yield i   1, j

    # Returns the faces incident to the tile at row i, column j.
    def _incident_faces(self, i, j):
        return {self._face(fi, fj) for fi in [i - 1, i] for fj in [j - 1, j]}

    def _face(self, i, j):
        return (
            self._faces[i][j]
            if 0 <= i < self._n - 1 and 0 <= j < self._n - 1
            else self._infinite_face
        ).rep()


# Tracks facial merges.
class Face:
    def __init__(self):
        self._parent = self

    # Returns the canonical representative of this face.
    def rep(self):
        while self != self._parent:
            grandparent = self._parent._parent
            self._parent = grandparent
            self = grandparent
        return self

    # Merges self and other into one face.
    def merge(self, other):
        other.rep()._parent = self.rep()


# Reference implementation with DFS.
class DFSBoard:
    def __init__(self, n):
        self._n = n
        self._black = [[False] * n for i in range(n)]

    # Blackens the tile at row i, column j if possible. Returns True if
    # successful.
    def blacken(self, i, j):
        neighbors = list(self._neighbors(i, j))
        if self._black[i][j] or any(self._black[ni][nj] for (ni, nj) in neighbors):
            return False
        self._black[i][j] = True
        if not self._connected():
            self._black[i][j] = False
            return False
        return True

    # Returns the coordinates of the tiles adjacent to row i, column j.
    def _neighbors(self, i, j):
        if i > 0:
            yield i - 1, j
        if j > 0:
            yield i, j - 1
        if j < self._n - 1:
            yield i, j   1
        if i < self._n - 1:
            yield i   1, j

    def _connected(self):
        non_black_count = sum(
            not self._black[i][j] for i in range(self._n) for j in range(self._n)
        )
        visited = set()
        for i in range(self._n):
            for j in range(self._n):
                if not self._black[i][j]:
                    self._depth_first_search(i, j, visited)
        return len(visited) == non_black_count

    def _depth_first_search(self, i, j, visited):
        if (i, j) in visited:
            return
        visited.add((i, j))
        for ni, nj in self._neighbors(i, j):
            if not self._black[ni][nj]:
                self._depth_first_search(ni, nj, visited)


def generate_board(n, board_constructor=Board):
    deck = [(i, j) for i in range(n) for j in range(n)]
    random.shuffle(deck)
    board = Board(n)
    return {(i, j) for (i, j) in deck if board.blacken(i, j)}


def generate_and_print_board(n):
    black = generate_board(n)
    for i in range(n):
        print("".join(chr(9633 - ((i, j) in black)) for j in range(n)))


def test():
    n = 4
    boards = set(frozenset(generate_board(n, Board)) for i in range(1000000))
    reference_boards = set(
        frozenset(generate_board(n, DFSBoard)) for k in range(1000000)
    )
    assert len(boards) == len(reference_boards)


if __name__ == "__main__":
    generate_and_print_board(15)
    test()