How to remove an ordering requirement from a board game simulation?

Question

The Problem:

I'm trying to simulate part of the game tantrix which is a board game played with hexagonal tiles. Each tile has 3 lines of different colors that each start at one side of the hexagon and end at another side. a line is drawn between these tiles. Adding multiple tiles together one can make a line consisting of more than one tile. These hexagonal tiles are placed on a board based on some rules:

• In real life the first tile is placed on the board without restrictions, as it marks how all other tiles are placed as they are aligned to the first tile.
• The second tile is placed next to it at 1 of the 6 sides, at this point the only requirement is that the sides that are connected to each other have the same color.
• From the third tile onward the new tile needs to be placed connecting to 2 sides instead of 1, again both of these sides need to have the same color as the side they connect to.

With these simple rules in mind I want to simulate a small part of the game with the intent to find all configurations of the board that satisfy a given condition, and then print those configurations: All connections with the color red form a single continuous line.

For now i'm interested in simulating games using 14 tiles (which is 1/4th the entire set). The tiles that I choose are such that they are all the tiles with 3/4 colors (let's say red, blue and green).

---

The Program:

I started writing a program in c++ to see if I can find these configurations. There are several things that I'm storing for these tiles:

• The coordinates on a grid: This is useful when I need to get information on adjacent tiles and when I need to keep track where a given tile is on the playing board.
• 6 "state" variables which can be either r,g,b,y (red,green,blue,yellow): These 6 variables store how the 6 sides are colored.
• An identifier variable: In the game each tile is identified by a number on the back. This number is also helpful when referencing tiles that haven't been placed on the board yet.

Also interesting is that tiles can be rotated using a function rotate() which basically takes state[0] and places it in state[1], state[1] in state[2] etc. My current mindset was to do the following:

• Loop through all tiles and place 1 on the board at coordinates {0,0} then remove it from the set of unplaced tiles.
• For each tile, see if it fits anywhere on the existing grid and save those coordinates and the rotation of the tile if it fits, then rotate the tile once and try again, do this until all 6 rotations have been checked.
• Once all valid states have been found for one tile move on to the next.

The problem with this solution is that it will find different configurations based on the order of the list. Therefor I initially though of checking all orders of the list, which would basically mean checking 14! = 87178291200 versions of the same list and finding all possible configurations with them.

Currently the main algorithm looks like this (written in c++):

//provide a board with tiles layed on them and premVec an list of tiles to still place on the board.
void calcboard(std::vector<tile> permVec, board b) {
    bool secondToAdd;
    std::list<tileRot> valid = std::list<tileRot>();
    secondToAdd = true;
    //iterate through all tiles in the list
    for (int iTile = 0; iTile < 13; iTile++) {
        //obtain the list of valid tiles and rotation for the iTileth tile of the list
        valid = getValidSpacesForTile(permVec.at(iTile), secondToAdd, b);
        //we now have a list of all valid positions for all rotations for the tile to insert next given the previous board.
        for (tileRot tileValid : valid) {
            //add the tile to the board so we can recursively see how the next tile fits the board.
            b.addToBoard(tileValid.t);
            //check if there are still tiles to place
            if (permVec.size() > 0) {
                //create a copy of the list
                std::vector<tile> cpy = permVec;
                //remove the placed element from the copy
                cpy.erase(cpy.begin() + iTile);
                //calculate all board options for the remaining tiles.
                calcboard(cpy, b);
            } else {
                totalBoards++;
                //check if the board contains a single line for state "r" (currently potentially broken)
                if (checkLineContinuous(r, b))
                {
                    //we've found a line that works, print the board.
                    printf("Board %d is valid!\n", totalBoards);
                    b.printBoard();
                }
                else
                {
                    //we've found an invalid board.
                    printf("Board %d is invalid!\n", totalBoards);
                }
            }
            //remove the tile from the board so it can be added somewhere else.
            b.removeFromBoard(tileValid.t);
        }
        secondToAdd = false;
    }
}

This function is called once for each permutation of the remaining list of 13 tiles once the first tile is placed on the board. This is repeated 14 times taking each tile as starting tile. therefor this function is called 14! times which is far from optimal.

The problem is there are probably a lot of calculations done which aren't needed. For example if you would take a grid of tiles and add 1 to all the X coordinates you essentially have the same configuration of the board (the only thing different being the arbitrary coordinates that have no reflection on the real world situation). currently we are doing a calculation for both these cases, but ideally we would do each configuration once and then exclude all configurations that only differ in their coordinates.

There are probably a lot more optimizations to do that i'm not thinking about right now but i think the most important thing is the fact that I use all permutations of the list. Having a different order to the list is going to influence which configurations can be made. Is there a way to mitigate this and make it so that I don't have to do this.

How can I remove the need to calculate every permutation of the set of 13 tiles? Are there any other optimizations to be done?

Here is the full project for anyone who wants to take a closer look: https://pastebin.com/HEjaGxAL

I hope my explanation is clear, feel free to ask any questions if it's not.

Answer 1

Let's consider a configuration to be the location of all tiles, i.e., a state of the board at a particular time. To be valid a configuration must satisfy four requirements: (1) every tile (other than the starter tile) must be adjacent to at least two other tiles; (2) adjacent tiles must have the same color at the edge they share; (3) the red edges must form a continuous path; (4) it uses each of the 14 tiles at most once. Your task is to enumerate all configurations that are reachable by a sequence of legal moves.

I'm pretty sure that every valid configuration is reachable by some sequence of moves. Therefore, we don't need to enumerate all sequences of moves; it suffices to enumerate all valid configurations (i.e., enumerate over just the final state after making the moves). Because most configurations are reachable by a large number of moves, this can potentially significant speed up enumeration.

Define the shape of a configuration to be the locations where tiles are present (i.e., if we imagine we erase all colors).

Here is one plausible high-level schema for enumerating valid configurations:

1. Enumerate all valid shapes (i.e., satisfying requirements (1) and (4)).

2. For each shape, enumerate all valid possibilities for the locations of the red edges (satisfying requirements (3)).

3. For each shape and path of red, enumerate all valid possibilities for the colors on the tiles (satisfying conditions (2) and (4)).

This will then give you an enumeration of all valid configurations.

Enumerating shapes

There are many ways to enumerate all possible shapes, and this probably is not the performance bottleneck, so any method will probably work fine.

Here is one possible approach. Without loss of generality, we can assume that hex at the origin is filled and there are no filled hexes above or to the left of it. (Effectively, we've translated the shape into a canonical position.) Then, enumerate all ways to build up the shape recursively, starting from the origin. At any point, we'll have a "boardmap" (which maps each hex location to one of three possibilities: "filled by a tile in the final shape", "not filled in the shape", "unknown/to be determined") and a hex tile we just placed. Our recursive function will enumerate all $2^6$ possibilities for which subsets of neighboring locations are filled vs empty, filter that set to keep only ones that are consistent with the boardmap so far and that ensure there are at least 2 neighbors filled and ensure that you don't place more than 14 tiles in total, and then temporarily fill in the boardmap with those 6 states for the neighbors and recurse. To account for the starter tile, whenever you place a tile, optionally allow that to be marked in the boardmap as a starter tile if the boardmap doesn't already contain a starter tile, and allow any starter tile to have only 1 filled neighbor. Keep track of all shapes reached during this search; that's your enumeration of shapes.

If you want to avoid duplicating each shape 6 times due to rotational symmetry, you can post-filter the list to keep only one shape from each rotational equivalence class. One approach: store the shapes in a hashtable, and before adding a shape to the hashtable, generate its 6 rotational equivalents and only add it if none of those are already present. A faster approach: when you form a shape, compute its hash and the hash of all of its 6 rotations, and keep only the shape whose hash value is lowest.

Enumerating red paths

Choose a tile to be the starting point for the red path (whenever I write "choose", I mean you should enumerate all possibilities). Then choose the next tile in the path, and so on.

This will enumerate each path twice (once where you start from one endpoint, once where you start from the other endpoint). It is easy to deduplicate if you want: e.g., hash the two endpoints of the path and keep the red path only if you started from the endpoint with lower hash value.

Enumerating tile colors

Now we are given a shape and the location of all red edges, and we must enumerate over all valid ways to fill in the other colors. I expect this will be the most performance-sensitive step.

One plausible approach is to visit the locations in the shape in some order, and when you visit a location, choose a tile from your supply of remaining tiles and place it there (but ensuring that it is consistent with rule (2) and with previously filled-in edge colors). This can be easily implemented with a recursive search, if you have an ordering in mind. At each step in the recursive traversal, you have a "colormap" that indicates for each location in the shape what the colors of some edges of some tiles are (others are not known yet), and a "supply" of tiles that you haven't used yet (initially this is all 14 tiles), and a location that you just filled in.

I imagine the order in which you visit tiles will greatly affect the performance of this step. A good order might help you prune many possibilities during the recursive traversal. I don't know how to choose an optimal order, but I will suggest one heuristic that might be reasonable.

Let $R$ be the set of hex locations that have red edges (i.e., that the red path goes through), and $r_0$ be a starting point of the red path. If $x$ is a location, let $d(r_0,x)$ denote the distance between $r_0$ and $x$ (i.e., the number of steps it takes to get from $r_0$ to $x$, if in each step you can move from one hex to another adjacent hex). Also let $d(R,x) = \min_{r \in R} d(r,x)$ denote the distance between $P$ and $x$ (i.e., the smallest number of steps to get from $x$ to some location on the red path).

Now I suggest you compute $100 d(R,x) + d(r_0,x)$ for each location $x$ in the shape, sort in order of this value, and visit the tiles in that sorted order.

---

This answer outlines one possible way to approach the problem. It's surely not the only way and I make no claim it is the best way, it is just one possibility you could try. If I understand your approach correctly (which I might not), it might speed up on your approach by avoiding the need to enumerate orders of moves.