1
$\begingroup$

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).

enter image description here

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 :/

enter image description here

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Yuval Filmus
    Dec 16, 2017 at 13:11
  • $\begingroup$ Thanks, I was asking for some ideas because if I work with a larger tile set backtracking becomes impractical. $\endgroup$
    – flybynight
    Dec 18, 2017 at 9:48

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for your answer, you are indeed correct, the prototype I have right now works reasonably fast for the 9 tiles I have right now, but when increasing that number to say 64, the whole thing becomes impractical. I shall edit the op to clarify that. $\endgroup$
    – flybynight
    Dec 18, 2017 at 9:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.