# Filling a 3x3 board with connected tiles

long story short: I want to list all possible combinations of n tiles on a 3x3 board with the restriction that at least 6 tiles are part of a connected chain. Tiles are connected if the pattern continues from one to the other and a tile can be repeated any number of times (see image below for clarification, I would like to increase the number of available tiles at one point).

You can see some of my thoughts below, I would like to know if there's a more elegant solution to this problem or (if I'm on the right track) some ideas on optimizations and data structures that I would need to actually implement this.

It seems to me there are three separate problems:

1. I need to map out all connected graphs with 6 vertices
2. Try all the combinations of tiles that fit on those vertices
3. List item

Since I actually need to print all the solutions I was thinking that there's no way of avoiding backtracking, so all my ideas so far are basically optimizations of the process. The biggest time save so far is the fact that once you have a valid configuration you can also print out its rotations (see picture below), thus cutting the search time to a quarter, but the catch is i don't know how to deal with duplicate solutions :/

There's also the observation that since I need to have a minimum of six connected tiles, one of them will surely be in a corner (upper left corners seems like the logical place to start) so all the connected graphs would have to start out in that corner.

That's about everything I have right now, thank you for reading and any help is highly appreciated.

• Backtracking seems like a terrific approach. You can possibly optimize it somewhat by first solving the $3\times 1$ case, though it's not clear whether the resulting algorithm will actually be faster. – Yuval Filmus Dec 16 '17 at 13:11
• Thanks, I was asking for some ideas because if I work with a larger tile set backtracking becomes impractical. – flybynight Dec 18 '17 at 9:48

There are only $9^9$ possible ways to fill each cell with one of the 9 tiles. That's a bit under 400 million possibilities. So, I suggest a simple approach: enumerate all of them, and for each, check whether or not it meets your conditions. That should run pretty fast: you should be able to very quickly test a candidate configuration to see if it satisfies your requirements, and then a computer should be able to do that 400 million times pretty rapidly. Repeatedly doing some tedious task is what computers are really good at.