For example, let's say we have a limited two-dimensional grid that we want to cover with square tiles of the same size. We have an unlimited number of tiles that fall into a certain number of types. Each type of tile indicates the letters printed on that tile. Letters are printed next to each edge, and only tiles with corresponding letters on their adjacent edges can be located next to each other on the grid. Tiles can be rotated.
Given the size of the grid type and tile type definitions, what is the fastest way to layout tiles so that the above restriction is met and the entire / most part of the grid is covered? Note that my use case is for large grids (~ 20 in each dimension) and the average number of solutions (unlike Eternity II).
So far I have tried DFS, starting from the center, and choosing places around the filled area that allow the least amount of opportunity and return in case progress cannot be made. This only works for simple scenarios with one or two types. More and more retreating.
Here is a trivial example showing the input and the final result:
