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

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)
{
}

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))
{
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)
{
if (nextPossibleMove.Equals(nextPossibleMoves[0]))
// create another path for other moves
else
}
}
}
}

// 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)
if (x < boardSize)
if (y > 1)
if (y < boardSize)
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;
}
// another constructor
public Path(List<Square> listToBeExtendedFrom, Square replaceLastSquareWith)
{
foreach(Square square in listToBeExtendedFrom)
{
}
visitedSquares.Remove(visitedSquares[visitedSquares.Count - 1]);
}
}


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.

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)
{
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)
if (x < cols - 1)
if (y > 0)
if (y < rows - 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 :-)

• Wow, that's a HUUUUGE upgrade, but still far from achieving 8*8. Seems like the number will be really really monstrous. Will try implementing your suggestions. Nov 5, 2021 at 16:36
• I changed struct to record and let the recursion version run overnight for 7x7 grid. The last line was Paths found = 575780564, second = 23135. 6 hours compared to 2 minutes!!! Orz I am just a beginner and this is getting overwhelmingly good. Nov 6, 2021 at 8:53
• @Prince, cool! I have posted a follow up question that you may want to keep an eye on =)
– jdt
Nov 6, 2021 at 13:01
• @pacmaninbw, I agree and I think that if there is any way to speed this up fundamentally, the same logic should be applicable to the C# version. I posted the C++ version to attract a different audience and see what they can come up with =)
– jdt
Nov 6, 2021 at 14:42
• Yes, and some of the things pointed out in the answer will help this C# question as well. Especially prune early. Nov 6, 2021 at 14:48