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