Formula for the max number of paths through a grid?

Question

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.

Answer 1

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:

n = 1, number of paths found = 1
n = 2, number of paths found = 4
n = 3, number of paths found = 22
n = 4, number of paths found = 113
n = 5, number of paths found = 571
n = 6, number of paths found = 2816
n = 7, number of paths found = 13616
n = 8, number of paths found = 64678
n = 9, number of paths found = 302574

And here's the code:

using System;
using System.Collections.Generic;
using System.Linq;

public struct Tile
{
    public Tile(int x, int y) { X = x; Y = y; }
    public readonly int X;
    public readonly int Y;
    public IEnumerable<Tile> GetNeighbours(int gridSize)
    {
        if (X > 0)
            yield return new Tile(X - 1, Y);
        if (X < gridSize - 1)
            yield return new Tile(X + 1, Y);
        if (Y > 0)
            yield return new Tile(X, Y - 1);
        if (Y < gridSize - 1)
            yield return new Tile(X, Y + 1);
    }
    public override string ToString()
    {
        return string.Format("({0},{1})", X, Y);
    }
}

public class Path
{
    public Path(Tile[] tiles) { Tiles = tiles; }
    public Tile[] Tiles { get; private set; }
    public override string ToString()
    {
        return string.Join("", Tiles.Select(tile => tile.ToString()).ToArray());
    }
}

public class PathFinder
{
    public IEnumerable<Path> FindPaths(int n, int gridSize)
    {
        if (n == 1)
        {
            for (int x = 0; x < gridSize; ++x)
                for (int y = 0; y < gridSize; ++y)
                    yield return new Path(new Tile[] { new Tile(x, y) });
        }
        else
        {
            Dictionary<string, object> pathsSeen = new Dictionary<string, object>();
            foreach (Path shortPath in FindPaths(n - 1, gridSize))
            {
                foreach (Tile tile in shortPath.Tiles)
                {
                    foreach (Tile neighbour in tile.GetNeighbours(gridSize))
                    {
                        // Ignore tiles that are already included in the path.
                        if (shortPath.Tiles.Contains(neighbour))
                            continue;

                        Path newPath = new Path(shortPath.Tiles
                            .Concat(new Tile[] { neighbour })
                            .OrderBy(t => t.X)
                            .ThenBy(t => t.Y)
                            .ToArray());

                        string pathKey = newPath.ToString();
                        if (!pathsSeen.ContainsKey(pathKey))
                        {
                            pathsSeen[pathKey] = null;
                            yield return newPath;
                        }
                    }
                }
            }
        }
    }

    static void Main()
    {
        PathFinder pathFinder = new PathFinder();
        for (int n = 1; n <= 9; ++n)
        {
            List<Path> paths = pathFinder.FindPaths(n, n).ToList();
            Console.WriteLine("n = {0}, number of paths found = {1}", n, paths.Count);
            //foreach (Path path in paths)
            //    Console.WriteLine(path.ToString());
        }
    }
}