Find all possible ways a rook can move to a diagonally opposite corner without going back to an already visited square

Question

This question seems similar to this one: Find number of unique paths to reach opposite grid corner but is entirely not. For moving from upper-left corner to lower-right corner we are not restricted to move only rightwards and downwards otherwise this will be a simple permutation and combination question instead.

I came up with the following very bruteforce method which works perfectly fine for a boardSize of 3 (meaning a (3x3) board), 4 and 5 giving 12, 184 and 8512 successfull paths respectively for reaching (boardSize, boardSize) from (1, 1). However the code takes forever for a board size of 6 onwards and I have to make it reach to a standard board size of 8 atleast.

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

namespace ChessProblem_StackOverFlow
{
    class Program
    {
        static void Main(string[] args)
        {
            Square currentRookPosition = new Square(1, 1);
            Square destinationPosition = new Square(Square.boardSize, Square.boardSize);    // (3, 3) as of now
            List<Path> paths = new List<Path>();
            List<Path> successfullPaths = new List<Path>();


            // One time initialization of "paths" List based on rook's starting position
            List<Square> possibleMoves = currentRookPosition.GetPossibleMoves();
            foreach (Square nextRookPosition in possibleMoves)
            {
                paths.Add(new Path(currentRookPosition, nextRookPosition));
            }


            while (paths.Any())
            {
                foreach (Path path in paths.ToList())
                {
                    Square lastSquare = path.visitedSquares[^1];
                    List<Square> nextPossibleMoves = lastSquare.GetPossibleMoves();


                    // For each nextPossibleMove check if it is already visited and if so remove it
                    foreach (Square nextPossibleMove in nextPossibleMoves.ToList())
                    {
                        foreach (Square visitedSquare in path.visitedSquares)
                        {
                            if (nextPossibleMove.Equals(visitedSquare))
                            {
                                nextPossibleMoves.RemoveAt(nextPossibleMoves.IndexOf(nextPossibleMove));
                                break;
                            }
                        }
                    }


                    // Add path to successfullPaths if destination reached
                    if (path.visitedSquares[^1].Equals(destinationPosition))
                    {
                        successfullPaths.Add(path);
                        paths.RemoveAt(paths.IndexOf(path));
                        break;
                    }

                    // Remove path from paths list if out of possible moves
                    if (!nextPossibleMoves.Any())
                    {
                        paths.RemoveAt(paths.IndexOf(path));
                        break;
                    }
                    else
                    {
                        foreach (Square nextPossibleMove in nextPossibleMoves)
                        {
                            // add first move in already running path
                            if (nextPossibleMove.Equals(nextPossibleMoves[0]))
                                path.visitedSquares.Add(new Square(nextPossibleMove.x, nextPossibleMove.y));
                            // create another path for other moves
                            else
                                paths.Add(new Path(path.visitedSquares, nextPossibleMove));
                        }
                    }
                }
            }


            // test
            foreach (Path path in successfullPaths)
            {
                foreach (Square visitedSquare in path.visitedSquares)
                {
                    Console.WriteLine(visitedSquare.x + ", " + visitedSquare.y);
                }
                Console.WriteLine("**********************************************************************");
            }
            Console.WriteLine("Number of successfull paths: " + successfullPaths.Count);
        }
    }
}

Here is my Square struct with only GetPossibleMoves() method which gives all possible moves irrespective of whether it is already visited or not, I am taking care of that in my Main() method.

struct Square
{
    public int x, y;
    public static int boardSize = 3;
    public Square(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
    public List<Square> GetPossibleMoves()
    {
        List<Square> possibleMoves = new List<Square>();
        if (x > 1)
            possibleMoves.Add(new Square(x - 1, y));
        if (x < boardSize)
            possibleMoves.Add(new Square(x + 1, y));
        if (y > 1)
            possibleMoves.Add(new Square(x, y - 1));
        if (y < boardSize)
            possibleMoves.Add(new Square(x, y + 1));
        return possibleMoves;
    }
}

And here is my Path class for keeping track of visitedSquares in any instance of this class.

class Path
{
    Square from, to;
    public List<Square> visitedSquares = new List<Square>();
    
    public Path(Square from, Square to)
    {
        this.from = from;
        this.to = to;
        visitedSquares.Add(new Square(from.x, from.y));
        visitedSquares.Add(new Square(to.x, to.y));
    }
    // another constructor
    public Path(List<Square> listToBeExtendedFrom, Square replaceLastSquareWith)
    {
        foreach(Square square in listToBeExtendedFrom)
        {
            visitedSquares.Add(new Square(square.x, square.y));
        }
        visitedSquares.Remove(visitedSquares[visitedSquares.Count - 1]);
        visitedSquares.Add(new Square(replaceLastSquareWith.x, replaceLastSquareWith.y));
    }
}

For a boardSize of 6, I let this program run for half an hour which used upto 6 GB of memory but didn't gave any output. How can I make this more efficient?

As @G. Sliepen and @pacmaninbw mentioned in this follow up question about Rook or king moves, the question meant to say as if we were tracing the rook's path, the rook isn't allowed to revisit an already visited square neither it is allowed to intersect it's own path. My bad I didn't already mentioned this but I pre assumed this as otherwise the question would have become really clumsy.

Answer 1

I would recommend that you change struct Square to record Square. This makes all the comparative stuff much easier.

Then you can change your Program class to the following which uses recursion to find the paths. I have also added a timer to show progress.

class Program
{
    static void GetPaths(List<Square> path, Square currentRookPosition, Square destinationPosition, int level)
    {
        path.Add(currentRookPosition);
        if (currentRookPosition == destinationPosition)
        {
            pathsFound++;
            return;
        }

        List<Square> possibleMoves = currentRookPosition.GetPossibleMoves();
        foreach (Square nextRookPosition in possibleMoves)
        {
            if (path.Contains(nextRookPosition) == false)
            {
                GetPaths(path.ToList(), nextRookPosition, destinationPosition, level + 1);
            }
        }
    }

    static void Main(string[] args)
    {
        sw.Start();
        using (var timer = new System.Timers.Timer(1000))
        {
            timer.Elapsed += ShowProgress;
            timer.Start();

            var currentRookPosition = new Square(1, 1);
            var destinationPosition = new Square(Square.boardSize, Square.boardSize);    // (3, 3) as of now
            var path = new List<Square>();
            GetPaths(path, currentRookPosition, destinationPosition, 0);
        }
        Console.WriteLine("Paths found = " + pathsFound);
    }

    private static void ShowProgress(object sender, System.Timers.ElapsedEventArgs e)
    {
        Console.WriteLine(String.Format("paths found = {0}, second = {1}", pathsFound, sw.ElapsedMilliseconds / 1000));
    }

    private static int pathsFound = 0;
    private static System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
}

This finds 1 262 816 paths for a 6x6 grid in about 20 seconds.

---

Here is a revised implementation that calculates a 6x6 grid in under a second using bitsets and pre-calculated moves:

using System;
using System.Collections.Generic;

namespace ChessProblem_StackOverFlow
{
    class Board
    {
        public Board(int cols, int rows)
        {
            this.cols = cols;
            this.rows = rows;
            this.squares = new int[cols * rows][];
            for (int y = 0; y < rows; y++)
            {
                for (int x = 0; x < cols; x++)
                {
                    squares[x + y * cols] = calcMoves(x, y);
                }
            }
        }

        int[] calcMoves(int x, int y)
        {
            var moves = new List<int>();
            if (x > 0)
                moves.Add(calcIndex(x - 1, y));
            if (x < cols - 1)
                moves.Add(calcIndex(x + 1, y));
            if (y > 0)
                moves.Add(calcIndex(x, y - 1));
            if (y < rows - 1)
                moves.Add(calcIndex(x, y + 1));
            return moves.ToArray();
        }

        public int calcIndex(int x, int y)
        {
            return x + y * cols;
        }

        public UInt64 calcBit(int index)
        {
            UInt64 one = 1;
            return one << index;
        }

        public int rows;
        public int cols;
        public int[][] squares;
    }

    class Program
    {
        static void GetPaths(UInt64 path, int currentRookPosition, int destinationPosition, int level)
        {
            path |= board.calcBit(currentRookPosition);
            if (currentRookPosition == destinationPosition)
            {
                pathsFound++;
                return;
            }

            foreach (int nextRookPosition in board.squares[currentRookPosition])
            {
                if ((UInt64)(path & board.calcBit(nextRookPosition)) == (UInt64)0)
                {
                    GetPaths(path, nextRookPosition, destinationPosition, level + 1);
                }
            }
        }

        static void Main(string[] args)
        {
            sw.Start();
            using (var timer = new System.Timers.Timer(1000))
            {
                timer.Elapsed += ShowProgress;
                timer.Start();

                int size = 6;
                board = new Board(size, size);
                var currentRookPosition = board.calcIndex(0, 0);
                var destinationPosition = board.calcIndex(board.cols - 1, board.rows - 1);
                
                UInt64 path = 0;
                GetPaths(path, currentRookPosition, destinationPosition, 0);
            }
            Console.WriteLine("Paths found = " + pathsFound);
        }

        private static void ShowProgress(object sender, System.Timers.ElapsedEventArgs e)
        {
            Console.WriteLine(String.Format("paths found = {0}, second = {1}", pathsFound, sw.ElapsedMilliseconds / 1000));
        }
        private static int pathsFound = 0;
        private static System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
        private static Board board;
    }
}

It took about 2 minutes to calculate 575 780 564 paths for a 7x7 grid. I will leave the 8x8 up to you...

PS. For my own amusement, I created a C++ version that is about 2 times faster than the C# one. Still waiting for the results for 8x8 :-)