I know my title is not very clear but I’m not sure how to word it.

Let’s start with a 4 by 4 grid; I eventually want to expand to an 8 by 8 or as big as I can get if 8 by 8 is too big but not any bigger. I’ve labeled the cells so it’s easier to talk about them and we need to start somewhere so I’ve added our starting position in the 0th cell in red. I’m only focusing on the 0th cell for now but you would start with a list of all the single cells. I’ll call this iteration 1.

Next, I would get all the possible positions that can be visited from here. I’ve marked cells that the starting position can visit in green. The rule is that you can only move up, down, left, or right, but you can move a variable distance. For example, you can move one tile to the right, or 3 tiles to the right. Back to this example, we could move to 1, 2, 3, 4, 8, and 12. (I would repeat this for all the 16 possible starting positions) As a set of pairs, they would be (0, 1), (0, 2), … , (0, 12). This is the second iteration.

Then, for each pair, get all the possible triplets. In the example, I’m using (0, 8). So they would be (0, 1, 8), (0, 2, 8), (0, 3, 8), (0, 4, 8), (0, 8, 9), (0, 8, 10), (0, 8, 11), (0, 8, 12)

And I would keep repeating these iterations until there’s no more empty space.

I’ve already written program that can do this. It’s fairly trivial, but it’s slow and uses a lot of memory. I’m hoping someone can give me some insight into this problem.

Code

I’m storing the positions as bitboards. It uses a breadth-first search to get all the positions. There’s a few optimizations I’m making, some I’m not sure are working, some I think might prune too much too soon leading to not all combinations being found.

internal class ValidPositionGenerator
{
    // Used to store new bitboards we need to check
    private readonly Queue<ulong> bitBoards = new Queue<ulong>();
    
    // Used to store unique bitboards we have found
    private readonly HashSet<ulong> visited = [];

    public ValidPositionGenerator(int maxTiles)
    {

        int i = 0;

    // This corresponds to the first iteration
        while (i < 64)
        {
            bitBoards.Enqueue(CanonicalizeBitboard((ulong)Math.Pow(2, i)));
            i++;
        }

        GenerateValid(bitBoards, maxTiles);
    }

    private void GenerateValid(Queue<ulong> bitBoards, int maxTiles)
    {
        int i = 0;
        while (bitBoards.Count != 0)
        {
            ulong board = bitBoards.Dequeue();

            if (visited.Contains(board))
            {
                continue;
            }

            if (BitOperations.PopCount(board) > maxTiles)
            {
                continue;
            }

            visited.Add(board);

            GetNewPositions(board, bitBoards, visited);
            
            i++;
        }
    }


    private static void GetNewPositions(ulong board, Queue<ulong> bitBoards, HashSet<ulong> visited)
    {
        // Get the active bits from board
        List<int> indices = GetIndices(board);

        int i;
        ulong canonical;

        // Loop over each one and attempt to add each one to the output
        foreach (int index in indices)
        {
            (int, int) pair = GetXYPairFromIndex(index);
            // Up
            i = 1;
            while (pair.Item2 - i > -1)
            {
                // Check if the next bit is already set: Optimization 1
                if (Util.GetBitboardCell(board, pair.Item1, pair.Item2 - i) == true)
                {
                    break;
                }
                // Optimization 2, 3, and 4 happens inside CanonicalizeBitboard()
                canonical = CanonicalizeBitboard(SetBitboardBit(board, pair.Item1, pair.Item2 - i, true));
                if (!visited.Contains(canonical))
                {
                    bitBoards.Enqueue(canonical);
                }
                i++;
            }
            // I've removed the rest to keep the code shorter
        // Left
            // Right
            // Down
            }
        }
    }

    private static List<int> GetIndices(ulong board)
    {
        ulong temp = board;
        List<int> indices = new List<int>();
        int index = 0;
        while (board > 0)
        {
            if ((board & 1) == 1)
            {
                indices.Add(index);
            }
            board >>= 1;
            index++;
        }
        return indices;
    }

    // Convert index to an x, y pair
    private static (int, int) GetXYPairFromIndex(int index)
    {
        return (index % 8, index / 8);
    }
}

Optimization 1: Don’t double check

While scanning for new positions, if we find an already active position, we can stop because we can continue from there when we get there. In the example below, I’m on (0, 2) scanning for bits to the right of 0. When we reach 2, we see that is already active so we can stop. Then we continue scanning down, left before scanning bits around 2. From here, we would continue scanning to the right getting anything we missed. I haven’t tested if this actually improves anything yet.

I think a possible optimization would be to create another bitboard with all the places we visited during this check and stop when we find something already found. Because once we get to 2, it’ll start scanning left towards 0 but it already found everything in that direction. I think I can merge this we the first optimization. It seems like an extension of it.

Optimization 2: Don’t store mirrors or rotations

Every combination has symmetry and I don’t need it. I only need to keep one of them. That’s what the canonicalizeBitboard method does. It checks it against rotations and reflections. This drastically reduces the search space. Instead of storing 16 possibilities in the first iteration, we only need to store 3: 0, 1, and 5.

Optimization 3: Don’t store similar translations

Consider the two grids below. They are essentially the same thing to me. So when I canonicalize the bitboard, I’m also shifting it so it’s flush to the top left corner.

Optimization 4: Condensed

Considered the following two bitboards. For my purposes, I only care about the unique combinations of moving up, down, left or right. If we start from 0, we can move right and down in both of them so to me, they are the same and I only need one. However, I’m not sure if I can remove it entirely. I think I’ll still need to keep it for when I check for new bitboards, but I don’t need it in my output. I’m confused about this point for my other optimizations as well. I think that even if I don’t need them in my output, I should still check them because the new position I can get from them might be unique and not found in their condensed version.

Conclusion

That’s all the optimizations I can think of for now, but writing this post has got me thinking. All I’m really doing is finding all the possible combinations/permutations of up, down, left or right, where the sum of left and right equals the size of the width of the bitboard – 1 and similarly with up and down, but with some extra rules, maybe. Maybe there’s a way to think about it differently. I think there might be a way to think about it terms of a string of up, down, left, and right and then that somehow gets mapped to a canonical bitboard.

What I’ve tried so far

I’ve tried my code and it works. I’m just wondering if there’s a better way. When I call the ValidPositionGenerator() constructor and use 6 as an input, it takes about 6 seconds and half a gig of memory. At 7, it takes about 2 minutes and uses 16 gigs of memory. When I profile it, the bitBoards queue blows up like crazy and that might very well be unavoidable. I know there are 2^64 possible bitboards but I’m hoping my rules and optimizations makes that more manageable.