3
\$\begingroup\$

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;
            }
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ Could you explain what the program is supposed to do? I mean what input does it expect and what does it do with it? I understand it calculates knight moves but from where to where etc? The general idea behind it. \$\endgroup\$ – t3chb0t Jul 2 '16 at 18:03
  • 1
    \$\begingroup\$ @t3chb0t I've copied what the program does from my original question. It is now in the body of the question. \$\endgroup\$ – pacmaninbw Jul 2 '16 at 20:16
  • 2
    \$\begingroup\$ Is this really breadth-first? Breadth-first searches are rarely done recursively. \$\endgroup\$ – 200_success Jul 2 '16 at 20:27
  • \$\begingroup\$ @200_success The function KMMoveFilters::GetPossibleMoves() does a one step search to the next level. I was debating the issue myself and looked both breadth first and depth first on Wikipedia, by the articles I found it is breadth first. \$\endgroup\$ – pacmaninbw Jul 2 '16 at 20:31
  • \$\begingroup\$ @t3chb0t I have added what I hope are meaningful comments to the code, they existed in the refactored C++ version but were missing in this version. The GitHub version has also been updated. \$\endgroup\$ – pacmaninbw Jul 3 '16 at 16:59
2
\$\begingroup\$

Some unorganized comments:

NotPrevioslyVisited has a typo, should be NotPreviouslyVisited.


if (VisitedLocations.Count != 0)
{
    if (VisitedLocations.Contains(PossibleLocation) == true)
    {
        NotPrevioslyVisited = false;
    }
}

You can combine if statements here - and there's no need to explicitly check for true. if (VisitedLocations.Count != 0 && VisitedLocations.Contains(PossibleLocation)) will do.


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

No need for else here, you're throwing an exception. Put guard clauses separate from your code. Like so:

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.");
}

foreach (KMMove CurrentMove in PossibleFirstMoves)
{
    CurrentMove.SetOriginCalculateDestination(PointOfOrigin);
    if (CurrentMove.IsValid() == true) {
        CalculatePath(CurrentMove);
    }
}

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

A hiccup with indentation - and more == true checks. Also, else { if(){ } else { } structures can be converted to else if() { } else { } structures:

if (Destination.IsSameLocation(CurrentLocation))
{
    Results.IncrementAttemptedPaths();
    Results.AddPath(m_Path);
}
else if (CurrentMove.IsValid())
{
    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");
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.