Haskell – Monads as adjunctions

Here's an even simpler answer: A Monad is something that "computes" when monadic context is collapsed by join :: m (m a) -> m a (recalling that >>= can be defined as x >>= y = join (fmap y x)). This is how Monads carry context through a sequential chain of computations: because at each point in the series, the context from the previous call is collapsed with the next.

A free monad satisfies all the Monad laws, but does not do any collapsing (i.e., computation). It just builds up a nested series of contexts. The user who creates such a free monadic value is responsible for doing something with those nested contexts, so that the meaning of such a composition can be deferred until after the monadic value has been created.

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());
        }
    }
}