如何更快判断Bitboard中的0是否构成Polyomino？

我当前使用的方法逻辑清晰，但希望进一步提升性能，寻求其他可行方案。需求是判断Bitboard里所有0的位置是否构成Polyomino——定义为所有方块通过边缘（上下左右）相连的排列，允许镜像、旋转、翻转，也允许带孔。

现有实现思路 #

我的现有方法：

• 统计Bitboard中0的总数；
• 找到第一个0的位置，通过**广度优先搜索（BFS）**遍历所有边缘连通的0；
• 若遍历到的0的数量等于总数，则判定为Polyomino，否则不是。

另一种思路构想 #

我还想到一个跨行合并岛屿的思路：遍历每一行拆分出0的“岛屿”（也可反转Bitboard找1的岛屿，逻辑一致）。例如下面两行：

1 1 1 0 0 1 1 1
0 0 1 1 1 1 0 0

第一行有两个0的岛屿a（前三个1后的两个0）和b（最后三个1前的两个0），第二行有一个0的岛屿c（中间四个1两侧的两个0）。若a和c的按位与结果不为0，说明二者连通；同理b和c也连通，可将a和b合并。重复这个跨行合并过程，最终若所有岛屿合并为一个，就说明是Polyomino。但不确定拆分岛屿的开销是否会影响效率。

注：Bitboard索引规则为左上角起点，从左到右排列，index+1对应右侧单元格，index-8对应上方单元格。

现有代码实现 #

public static bool PolyominoChecker(ulong bitboard)
{
    // 统计0的数量
    int population = 64 - BitOperations.PopCount(bitboard);

    HashSet<int> visited = new HashSet<int>();
    Queue<int> queue = new Queue<int>();

    // 获取第一个0的位置
    int firstZero = BitOperations.TrailingZeroCount(~bitboard);
    visited.Add(firstZero);
    queue.Enqueue(firstZero);

    // BFS遍历所有连通的0
    while (queue.Count > 0)
    {
        int index = queue.Dequeue();
        // 检查左侧单元格
        if(index % 8 > 0 && !GetBitboardCell(bitboard, index - 1))
        {
            if (!visited.Contains(index - 1))
            {
                visited.Add(index - 1);
                queue.Enqueue(index - 1);
            }
        }
        // 检查上方单元格
        if (index >= 8 && !GetBitboardCell(bitboard, index - 8))
        {
            if (!visited.Contains(index - 8))
            {
                visited.Add(index - 8);
                queue.Enqueue(index - 8);
            }
        }
        // 检查下方单元格
        if (index + 8 < 64 && !GetBitboardCell(bitboard, index + 8))
        {
            if (!visited.Contains(index + 8))
            {
                visited.Add(index + 8);
                queue.Enqueue(index + 8);
            }
        }
        // 检查右侧单元格
        if (index % 8 < 7 && !GetBitboardCell(bitboard, index + 1))
        {
            if (!visited.Contains(index + 1))
            {
                visited.Add(index + 1);
                queue.Enqueue(index + 1);
            }
        }
    }

    // 遍历到的0数量等于总数则符合条件
    return visited.Count == population;
}

public static bool GetBitboardCell(ulong bitboard, int index)
{
    return (bitboard & (1UL << index)) != 0;
}

优化方案建议 #

1. 现有BFS的性能优化 #

现有代码的瓶颈在于HashSet<int>的哈希查找开销，以及GetBitboardCell的重复调用。可以通过以下方式优化：

• 用位掩码替代HashSet：用ulong visitedMask记录已访问的0位置，位运算判断访问状态比哈希查找快得多；
• 提前计算反转后的Bitboard：减少重复的位运算调用；
• 提前终止遍历：一旦遍历到的0数量等于总数，直接返回结果。

优化后的BFS代码：

public static bool PolyominoCheckerOptimized(ulong bitboard)
{
    ulong emptyCells = ~bitboard;
    int population = BitOperations.PopCount(emptyCells);

    // 无0或全为0的情况直接返回true
    if (population == 0 || population == 64)
        return true;

    ulong visitedMask = 0;
    Queue<int> queue = new Queue<int>();

    int firstZero = BitOperations.TrailingZeroCount(emptyCells);
    ulong firstZeroMask = 1UL << firstZero;
    visitedMask |= firstZeroMask;
    queue.Enqueue(firstZero);
    int visitedCount = 1;

    while (queue.Count > 0)
    {
        int index = queue.Dequeue();

        // 左侧单元格
        if (index % 8 > 0)
        {
            int left = index - 1;
            ulong leftMask = 1UL << left;
            if ((emptyCells & leftMask) != 0 && (visitedMask & leftMask) == 0)
            {
                visitedMask |= leftMask;
                queue.Enqueue(left);
                visitedCount++;
                if (visitedCount == population)
                    return true;
            }
        }

        // 上方单元格
        if (index >= 8)
        {
            int up = index - 8;
            ulong upMask = 1UL << up;
            if ((emptyCells & upMask) != 0 && (visitedMask & upMask) == 0)
            {
                visitedMask |= upMask;
                queue.Enqueue(up);
                visitedCount++;
                if (visitedCount == population)
                    return true;
            }
        }

        // 下方单元格
        if (index < 56) // 56 = 64 - 8，避免越界
        {
            int down = index + 8;
            ulong downMask = 1UL << down;
            if ((emptyCells & downMask) != 0 && (visitedMask & downMask) == 0)
            {
                visitedMask |= downMask;
                queue.Enqueue(down);
                visitedCount++;
                if (visitedCount == population)
                    return true;
            }
        }

        // 右侧单元格
        if (index % 8 < 7)
        {
            int right = index + 1;
            ulong rightMask = 1UL << right;
            if ((emptyCells & rightMask) != 0 && (visitedMask & rightMask) == 0)
            {
                visitedMask |= rightMask;
                queue.Enqueue(right);
                visitedCount++;
                if (visitedCount == population)
                    return true;
            }
        }
    }

    return visitedCount == population;
}

2. 跨行岛屿合并思路的评估 #

这个思路的核心是通过行内岛屿的跨行连通性合并，但拆分行内岛屿需要额外的位运算操作。对于8x8的Bitboard来说，每行拆分岛屿的开销不大，但合并逻辑需要维护岛屿集合并检查连通性，整体复杂度比优化后的BFS更高，甚至可能因为集合操作的开销更慢。如果是更大尺寸的Bitboard，该思路可能有并行处理的潜力，但8x8场景下优化后的BFS更直接高效。

3. 极致位运算连通性判断 #

针对8x8的Bitboard，可完全用位运算实现连通分量计算，无需集合和队列，性能最优：

public static bool PolyominoCheckerBitwise(ulong bitboard)
{
    ulong empty = ~bitboard;
    if (empty == 0) return true;

    ulong connected = empty & -empty; // 获取第一个0对应的位掩码
    ulong prev;

    do
    {
        prev = connected;
        // 处理右侧邻居：左移1位，用掩码避免跨行列
        ulong right = connected << 1;
        right &= 0x7F7F7F7F7F7F7F7F;
        // 处理左侧邻居：右移1位，用掩码避免跨行列
        ulong left = connected >> 1;
        left &= 0xFEFEFEFEFEFEFEFE;
        // 处理上方邻居：上移8位
        ulong up = connected << 8;
        // 处理下方邻居：下移8位
        ulong down = connected >> 8;

        // 合并所有连通的邻居，并仅保留属于empty的部分
        connected |= right | left | up | down;
        connected &= empty;
    } while (connected != prev);

    return connected == empty;
}

内容的提问来源于stack exchange，提问作者timeslidr