This program was written on Windows 7 using Visual Studio 2012 Professional. Some of the issues encountered may have been fixed or changed in a more recent version.
This is a quote from my second question in response to a comment made below:
The algorithm in KnightMovesImplementation.cs implements a recursive tree search for all possible paths of a Knight on a Chess Board from point A to point B with the given restrictions of board size and slicing . The tree is implemented as a recursive algorithm rather than a data structure. The data structures used in the algorithm are paths (a collection of moves from the origin to the destination), moves (the 8 possi ble moves a Knight can make on a Chess Board), and locations (squares on the chessboard represented by row number and column number).
Slicing can be either the Knight can't visit a previously visited row or column on the board, or the Knight can't visit a previously visited square on the board.
My second question here on Code Review is here. It was as a request for review of my C++ and as an answer to this question. The author of that question asked me if I could provide a solution in C# since he was first learning C# and didn't know C++. I hope he didn't hold his breath waiting because that was 3 months ago, but here is my C# version. To write this solution I had to take a detour and refactor my original post which I asked last week.
Only three main files are shown here. You can find the entire program on GitHub. The three files are the core algorithm (KnightMoveImplementation and KMMoveFilters) and the Program.cs file.
Since it is my first C# program, I'd really love someone to dissect it and tell me all the things I can do to improve it.
Sample Output
Do you want to print each of the resulting paths? (y/n) Select the number of the test case you want to run. Test Case # Start Name Target Name Board Size Slicing Method 1 A3 H4 8 Can't return to previous row or column 2 A1 H8 8 Can't return to previous row or column 3 A8 H1 8 Can't return to previous row or column 4 B3 H4 8 Can't return to previous row or column 5 B3 H8 8 Can't return to previous row or column 6 C1 H4 8 Can't return to previous row or column 7 A3 H8 8 Can't return to previous row or column 8 A3 H4 8 Can't return to previous row or column 9 H4 A3 8 Can't return to previous row or column 10 D4 A8 8 Can't return to previous row or column 11 D4 E6 8 Can't return to previous row or column 12 A3 B5 8 Can't return to previous row or column 13 A3 B5 13 Can't return to previous row or column 14 A3 B5 8 Can't return to previous location 15 A3 B5 26 Can't return to previous row or column 16 All of the above except for 15 and 14 17 All of the above (Go get lunch) finished computation at 7/1/2016 12:57:41 PM elapsed time: 0.0144886 Seconds The point of origin for all path searches was A3 The destination point for all path searches was H4 The number of squares on each edge of the board is 8 The slicing methodology used to further limit searches was no repeat visits to any rows or columns. There are 5 Resulting Paths There were 276 attempted paths The average path length is 4.8 The median path length is 4 The longest path is 6 moves. The shortest path is 4 moves. ######################### End of Test Case A3 to H4######################### finished computation at 7/1/2016 12:57:41 PM elapsed time: 0.0006995 Seconds The point of origin for all path searches was A1 The destination point for all path searches was H8 The number of squares on each edge of the board is 8 The slicing methodology used to further limit searches was no repeat visits to any rows or columns. There are 18 Resulting Paths There were 138 attempted paths The average path length is 6 The median path length is 6 The longest path is 6 moves. The shortest path is 6 moves. ######################### End of Test Case A1 to H8######################### finished computation at 7/1/2016 12:57:41 PM elapsed time: 0.0018398 Seconds The point of origin for all path searches was B3 The destination point for all path searches was H4 The number of squares on each edge of the board is 8 The slicing methodology used to further limit searches was no repeat visits to any rows or columns. There are 7 Resulting Paths There were 330 attempted paths The average path length is 4.71428571428571 The median path length is 5 The longest path is 5 moves. The shortest path is 3 moves. ######################### End of Test Case B3 to H4#########################
KnightMovesImplementation.cs
using System;
using System.Collections.Generic;
namespace KnightMoves_CSharp
{
class KnightMovesImplementation {
/*
* This class provides the search for all the paths a Knight on a chess
* board can take from the point of origin to the destination. It
* implements a modified Knights Tour. The classic knights tour problem
* is to visit every location on the chess board without returning to a
* previous location. That is a single path for the knight. This
* implementation returns all possible paths from point a to point b.
*
* The current implementation is a Recursive Breadth First Search. Conceptually
* the algorithm implements a B+ tree with a maximum of 8 possible branches
* at each level. The root of the tree is the point of origin. A particular
* path terminates in a leaf. A leaf is the result of either reaching the
* destination, or reaching a point where there are no more branches to
* traverse.
*
* The public interface CalculatePaths establishes the root and creates
* the first level of branching. The protected interface CalculatePath
* performs the recursive depth first search, however, the
* MoveFilters.GetPossibleMoves() function it calls performs a breadth
* first search of the current level.
*/
KMBoardLocation PointOfOrigin;
KMBoardLocation Destination;
uint SingleSideBoardDimension;
KnightMovesMethodLimitations PathLimitations;
KMOutputData Results;
KMMoveFilters MoveFilter;
KMPath m_Path;
public KnightMovesImplementation(KMBaseData UserInputData)
{
SingleSideBoardDimension = UserInputData.DimensionOneSide;
PathLimitations = UserInputData.LimitationsOnMoves;
InitPointOfOrigin(UserInputData);
InitDestination(UserInputData);
Results = new KMOutputData(PointOfOrigin, Destination, SingleSideBoardDimension, PathLimitations);
MoveFilter = new KMMoveFilters(PointOfOrigin, SingleSideBoardDimension, PathLimitations);
m_Path = new KMPath();
}
public KMOutputData CalculatePaths()
{
List<KMMove> PossibleFirstMoves = MoveFilter.GetPossibleMoves(PointOfOrigin);
if (PossibleFirstMoves.Count == 0)
{
// Anywhere on the board should have at between 2 and 8 possible moves
throw new ApplicationException("KnightMovesImplementation::CalculatePaths: No Possible Moves.");
}
else
{
foreach (KMMove CurrentMove in PossibleFirstMoves)
{
CurrentMove.SetOriginCalculateDestination(PointOfOrigin);
if (CurrentMove.IsValid() == true) {
CalculatePath(CurrentMove);
}
}
}
return Results;
}
protected void InitPointOfOrigin(KMBaseData UserInputData)
{
PointOfOrigin = new KMBoardLocation(UserInputData.StartRow, UserInputData.StartColumn, SingleSideBoardDimension);
PointOfOrigin.SetName(UserInputData.StartName);
}
protected void InitDestination(KMBaseData UserInputData)
{
Destination = new KMBoardLocation(UserInputData.TargetRow, UserInputData.TargetColumn, SingleSideBoardDimension);
Destination.SetName(UserInputData.TargetName);
}
/*
* Recursive algorith that performs a depth search.
* The call to CurrentMove.GetNextLocation() implements the breadth-first portion
* of the search.
*/
protected void CalculatePath(KMMove CurrentMove)
{
KMBoardLocation CurrentLocation = CurrentMove.GetNextLocation();
m_Path.AddMoveToPath(CurrentMove);
MoveFilter.PushVisited(CurrentLocation);
if (Destination.IsSameLocation(CurrentLocation) == true)
{
Results.IncrementAttemptedPaths();
Results.AddPath(m_Path);
}
else
{
if (CurrentMove.IsValid() == true)
{
List<KMMove> PossibleMoves = MoveFilter.GetPossibleMoves(CurrentLocation);
if (PossibleMoves.Count != 0)
{
foreach (KMMove NextMove in PossibleMoves)
{
CalculatePath(NextMove);
}
}
else
{
Results.IncrementAttemptedPaths();
}
}
else
{
throw new ApplicationException("In KnightMovesImplementation::CalculatePath CurrentLocation Not Valid");
}
}
// Backup to previous location
MoveFilter.PopVisited();
m_Path.RemoveLastMove();
}
};
}
KMMoveFilters.cs
using System;
using System.Collections.Generic;
namespace KnightMoves_CSharp
{
/*
* This class provides all the possible Knight moves for a specified location
* on the chess board. In the center of the chess board there are 8 possible
* moves. In the middle of the edge on the chess board there are 4 possible
* moves. In a corner of the chess board there are 2 possible moves. The
* location on the board provides the first filter.
* Slicing is used to allow the program to complete in a reasonable finite
* amount of time. The slicing method can be varied, the default slicing
* method is the knight can't return to any row or column it has previously
* visited. The slicing is the second filter.
*/
public class KMMoveFilters {
private struct LocationBase { public uint Row; public uint Column; }
// The 8 possible moves the knight can make.
public static int MAIXMUM_POSSIBLE_MOVES = 8;
private KMMove Left1Up2;
private KMMove Left2Up1;
private KMMove Left2Down1;
private KMMove Left1Down2;
private KMMove Right1Up2;
private KMMove Right2Up1;
private KMMove Right2Down1;
private KMMove Right1Down2;
const int Left1 = -1;
const int Left2 = -2;
const int Down1 = -1;
const int Down2 = -2;
const int Right1 = 1;
const int Right2 = 2;
const int Up1 = 1;
const int Up2 = 2;
List<KMMove> AllPossibleMoves = new List<KMMove>();
private uint BoardDimension;
public uint GetBoardDimension() { return BoardDimension; }
KnightMovesMethodLimitations PathLimitations;
Stack<LocationBase> VisitedLocations = new Stack<LocationBase>();
Stack<uint> VisitedRows = new Stack<uint>();
Stack<uint> VisitedColumns = new Stack<uint>();
public KMMoveFilters(KMBoardLocation Origin, uint SingleSideBoardDimension, KnightMovesMethodLimitations VisitationLimitations)
{
PathLimitations = VisitationLimitations;
BoardDimension = SingleSideBoardDimension;
Left1Up2 = new KMMove(Left1, Up2, BoardDimension);
Left2Up1 = new KMMove(Left2, Up1, BoardDimension);
Left2Down1 = new KMMove(Left2, Down1, BoardDimension);
Left1Down2 = new KMMove(Left1, Down2, BoardDimension);
Right1Up2 = new KMMove(Right1, Up2, BoardDimension);
Right2Up1 = new KMMove(Right2, Up1, BoardDimension);
Right2Down1 = new KMMove(Right2, Down1, BoardDimension);
Right1Down2 = new KMMove(Right1, Down2, BoardDimension);
AllPossibleMoves.Add(Left1Up2);
AllPossibleMoves.Add(Left2Up1);
AllPossibleMoves.Add(Left2Down1);
AllPossibleMoves.Add(Left1Down2);
AllPossibleMoves.Add(Right1Up2);
AllPossibleMoves.Add(Right2Up1);
AllPossibleMoves.Add(Right2Down1);
AllPossibleMoves.Add(Right1Down2);
// Record the initial location so we never return
LocationBase PtOfOrigin = new LocationBase();
PtOfOrigin.Row = Origin.GetRow();
PtOfOrigin.Column = Origin.GetColumn();
VisitedLocations.Push(PtOfOrigin);
}
/*
* C# does not seem to provide a default copy constructor so copy AllPossibleMoves
*/
private List<KMMove> GetAllPossibleMoves() { return CopyAllPossibleMoves(); }
private List<KMMove> CopyAllPossibleMoves()
{
List<KMMove> PublicCopy = new List<KMMove>();
foreach (KMMove PossibleMove in AllPossibleMoves)
{
PublicCopy.Add(new KMMove(PossibleMove));
}
return PublicCopy;
}
public List<KMMove> GetPossibleMoves(KMBoardLocation Origin)
{
if (Origin.IsValid() == false)
{
throw new ArgumentException("KMMoveFilters::GetPossibleMoves : Parameter Origin is not valid!\n");
}
List<KMMove> TempAllPossibleMoves = GetAllPossibleMoves();
List<KMMove> PossibleMoves = new List<KMMove>();
foreach (KMMove PossibeMove in TempAllPossibleMoves)
{
PossibeMove.SetOriginCalculateDestination(Origin);
if ((PossibeMove.IsValid() == true) && (IsNotPreviouslyVisited(PossibeMove.GetNextLocation()) == true))
{
PossibleMoves.Add(PossibeMove);
}
}
return PossibleMoves;
}
protected bool IsNotPreviouslyVisited(KMBoardLocation PossibleDestination)
{
bool NotPrevioslyVisited = true;
LocationBase PossibleLocation;
PossibleLocation.Row = PossibleDestination.GetRow();
PossibleLocation.Column = PossibleDestination.GetColumn();
// We can't ever go back to a previously visited location
if (VisitedLocations.Count != 0)
{
if (VisitedLocations.Contains(PossibleLocation) == true)
{
NotPrevioslyVisited = false;
}
}
switch (PathLimitations)
{
default:
throw new ArgumentException("KMPath::CheckMoveAgainstPreviousLocations : Unknown type of Path Limitation.");
case KnightMovesMethodLimitations.DenyByPreviousLocation:
// Handled above by VisitedLocations.Contains().
break;
case KnightMovesMethodLimitations.DenyByPreviousRowOrColumn:
if ((VisitedRows.Count != 0) && (VisitedColumns.Count != 0))
{
if (VisitedRows.Contains(PossibleDestination.GetRow()) == true)
{
NotPrevioslyVisited = false;
break;
}
if (VisitedColumns.Contains(PossibleDestination.GetColumn()) == true)
{
NotPrevioslyVisited = false;
break;
}
}
break;
}
return NotPrevioslyVisited;
}
public void PushVisited(KMBoardLocation Location)
{
LocationBase TestLocation = new LocationBase();
TestLocation.Row = Location.GetRow();
TestLocation.Row = Location.GetRow();
VisitedLocations.Push(TestLocation);
VisitedRows.Push(Location.GetRow());
VisitedColumns.Push(Location.GetColumn());
}
public void PopVisited()
{
VisitedRows.Pop();
VisitedColumns.Pop();
VisitedLocations.Pop();
}
};
}
Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;
namespace KnightMoves_CSharp
{
class Program
{
static void OutputOverAllStatistics(List<double> TestTimes)
{
if (TestTimes.Count < 1) // Prevent Division by 0 in Average
{
Console.WriteLine("No test times to run statistics on!");
return;
}
TestTimes.Sort(); // Sort once for Min, Median and Max
Console.WriteLine("\nOverall Results");
Console.WriteLine("The average execution time is {0} seconds.", TestTimes.Average());
Console.WriteLine("The median execution time is {0} seconds.", TestTimes[TestTimes.Count() / 2]);
Console.WriteLine("The longest execution time is {0} seconds.", TestTimes[TestTimes.Count - 1]);
Console.WriteLine("The shortest execution time is {0} seconds.", TestTimes[0]);
}
static double ExecutionLoop(KMBaseData UserInputData, bool ShowPathData)
{
Stopwatch StopWatch = new Stopwatch();
KnightMovesImplementation KnightPathFinder = new KnightMovesImplementation(UserInputData);
StopWatch.Start();
KMOutputData OutputData = KnightPathFinder.CalculatePaths();
StopWatch.Stop();
TimeSpan ts = StopWatch.Elapsed;
Double ElapsedTimeForOutPut = ts.TotalSeconds;
Console.Write("finished computation at ");
Console.WriteLine(DateTime.Now);
Console.WriteLine("elapsed time: {0} Seconds", ElapsedTimeForOutPut);
Console.WriteLine();
Console.WriteLine();
OutputData.ShowPathData(ShowPathData);
OutputData.ShowResults();
return ElapsedTimeForOutPut;
}
static void Main(string[] args)
{
bool ShowPathData = false;
Console.WriteLine("Do you want to print each of the resulting paths? (y/n)");
string ShowPathAnswer = Console.ReadLine();
ShowPathData = (ShowPathAnswer.ToLower() == "y");
KMTestData TestData = new KMTestData();
List<KMBaseData> ListOfTestCases = TestData.LetUserEnterTestCaseNumber();
try
{
List<double> TestTimes = new List<double>();
foreach (KMBaseData TestCase in ListOfTestCases)
{
TestTimes.Add(ExecutionLoop(TestCase, ShowPathData));
GC.Collect();
}
OutputOverAllStatistics(TestTimes);
return;
}
catch (ArgumentOutOfRangeException e)
{
Console.Error.Write("A fatal range error occurred in KnightMoves: ");
Console.Error.WriteLine(e.ToString());
return;
}
catch (ArgumentException e)
{
Console.Error.Write("A fatal argument error occurred in KnightMoves: ");
Console.Error.WriteLine(e.ToString());
return;
}
catch (ApplicationException e)
{
Console.Error.Write("A fatal application error occurred in KnightMoves: ");
Console.Error.WriteLine(e.ToString());
return;
}
}
}
}
