Given a grid of open spots, and a certain number of tiles to place in those spots, what function f(openSpots, tilesToPlace)
will give you the number of continuous paths you can form?
Continuous paths are placements of the tiles such that each tile shares an edge with another. (Only corners touching is not good enough. So (0, 1)
and (0, 0)
are legal, but (1, 1)
and (2, 2)
is not.)
I already have a function that will find all these paths. However, it only works for small numbers. For larger values, all I need is a count of how many could possibly exist. Here is some data:
For 1 tiles, there are 1 paths.
For 2 tiles, there are 4 paths.
For 3 tiles, there are 22 paths.
For 4 tiles, there are 89 paths.
For 5 tiles, there are 390 paths.
For 6 tiles, there are 1476 paths.
For 7 tiles, there are 5616 paths.
For 8 tiles, there are 19734 paths.
For 9 tiles, there are 69555 paths.
This gets really slow to calculate as the puzzle size increases. I think the asymptotic complexity of my path finding solution is pretty bad.
If there are n
tiles, the grid is at most n
spots long and wide.
Best Answer
Your problem seems to be at least as difficult as enumerating polyominoes. There are no known fast algorithms for doing this, and the best known algorithms struggle after n=50. I doubt there is a fast way to solve this problem.
I'm not even going to pretend that this is an optimal solution but it might be useful as a reference solution. I think it at least gives the correct answer, although it takes some time. It solves the problem recursively by finding all paths of length n-1, then checking for all possible places it can add one more tile and removing duplicate solutions. It has a particularly ugly part where it checks for duplicate by converting the path to a string and comparing the strings, but it was fast to write.
Here's the output it generates:
And here's the code: