Recursive tree search

Question

Taking into account a 5x5 grid, it requires all possible combinations of knights moves to be recorded, from every single starting square, via every subsequent square.

I envisaged it as being a binary tree like structure, but as each square on the board can have more than 2 potential next moves, I don't think it would work. I looked into A*/Pathfinding algorithms, but they all require an end node to work with from what I can see, and I don't know the end node as it is on going every time and would be different.

My pseudocode thus far is:

For each square on the board
    Check if this key has potential moves
        If Potential moves
            <Some way of selecting a next move (this could be the square we just originated from too!)>
            Register this move into a collection we can check against for subsequent                             moves
            Recursively call function with the square we just landed on 
        Else Continue
End

Any advice/pointers would be greatly appreciated as I am very lost!

Answer 1

Ok, there will be an extreme number of possible sequences of moves, as comments allude to. This is from the top of my head, so bear with me.

Non-recursive version: You need a list of lists of positions (called a position list), which will be your final answer, i'll call that list the routes list.

Create one list for each starting position and put them all into the routes list.

While the routes list has a position list that's less than the required length
{
    Get a position list that's too short.
    Remove it from the routes list
    Create new position lists that are a copy of the list we just removed + a possible next position from the last position in the list.
    Add those lists to the routes list.
}

---

EDIT: Recursive version:

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

namespace ConsoleApplication1
{
    class Program
    {
        static int GridSize = 5;

        static void Main(string[] args)
        {
            List<List<Point>> Positions = (from X in Enumerable.Range(0, GridSize)
                                           from Y in Enumerable.Range(0, GridSize)
                                           select new List<Point>() { new Point(X, Y) }).ToList();

            var PossibleRoutes = WalkGraph(Positions, 5);
        }

        static List<List<Point>> WalkGraph(List<List<Point>> RoutesList, int DesiredLength)
        {
            List<List<Point>> Result = new List<List<Point>>();

            foreach (var Route in RoutesList)
            {
                if (Route.Count < DesiredLength)
                {
                    // Extend the route (produces a list of routes) and recurse
                    Result.AddRange(WalkGraph(ExtendRoute(Route), DesiredLength));
                }
                else
                {
                    Result.Add(Route);
                }
            }

            return Result;
        }

        static List<List<Point>> ExtendRoute(List<Point> Route)
        {
            List<List<Point>> NextMoveRoutes = new List<List<Point>>();

            // Itterate through each possible move
            foreach (var NextMove in PossibleMoves(Route.Last()))
            {
                // Create a copy of the route, and add this possible move to it.
                List<Point> NextMoveRoot = new List<Point>(Route);
                NextMoveRoot.Add(NextMove);
                NextMoveRoutes.Add(NextMoveRoot);
            }

            return NextMoveRoutes;
        }

        static List<Point> PossibleMoves(Point P)
        {
            // TODO Generate a list of possible places to move to

            List<Point> Result = new List<Point>();

            Result.Add(new Point(P.X + 1, P.Y + 2));
            Result.Add(new Point(P.X - 1, P.Y + 2));
            Result.Add(new Point(P.X + 1, P.Y - 2));
            Result.Add(new Point(P.X - 1, P.Y - 2));

            Result.Add(new Point(P.X + 2, P.Y + 1));
            Result.Add(new Point(P.X - 2, P.Y + 1));
            Result.Add(new Point(P.X + 2, P.Y - 1));
            Result.Add(new Point(P.X - 2, P.Y - 1));

            Result.RemoveAll(PossibleMove => PossibleMove.X < 0 || PossibleMove.X > GridSize ||
                                             PossibleMove.Y < 0 || PossibleMove.Y > GridSize);

            return Result;
        }
    }
}

---

EDIT: Below is a version using IEnumerable, to eliminate initial computation time, and to reduce memory footprint drastically.

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

namespace ConsoleApplication1
{
    class Program
    {
        static int GridSize = 5;

        static void Main(string[] args)
        {
            IEnumerable<IEnumerable<Point>> Positions = from X in Enumerable.Range(0, GridSize)
                                                        from Y in Enumerable.Range(0, GridSize)
                                                        select new List<Point>() { new Point(X, Y) } as IEnumerable<Point>;

            var PossibleRoutes = WalkGraph(Positions, 100);

            foreach (var Route in PossibleRoutes)
            {
                Console.WriteLine(Route.Select(P => P.ToString()).Aggregate((curr, next) => curr + " " + next));
                //Thread.Sleep(500); // Uncomment this to slow things down so you can read them!
            }

            Console.ReadKey();
        }

        static IEnumerable<IEnumerable<Point>> WalkGraph(IEnumerable<IEnumerable<Point>> RoutesList, int DesiredLength)
        {
            foreach (var Route in RoutesList)
            {
                if (Route.Count() < DesiredLength)
                {
                    // Extend the route (produces a list of routes) and recurse
                    foreach (var ExtendedRoute in WalkGraph(ExtendRoute(Route), DesiredLength))
                        yield return ExtendedRoute;
                }
                else
                {
                    //Result.Add(Route);
                    yield return Route;
                }
            }
        }

        static IEnumerable<IEnumerable<Point>> ExtendRoute(IEnumerable<Point> Route)
        {
            // Itterate through each possible move
            foreach (var NextMove in PossibleMoves(Route.Last()))
            {
                // Create a copy of the route, and add this possible move to it.
                List<Point> NextMoveRoute = new List<Point>(Route);
                NextMoveRoute.Add(NextMove);
                yield return NextMoveRoute;
            }
        }

        static IEnumerable<Point> PossibleMoves(Point P)
        {
            List<Point> Result = new List<Point>();

            Result.Add(new Point(P.X + 1, P.Y + 2));
            Result.Add(new Point(P.X - 1, P.Y + 2));
            Result.Add(new Point(P.X + 1, P.Y - 2));
            Result.Add(new Point(P.X - 1, P.Y - 2));

            Result.Add(new Point(P.X + 2, P.Y + 1));
            Result.Add(new Point(P.X - 2, P.Y + 1));
            Result.Add(new Point(P.X + 2, P.Y - 1));
            Result.Add(new Point(P.X - 2, P.Y - 1));

            Result.RemoveAll(PossibleMove => PossibleMove.X < 0 || PossibleMove.X > GridSize ||
                                             PossibleMove.Y < 0 || PossibleMove.Y > GridSize);

            return Result as IEnumerable<Point>;
        }
    }
}

Answer 2

Although depth-first search will work, I think you can do this better (faster) with a breadth first search since you don't actually need to generate the moves, you just need to count the number of moves.

If you can create a matrix containing the number of counts of possible branches when you do on (n-1)th movements, then you can use that to calculate the counts of possible branches for nth movement.

At iteration 0, the matrix is simply a matrix of ones since you haven't moved your pieces yet:

    table0

   1 1 1 1
   1 1 1 1
   1 1 1 1
   1 1 1 1

Let's name the table above table0 since this is the 0th move. To obtain table1 from table0, you do table1[r1c1] = table0[r2c3] + table0[r3c2] since r1c1 can reached only by knights in r2c3 and r3c2, another example, to find table1[r2c2] = table0[r1c4] + table0[r3c4] + table0[r4c3] + table0[r4c1] since r2c2 can only be reached by knights in r1c4, r3c4, r4c3, r4c1. And so on.

Using this algorithm, the next few values of the table are so:

    table1

   2 3 3 2
   3 4 4 3
   3 4 4 3
   2 3 3 2




    table2

   8 10 10  8
  10 10 10 10
  10 10 10 10
   8 10 10  8




    table3

  20 30 30 20
  30 36 36 30
  30 36 36 30
  20 30 30 20




    table4

  72  96  96 72
  96 100 100 96
  96 100 100 96
  72  96  96 72



    table5

  200 292 192 200
  192 336 336 192
  192 336 336 192
  200 192 192 200

So basically in this 4x4 game, this will be the formula for calculating the next grid:

last = table from previous iteration
next = create new table of zeros

// corners
next[r1c1] = last[r2c3] + last[r3c2]
next[r1c4] = last[r2c2] + last[r3c3]
next[r4c1] = last[r2c3] + last[r3c2]
next[r4c4] = last[r3c3] + last[r3c3]

// sides, clockwise
next[r1c2] = last[r3c1] + last[r3c3] + last[r2c4]
next[r1c3] = last[r3c2] + last[r3c4] + last[r2c1]
next[r2c4] = last[r1c2] + last[r3c2] + last[r4c3]
next[r3c4] = last[r2c2] + last[r4c2] + last[r1c3]
next[r4c3] = last[r2c2] + last[r2c4] + last[r3c1]
next[r4c2] = last[r2c1] + last[r2c3] + last[r3c4]
next[r3c1] = last[r2c3] + last[r4c3] + last[r1c2]
next[r2c1] = last[r1c3] + last[r3c3] + last[r4c2]

// middle four
next[r2c2] = last[r1c4] + last[r3c4] + last[r4c1] + last[r4c3]
next[r2c3] = last[r1c1] + last[r3c1] + last[r4c2] + last[r4c4]
next[r3c2] = last[r1c1] + last[r1c3] + last[r2c4] + last[r4c4]
next[r3c3] = last[r2c1] + last[r4c1] + last[r1c2] + last[r1c4]

This will take constant memory O(1), and the number of operations is linear O(n) depending on the number of moves. Note: you need to check that this algorithm actually works, I haven't given much thought about whether it correctly calculates the counts.