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.