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:


I need to map out all connected graphs with 6 vertices
Try all the combinations of tiles that fit on those vertices
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.
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.

You could also use backtracking or other more sophisticated methods to reduce the number of configurations you need to examine, but it might not be worthwhile to implement.  You might spend 10 hours programming to save 1 hour of CPU time -- might not be worth it.  I suggest you try the simple, dumb, brute-force search first, before thinking too hard about more sophisticated algorithms.