Recursive Breadth First Search for Knights Tour

Question

This was written as an experiment in performance, based on another question here on CodeReview. Input into the algorithm is the number of squares on one edge of the chess board, the point of origin, the destinat ion and the type of slicing (imposing restrictions on the search to allow it to complete in a reasonable finite time). The program is written in C++ using the C++11 standard as implemented by the GNUg++ compiler in Centos 7.

The algorithm in KnightMovesImplementation.cpp 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.

Board size can be varied from 8 squares on a side up to 26 squares on a side.

This development and testing was done on a Dell M6400 Laptop (Intel Core 2 Duo) running Centos 7, g++ compiler, compiler switches -g3 (debugging). (machine bought August 2009 with Windows XP)

Besides multi-threading, what are possible optimizations? I plan to try this with multi-threading. How can I improve my use of C++11? How can I reduce the coupling between classes? I used 3 typedefs in KMPath.h, are these considered bad form now?

Average time on an 8 by 8 chess board is under 2 hundreths of a second, the one test on a 12 by 12 chessboard took 0.127273 seconds. The single test on a 26 by 26 board was over 85 minutes, here are some of the output results:

finished computation at Mon Mar 21 10:41:41 2016
elapsed time: 5116.61 seconds (85.2768 minutes)


The point of origin for all path searches was  A3
The destination point for all path searches was  B5
The number of squares on each edge of the board is 26
The slicing methodology used to further limit searches was no repeat visits rows or columns.
There are 6 Resulting Paths
There were 96929021 attempted paths
The average path length is 3
The median path length is 3
The longest path is 5 moves
The shortest path is 1 moves
-------------------------

finished computation at Mon Mar 21 09:16:24 2016
elapsed time: 0.0162263 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 rows or columns.
There are 5 Resulting Paths
There were 671 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
-------------------------

finished computation at Mon Mar 21 09:16:24 2016
elapsed time: 0.00716998 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 rows or columns.
There are 22 Resulting Paths
There were 341 attempted paths
The average path length is 6.36364
The median path length is 6
The longest path is 8 moves
The shortest path is 6 moves
-------------------------

KnightMovesImplementation.h

#ifndef KNIGHTMOVESIMPLEMENTATION_H_
#define KNIGHTMOVESIMPLEMENTATION_H_

#include "KMPath.h"
#include "KMOutputData.h"

class KnightMovesImplementation {
private:
    KMBoardLocation m_PointOfOrigin;
    KMBoardLocation m_Destination;
    unsigned int m_SingleSideBoardDimension;    // Should this be a static member of a common base class?
    KnightMovesMethodLimitations m_PathLimitations;
    KMOutputData m_Results;
    KMRandomAccessMoveCollection m_AllPossibleMoves;

protected:
    bool CalculatePath(KMPath CurrentPath);        // Recursive function
    KMPath TryNextMove(KMMove CurrentMove, KMPath CurrentPath);
    void InitPointOfOrigin(KnightMovesBaseData UserData);
    void InitDestination(KnightMovesBaseData UserData);

public:
    KnightMovesImplementation();
    KnightMovesImplementation(KnightMovesBaseData UserData);
    virtual ~KnightMovesImplementation() = default;
    KMOutputData CalculatePaths();
};

#endif /* KNIGHTMOVESIMPLEMENTATION_H_ */

KnightMovesImplementation.cpp

#include "KnightMovesImplementation.h"
#include "KMBoardDimensionConstants.h"

KnightMovesImplementation::KnightMovesImplementation()
 : m_SingleSideBoardDimension{DefaultBoardDimensionOnOneSide},
   m_PathLimitations{DenyByPreviousRowOrColumn}
{
}

KnightMovesImplementation::KnightMovesImplementation(KnightMovesBaseData UserInputData)
{
    m_SingleSideBoardDimension = UserInputData.m_DimensionOneSide;
    m_PathLimitations = UserInputData.m_LimitationsOnMoves;
    InitPointOfOrigin(UserInputData);
    InitDestination(UserInputData);
    KMPossibleMoves PossibleMoves(UserInputData.m_DimensionOneSide);
    m_AllPossibleMoves = PossibleMoves.AllPossibleMoves;
}

void KnightMovesImplementation::InitPointOfOrigin(KnightMovesBaseData UserInputData)
{
    m_PointOfOrigin.SetRow(UserInputData.m_StartRow);
    m_PointOfOrigin.SetColumn(UserInputData.m_StartColumn);
    m_PointOfOrigin.SetName(UserInputData.m_StartName);
    m_PointOfOrigin.SetBoardDimension(m_SingleSideBoardDimension);
}

void KnightMovesImplementation::InitDestination(KnightMovesBaseData UserInputData)
{
    m_Destination.SetRow(UserInputData.m_TargetRow);
    m_Destination.SetColumn(UserInputData.m_TargetColumn);
    m_Destination.SetName(UserInputData.m_TargetName);
    m_Destination.SetBoardDimension(m_SingleSideBoardDimension);
}

KMOutputData KnightMovesImplementation::CalculatePaths()
{
    KMPath FirstPath(m_PointOfOrigin, m_Destination, m_SingleSideBoardDimension, m_PathLimitations);
    KMRandomAccessMoveCollection PossibleFirstMoves = FirstPath.GetPossibleMoves(m_PointOfOrigin);
    m_Results.IncrementAttemptedPaths();

    if (PossibleFirstMoves.empty())
    {
        std::cerr << "No Possible Moves in KnightMovesImplementation::CalculatePaths" << std::endl;
    }
    else
    {
        for (auto CurrentMoveIter : PossibleFirstMoves)
        {
            KMMove CurrentMove = CurrentMoveIter;
            CurrentMove.SetOriginCalculateDestination(m_PointOfOrigin);
            if (CurrentMove.IsValid()) {
                /**
                 * This might be a good place to improve performance by
                 * using multiple threads.
                 */
                CalculatePath(TryNextMove(CurrentMove, FirstPath));
            }
        }
    }
    m_Results.SetPointOfOrigin(m_PointOfOrigin);
    m_Results.SetDestination(m_Destination);
    m_Results.SetBoardDimension(m_SingleSideBoardDimension);
    m_Results.SetSlicingMethod(m_PathLimitations);
    return m_Results;
}

/**
 * Performs a breadth first search, trimming all invalid branches at this level
 * before searching deeper.
 */
bool KnightMovesImplementation::CalculatePath(KMPath CurrentPath)
{
    bool CompletedSearch = false;
    KMBoardLocation NewPointOfOrigin;
    KMRandomAccessMoveCollection PossibleMoves;

    if (CurrentPath.HasKnightArrivedAtDestination())
    {
        m_Results.AddPath(CurrentPath);
        return (CompletedSearch = true);
    }

    KMMove LastMove = CurrentPath.GetLastMove();
    if (LastMove.IsValid())
    {
        PossibleMoves = CurrentPath.GetPossibleMoves(LastMove);
    }
    else
    {
        // There is a logic error if we get here.
        std::cerr << "In KnightMovesImplementation::CalculatePath Path not started" << std::endl;
        return CompletedSearch;
    }

    if (PossibleMoves.empty())
    {
        CurrentPath.SetInvalid();
        CompletedSearch = false;
    }
    else
    {
        for (auto CurrentMoveIter : PossibleMoves)
        {
            CalculatePath(TryNextMove(CurrentMoveIter, CurrentPath));
        }
    }

    return CompletedSearch;
}

KMPath KnightMovesImplementation::TryNextMove(KMMove CurrentMove, KMPath CurrentPath)
{
    /**
     * Maintain the history of where we have been, but start a new search
     * from our current location.
     */
    KMPath NewPath(CurrentPath);
    if (CurrentMove.IsValid()) {
        NewPath.AddMoveToPath(CurrentMove);
        m_Results.IncrementAttemptedPaths();
    }
    else {
        std::cerr << "Current Move is Invalid " << CurrentMove << std::endl;
    }

    return NewPath;
}

KMPath.h

#ifndef KMPATH_H_
#define KMPATH_H_

#include "KMBoardLocation.h"
#include "KMMove.h"
#include "KnightMoves.h"
#include "KMPossibleMoves.h"

class KMPath : public KMPossibleMoves {
private:
    KMBoardLocation m_PointOfOrigin;
    KMBoardLocation m_Destination;
    using KMPossibleMoves::m_SingleSideBoardDimension;
    bool m_ReachedDestination;
    bool m_Valid;
    unsigned int m_PathLength;
    KnightMovesMethodLimitations m_PathLimitations;
    std::vector<KMBoardLocation> m_VisitedLocations;
    std::vector<unsigned int> m_VisitedRows;
    std::vector<unsigned int> m_VisitedColumns;
    KMFastAccessMoveCollection m_RecordOfMoves;

protected:
    bool IsNotPreviouslyVisited(KMMove Move) { return IsNotPreviouslyVisited(Move.GetNextLocation()); };
    bool IsNotPreviouslyVisited(KMBoardLocation Destination);

public:
    KMPath();
    KMPath(KMBoardLocation Origin, KMBoardLocation Destination, int BoardDimension, KnightMovesMethodLimitations PathLimitations);
    KMPath(const KMPath &Original);
    virtual ~KMPath() = default;
    void AddMoveToPath(KMMove Move);
    bool HasKnightArrivedAtDestination(KMBoardLocation Origin) { m_ReachedDestination = (Origin == m_Destination); return m_ReachedDestination; }
    bool HasKnightArrivedAtDestination() const { return m_ReachedDestination; }
    unsigned int GetLength() const { return m_PathLength; }
    KMFastAccessMoveCollection GetRecordOfMoves() const { return m_RecordOfMoves; }
    KMRandomAccessMoveCollection GetPossibleMoves(KMBoardLocation Origin);
    KMRandomAccessMoveCollection GetPossibleMoves(KMMove CurrentMove) {return GetPossibleMoves(CurrentMove.GetNextLocation()); };
    KMMove GetLastMove();
    void SetInvalid() { m_Valid = false; }
    void SetValid() { m_Valid = true; }
    bool IsValid() const { return m_Valid; }
    friend std::ostream &operator<<( std::ostream &output, KMPath &Path)
    {
        output << " " << Path.GetLength() << std::endl;
        KMFastAccessMoveCollection RecordOfMoves = Path.GetRecordOfMoves();
        for (auto PathIter: RecordOfMoves) {
            output << PathIter << std::endl;
        }
        return output;
    }
};

#endif /* KMPATH_H_ */

KMPath.cpp

#include <stdexcept>
#include <algorithm>
#include "KMPath.h"
#include "KMBoardDimensionConstants.h"

KMPath::KMPath()
: //m_SingleSideBoardDimension{DefaultBoardDimensionOnOneSide},
  m_ReachedDestination{false},
  m_Valid{false},
  m_PathLength{0},
  m_PathLimitations{DenyByPreviousRowOrColumn}
{
    m_SingleSideBoardDimension = DefaultBoardDimensionOnOneSide;
}

KMPath::KMPath(KMBoardLocation Origin, KMBoardLocation Destination, int BoardDimension, KnightMovesMethodLimitations PathLimitations)
: m_ReachedDestination{false},
  m_Valid{false},
  m_PathLength{0},
  m_PathLimitations{PathLimitations}
{
    m_PointOfOrigin = Origin;
    m_Destination = Destination;
    m_SingleSideBoardDimension = BoardDimension;
    UpdateDimension(m_SingleSideBoardDimension);
}

KMPath::KMPath(const KMPath &Original)
{
    m_SingleSideBoardDimension = Original.m_SingleSideBoardDimension;
    m_Valid = Original.m_Valid;
    m_ReachedDestination = Original.m_ReachedDestination;
    m_PathLength = Original.m_PathLength;
    m_PathLimitations = Original.m_PathLimitations;
    m_PointOfOrigin = Original.m_PointOfOrigin;
    m_Destination = Original.m_Destination;
    m_VisitedLocations = Original.m_VisitedLocations;
    m_VisitedRows = Original.m_VisitedRows;
    m_VisitedColumns = Original.m_VisitedColumns;
    m_RecordOfMoves = Original.m_RecordOfMoves;
}

KMRandomAccessMoveCollection KMPath::GetPossibleMoves(KMBoardLocation Origin)
{
    /**
     * ValidPossibleMoves contain the moves that are on the board, we
     * then need to see if the destination has been previously visited.
     */
    KMRandomAccessMoveCollection ValidPossibleMoves = GetOnlyValidPossibleMoves(Origin);
    KMRandomAccessMoveCollection PossibleMoves;
    for (auto APossibeMove : ValidPossibleMoves) {
        KMMove ThisPossibleMove = APossibeMove;
        if (IsNotPreviouslyVisited(ThisPossibleMove)) {
            PossibleMoves.push_back(ThisPossibleMove);
        }
    }
    return PossibleMoves;
}

bool KMPath::IsNotPreviouslyVisited(KMBoardLocation PossibleDestination)
{
    bool NotPrevioslyVisited = true;

    switch (m_PathLimitations) {
    default :
        throw std::runtime_error("KMPath::CheckMoveAgainstPreviousLocations : Unknown type of Path Limitation.");
    case DenyByPreviousLocation :
        if (!m_VisitedLocations.empty()) {
            if (std::find(m_VisitedLocations.begin(), m_VisitedLocations.end(), PossibleDestination)
                != m_VisitedLocations.end()) {
                NotPrevioslyVisited = false;
            }
        }
        break;
    case DenyByPreviousRowOrColumn:
        if ((!m_VisitedRows.empty()) && (!m_VisitedColumns.empty())) {
            unsigned int PossibleRow = PossibleDestination.GetRow();
            if (std::find(m_VisitedRows.begin(), m_VisitedRows.end(), PossibleRow) != m_VisitedRows.end()) {
                NotPrevioslyVisited = false;
                break;
            }
            unsigned int PossibleColum = PossibleDestination.GetColumn();
            if (std::find(m_VisitedColumns.begin(), m_VisitedColumns.end(), PossibleColum) != m_VisitedColumns.end()) {
                NotPrevioslyVisited = false;
            }
        }
        break;
    }

    return NotPrevioslyVisited;
}

void KMPath::AddMoveToPath(KMMove Move)
{
    m_RecordOfMoves.push_back(Move);
    KMBoardLocation CurrentLocation = Move.GetNextLocation();
    m_VisitedRows.push_back(CurrentLocation.GetRow());
    m_VisitedColumns.push_back(CurrentLocation.GetColumn());
    m_VisitedLocations.push_back(CurrentLocation);
    m_ReachedDestination = (CurrentLocation == m_Destination);
    m_PointOfOrigin = CurrentLocation;
}

KMMove KMPath::GetLastMove()
{
    KMMove LastMove;
    if (m_RecordOfMoves.size() > 0) {
        LastMove = m_RecordOfMoves.back();
    }
    else
    {
        std::cerr << "In KMPath::GetLastMove() : There was no last move" << std::endl;
    }

    return LastMove;
}

KMPossibleMoves.h

#ifndef KMPOSSIBLEMOVES_H_
#define KMPOSSIBLEMOVES_H_

#include "KMMove.h"

class KMPossibleMoves {

protected:
    unsigned int m_SingleSideBoardDimension;
    void UpdateDimension(unsigned int BoardDimension);

public:
    KMPossibleMoves();
    KMPossibleMoves(unsigned int BoardDimension);
    KMPossibleMoves(const KMPossibleMoves &Original);
    virtual ~KMPossibleMoves() = default;
    KMRandomAccessMoveCollection GetAllPossibleMoves() const { return AllPossibleMoves; };
    KMRandomAccessMoveCollection GetOnlyValidPossibleMoves(KMBoardLocation Origin);
    // The 8 possible moves the knight can make.
    static KMMove Left1Up2;
    static KMMove Left2Up1;
    static KMMove Left2Down1;
    static KMMove Left1Down2;
    static KMMove Right1Up2;
    static KMMove Right2Up1;
    static KMMove Right2Down1;
    static KMMove Right1Down2;
    static KMRandomAccessMoveCollection AllPossibleMoves;
};

#endif /* KMPOSSIBLEMOVES_H_ */

KMPossibleMoves.cpp

#include "KMPossibleMoves.h"
#include "KMBoardDimensionConstants.h"

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;

KMRandomAccessMoveCollection KMPossibleMoves::AllPossibleMoves;
KMMove KMPossibleMoves::Left1Up2(Left1, Up2, DefaultBoardDimensionOnOneSide);
KMMove KMPossibleMoves::Left2Up1(Left2, Up1, DefaultBoardDimensionOnOneSide);
KMMove KMPossibleMoves::Left2Down1(Left2, Down1, DefaultBoardDimensionOnOneSide);
KMMove KMPossibleMoves::Left1Down2(Left1, Down2, DefaultBoardDimensionOnOneSide);
KMMove KMPossibleMoves::Right1Up2(Right1, Up2, DefaultBoardDimensionOnOneSide);
KMMove KMPossibleMoves::Right2Up1(Right2, Up1, DefaultBoardDimensionOnOneSide);
KMMove KMPossibleMoves::Right2Down1(Right2, Down1, DefaultBoardDimensionOnOneSide);
KMMove KMPossibleMoves::Right1Down2(Right1, Down2, DefaultBoardDimensionOnOneSide);

KMPossibleMoves::KMPossibleMoves()
 : m_SingleSideBoardDimension{DefaultBoardDimensionOnOneSide}
{
    KMPossibleMoves::AllPossibleMoves.clear();
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Left1Up2);
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Left2Up1);
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Left2Down1);
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Left1Down2);
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Right1Up2);
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Right2Up1);
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Right2Down1);
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Right1Down2);
}

KMPossibleMoves::KMPossibleMoves(unsigned int BoardDimension)
 : m_SingleSideBoardDimension{BoardDimension}
{
    KMPossibleMoves::AllPossibleMoves.clear();
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Left1Up2);
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Left2Up1);
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Left2Down1);
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Left1Down2);
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Right1Up2);
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Right2Up1);
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Right2Down1);
    KMPossibleMoves::AllPossibleMoves.push_back(KMPossibleMoves::Right1Down2);

    UpdateDimension(m_SingleSideBoardDimension);
}

/**
 * Copy constructor for when a path is copied.
 */
KMPossibleMoves::KMPossibleMoves(const KMPossibleMoves &Original)
{
    m_SingleSideBoardDimension = Original.m_SingleSideBoardDimension;
    AllPossibleMoves = Original.AllPossibleMoves;
}

void KMPossibleMoves::UpdateDimension(unsigned int BoardDimension)
{
    for (auto MoveToUpdate: KMPossibleMoves::AllPossibleMoves) {
        MoveToUpdate.SetBoardDimension(BoardDimension);
    }
}

KMRandomAccessMoveCollection KMPossibleMoves::GetOnlyValidPossibleMoves(KMBoardLocation Origin)
{
    KMRandomAccessMoveCollection ValidMoves;
    for (auto MoveToUpdate: KMPossibleMoves::AllPossibleMoves) {
        KMMove TempMove = MoveToUpdate;
        /**
         * Origin and Destination are not set in the Possible Moves.
         * They only containt the transition values.
         */
        TempMove.SetOriginCalculateDestination(Origin);
        TempMove.SetBoardDimension(m_SingleSideBoardDimension);
        if (TempMove.IsValid()) {
            ValidMoves.push_back(TempMove);
        }
    }

    return ValidMoves;
}

KMMove.h

#ifndef KMMOVE_H_
#define KMMOVE_H_

#include <vector>
#include <list>
#include "KMBoardLocation.h"

class KMMove {
private:
    int m_RowTransition;
    int m_ColumnTransition;
    int m_BoardDimension;
    KMBoardLocation m_Origin;
    KMBoardLocation m_Destination;

public:
    KMMove();
    KMMove(int RowTransition, int ColumnTransition, unsigned int BoardDimension);
    virtual ~KMMove() = default;
    const bool IsValid();
    void CalculateDestination();
    void SetOriginCalculateDestination(const KMBoardLocation Origin);
    KMBoardLocation GetNextLocation() const { return m_Destination; }
    void SetOrigin(KMBoardLocation Origin) { m_Origin = Origin; }
    KMBoardLocation GetOrigin() const { return m_Origin; }
    void SetRowTransition(int RowTransition){ m_RowTransition = RowTransition; }
    int GetRowTransition() const { return m_RowTransition; }
    void SetColumnTransition(int ColumnTransition){ m_ColumnTransition = ColumnTransition; }
    int GetColumnTransition() const { return m_ColumnTransition; }
    void SetBoardDimension(unsigned int BoardDimension) { m_BoardDimension = static_cast<int>(BoardDimension); }
    int GetBoardDimension() { return m_BoardDimension; }
    void SetTransitionsAndDimension(const int RowTransition, const int ColumnTransition, const unsigned int BoardDimension) {
        m_RowTransition = RowTransition;
        m_ColumnTransition = ColumnTransition;
        m_BoardDimension = static_cast<int>(BoardDimension);
    }
    friend std::ostream &operator<<( std::ostream &output, KMMove &Move)
    {
        output << "Move from " << Move.GetOrigin().GetName();
        output << " To " << Move.GetNextLocation().GetName();
        return output;
    }
};

typedef std::vector<KMMove> KMRandomAccessMoveCollection;
typedef std::list<KMMove> KMFastAccessMoveCollection;
typedef std::vector<std::list<KMMove>> KMCollectionOfPathRecords;

#endif /* KMMOVE_H_ */

KMMove.cpp

#include <stdexcept>
#include "KMMove.h"
#include "KMBoardDimensionConstants.h"

KMMove::KMMove()
 : m_RowTransition{0},
   m_ColumnTransition{0},
   m_BoardDimension{DefaultBoardDimensionOnOneSide}
{
}

/**
 * BoardDimension is converted to int for type safe comparisions.
 */
KMMove::KMMove(int RowTransition, int ColumnTransition, unsigned int BoardDimension)
: m_RowTransition{RowTransition},
  m_ColumnTransition{ColumnTransition},
  m_BoardDimension{static_cast<int>(BoardDimension)}
{
}

void KMMove::CalculateDestination()
{
    if (m_Origin.IsSet()) {
        m_Destination.SetRow(m_RowTransition + m_Origin.GetRow());
        m_Destination.SetColumn(m_ColumnTransition + m_Origin.GetColumn());
        m_Destination.SetBoardDimension(m_Origin.GetBoardDimension());
    }
    else
    {
        throw std::runtime_error("KMMove::CalculateDestination : Point of Origin has not been set;\n");
    }
}

void KMMove::SetOriginCalculateDestination(KMBoardLocation Origin)
{
    if (Origin.IsValid()) {
        m_Origin = Origin;
        CalculateDestination();
    }
    else
    {
        throw std::runtime_error("KMMove::CalculateDestination : Parameter Origin has not been set;\n");
    }
}

const bool KMMove::IsValid()
{
    if (((!m_RowTransition) || (!m_ColumnTransition)) || (!m_Destination.IsValid())) {
        // default constructor, not a valid move.
        return false;
    }

    return true;
}

KMBoardLocation.h

#ifndef KMBOARDLOCATION_H_
#define KMBOARDLOCATION_H_

#include <iostream>
#include <string>

class KMBoardLocation {
private:
    std::string m_Name;
    unsigned int m_Row;
    unsigned int m_Column;
    unsigned int m_BoardDimension;
    void ThrowBoundsException(const char* FormatString);

public:
    KMBoardLocation();
    KMBoardLocation(unsigned int Row, unsigned int Column, unsigned int BoardSingleSideDimension);
    virtual ~KMBoardLocation() = default;
    std::string GetName();
    void SetName(std::string Name) { m_Name = Name; }
    void MakeName();
    void SetRow(const unsigned int Row) { m_Row = Row; }
    unsigned int GetRow() const { return m_Row; }
    void SetColumn(const unsigned int Column) { m_Column = Column; }
    unsigned int GetColumn() const { return m_Column; }
    bool IsSet() { return (m_Row && m_Column); }
    bool IsValid();
    void SetBoardDimension(unsigned int Dimension) { m_BoardDimension = Dimension; }
    int GetBoardDimension() { return m_BoardDimension; }
    bool operator ==(const KMBoardLocation &OtherLocation) {
        if ((m_Row == OtherLocation.m_Row) && (m_Column == OtherLocation.m_Column)) {
            return true;
        }
        return false;
    }
    friend std::ostream &operator<<( std::ostream &output, KMBoardLocation &KMLoc)
    {
        output << " " << KMLoc.GetName();
        return output;
    }
};

#endif /* KMBOARDLOCATION_H_ */

KMBoardLocation.cpp

#include "KnightMoves.h"
#include <stdio.h>
#include <string>
#include <stdexcept>
#include "KMBoardLocation.h"
#include "KMBoardDimensionConstants.h"

const int ExceptionMessageBufferSize = 1024;

KMBoardLocation::KMBoardLocation()
: m_Row{0}, m_Column{0}, m_BoardDimension{DefaultBoardDimensionOnOneSide}
{
    m_Name = "";
}

KMBoardLocation::KMBoardLocation(unsigned int Row, unsigned int Column, unsigned int BoardSingleSideDimension)
 : m_Row{Row}, m_Column{Column}, m_BoardDimension{BoardSingleSideDimension}
{
    if (((m_Row < MinimumBoardLocationValue)|| (m_Row > m_BoardDimension)) ||
        ((m_Column < MinimumBoardLocationValue) || (m_Column > m_BoardDimension))) {
        ThrowBoundsException("KMBoardLocation::KMBoardLocation");
    }
    MakeName();
}

/**
 * A common chess notation for location is using A-H for rows and 1-8 for columns.
 * MakeName creates a name for the location using that notation.
 */
void KMBoardLocation::MakeName()
{
    const unsigned int RowCStrSize = 2; // Enough for a null terminated string of 1 character
    const unsigned int RowCharacterPosition = 0;
    const unsigned int RowNullTerminatorPosition = 1;

    if (((m_Row < MinimumBoardLocationValue)|| (m_Row > m_BoardDimension)) ||
        ((m_Column < MinimumBoardLocationValue) || (m_Column > m_BoardDimension))) {
        ThrowBoundsException("KMBoardLocation::MakeName()");
    }

    char RowCStr[RowCStrSize];
    RowCStr[RowCharacterPosition] = ('A' + (m_Row - 1));
    RowCStr[RowNullTerminatorPosition] = '\0';

    std::string tempRow(RowCStr);
    std::string tempColumn = std::to_string(m_Column);
    m_Name = tempRow + tempColumn;
}

std::string KMBoardLocation::GetName() {
    if (m_Name.empty()) {
        MakeName();
    }

    return m_Name;
}

void KMBoardLocation::ThrowBoundsException(const char *CallingFunction)
{
    char estrbuff[ExceptionMessageBufferSize];
    sprintf(estrbuff, "%s value out of range (%d to %d) : ", CallingFunction, MinimumBoardLocationValue, m_BoardDimension);
    std::string EMessage(estrbuff);
    sprintf(estrbuff, "Row = %d, Column = %d", m_Row, m_Column);
    EMessage.append(estrbuff);
    throw std::runtime_error(EMessage);
}

bool KMBoardLocation::IsValid()
{
    bool ValidLocation = true;
    if (!IsSet())
    {
        ValidLocation = false;
    }
    else
    {
        if ((m_Row < MinimumBoardLocationValue)|| (m_Row > m_BoardDimension)) {
            ValidLocation = false;
        }
        if ((m_Column < MinimumBoardLocationValue)|| (m_Column > m_BoardDimension)) {
            ValidLocation = false;
        }
    }

    return ValidLocation;
}

KnightMoves.cpp

#include <iostream>
#include <stdexcept>
#include <chrono>
#include <ctime>
#include "KnightMoves.h"
#include "KnightMovesTIO.h"
#include "KnightMovesImplementation.h"
#include "KMBoardDimensionConstants.h"

KMBaseData TestData[] {
        {1,3,"A3",8,4,"H4",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn},
        {1,1,"A1",8,8,"H8",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn},
        {1,8,"A8",8,1,"H1",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn},
        {2,3,"B3",8,4,"H4",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn},
        {2,3,"B3",8,8,"H8",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn},
        {3,1,"C1",8,4,"H4",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn},
        {3,1,"A3",8,8,"H8",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn},
        {1,3,"A3",2,5,"B5",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn},    // Minimum should be one move
        {1,3,"A3",2,5,"B5",12,DenyByPreviousRowOrColumn},                            // Minimum should be one move
        {1,3,"A3",2,5,"B5",MaximumBoardDimension,DenyByPreviousRowOrColumn},        // Minimum should be one move
        {8,4,"H4",1,3,"A3",DefaultBoardDimensionOnOneSide,DenyByPreviousRowOrColumn}
};

void ExecutionLoop(KnightMovesBaseData UserInputData)
{
    KnightMovesImplementation KnightPathFinder(UserInputData);
    std::chrono::time_point<std::chrono::system_clock> start, end;
    start = std::chrono::system_clock::now();
    KMOutputData OutputData = KnightPathFinder.CalculatePaths();
    end = std::chrono::system_clock::now();

    std::chrono::duration<double> elapsed_seconds = end-start;
    std::time_t end_time = std::chrono::system_clock::to_time_t(end);

    std::cout << "finished computation at " << std::ctime(&end_time)
              << "elapsed time: " << elapsed_seconds.count() << std::endl << std::endl << std:: endl;
    // Don't include output of results in elapsed time calculation
    OutputData.DontShowPathData();
    OutputData.ShowResults();
}

int main(const int argc, const char *argv[])
{
    int status = 0;
    size_t TestDataCount = sizeof(TestData) / sizeof(KMBaseData);

    try {
//        for (size_t i = TestDataCount - 2; i < TestDataCount; i++) {
        for (size_t i = 0; i < TestDataCount; i++) {
            ExecutionLoop(TestData[i]);
        }
        return status;
    }
    catch(std::runtime_error &e) {
        std::cerr << "A fatal error occurred in KnightMoves: ";
        std::cerr << e.what()  << std::endl;
        status = 1;
    }
    catch(std::runtime_error *e) {
        std::cerr << "A fatal error occurred in KnightMoves: ";
        std::cerr << e->what()  << std::endl;
        status = 1;
    }
    catch(...) {
        std::cerr << "An unknown fatal error occurred in KnightMoves." << std::endl;
        status = 1;
    }
    return status;
}

KMBaseData.h

typedef struct KnightMovesBaseData {
    unsigned int m_StartRow;
    unsigned int m_StartColumn;
    std::string m_StartName;
    unsigned int m_TargetRow;
    unsigned int m_TargetColumn;
    std::string m_TargetName;
    unsigned int m_DimensionOneSide;
    KnightMovesMethodLimitations m_LimitationsOnMoves;
} KMBaseData;

KMBoardDimensionConstants.h

const int MinimumBoardLocationValue = 1;       // While arrays are 0 to N, the minimum board location is A and 1
const unsigned int DefaultBoardDimensionOnOneSide = 8;
const unsigned int MaximumBoardDimension = 26; // A to Z, common chess notation of a square on the board is [A-H][1-8]

KMMethodLimitations.h

enum KnightMovesMethodLimitations
{
    DenyByPreviousRowOrColumn,
    DenyByPreviousLocation
};

KnightMoves.h

#ifndef KNIGHTMOVES_H
#define KNIGHTMOVES_H 1
#include "KMMethodLimitations.h"
#include "KMBaseData.h"

#endif // KNIGHTMOVES_H

KMOutputData.h

#ifndef KMOUTPUTDATA_H_
#define KMOUTPUTDATA_H_

#include "KMPath.h"

class KMOutputData {
private:
    KMBoardLocation m_Origin;
    KMBoardLocation m_Destination;
    unsigned int m_BoardDimension;
    KMCollectionOfPathRecords m_PathRecords;
    unsigned int m_AttemptedPaths;
    KnightMovesMethodLimitations m_LimitationsOnMoves;
    bool m_ShowPathData;
protected:
    void OutputOnePath(KMFastAccessMoveCollection MoveList);
    void OutputSlicingMethodlogy();

public:
    KMOutputData();
    virtual ~KMOutputData() = default;
    void IncrementAttemptedPaths() { m_AttemptedPaths++; }
    void AddPath(const KMPath PathData) { m_PathRecords.push_back(PathData.GetRecordOfMoves()); }
    int GetPathCount() const { return m_PathRecords.size(); }
    KMCollectionOfPathRecords GetAllPaths() const { return m_PathRecords; }
    unsigned int GetAttempts() const { return m_AttemptedPaths; }
    void SetPointOfOrigin(KMBoardLocation Origin) { m_Origin = Origin; }
    KMBoardLocation GetPointOfOrigin() { return m_Origin; }
    void SetDestination(KMBoardLocation Destination) { m_Destination = Destination; }
    KMBoardLocation GetDestination() { return m_Destination; }
    void SetBoardDimension(unsigned int BoardDimension) { m_BoardDimension = BoardDimension; }
    unsigned int GetBoardDimension() { return m_BoardDimension; }
    // Statistics on the returned paths.
    void ShowStats();
    double Average(std::vector<double> PathLengths);
    void SetSlicingMethod(KnightMovesMethodLimitations Limitations) { m_LimitationsOnMoves = Limitations; }
    KnightMovesMethodLimitations GetSlicingMethod() { return m_LimitationsOnMoves; }
    void DontShowPathData() { m_ShowPathData = false; }
    void ShowPathData() { m_ShowPathData = true; }
    bool GetShowPathData() { return m_ShowPathData; }
    void ShowResults();
};

#endif /* KMOUTPUTDATA_H_ */

KMOutputData.cpp

#include <vector>
#include <algorithm>
#include <functional>
#include "KMOutputData.h"

KMOutputData::KMOutputData()
 : m_BoardDimension{0}, m_AttemptedPaths{0}, m_LimitationsOnMoves{DenyByPreviousRowOrColumn}, m_ShowPathData{false}
{

}

void KMOutputData::ShowStats()
{

    std::vector<double> PathLengths;
    for (auto PathsIter : m_PathRecords)
    {
        PathLengths.push_back(static_cast<double>(PathsIter.size()));
    }

    std::cout << "The average path length is " << Average(PathLengths) << std::endl;
    std::nth_element(PathLengths.begin(), PathLengths.begin() + PathLengths.size()/2, PathLengths.end());
    std::cout << "The median path length is " << PathLengths[PathLengths.size()/2] << std::endl;
    std::nth_element(PathLengths.begin(), PathLengths.begin()+1, PathLengths.end(), std::greater<int>());
    std::cout << "The longest path is " << PathLengths[0] << " moves" << std::endl;
    std::nth_element(PathLengths.begin(), PathLengths.begin()+1, PathLengths.end(), std::less<int>());
    std::cout << "The shortest path is " << PathLengths[0] << " moves" << std::endl;
}

double KMOutputData::Average(std::vector<double> PathLengths)
{
    double AverageLength = 0.0;
    for (auto PathLenthsIter : PathLengths)
    {
        AverageLength += PathLenthsIter;
    }
    AverageLength = AverageLength / static_cast<double>(PathLengths.size());
    return AverageLength;
}
    for (auto PathLenthsIter : PathLengths)
    {
        AverageLength += PathLenthsIter;
    }
    AverageLength = AverageLength / static_cast<double>(PathLengths.size());
    return AverageLength;
}

void KMOutputData::ShowResults()
{
    std::cout << "The point of origin for all path searches was " << m_Origin << std::endl;
    std::cout << "The destination point for all path searches was " << m_Destination << std::endl;
    std::cout << "The number of squares on each edge of the board is " << m_BoardDimension << std::endl;
    OutputSlicingMethodlogy();
    std::cout << "There are " << m_PathRecords.size() << " Resulting Paths" << std::endl;
    std::cout << "There were " << m_AttemptedPaths << " attempted paths" << std::endl;
    ShowStats();

    if (!m_ShowPathData) {
        for (int i = 0; i < 25; i++) std::cout << "-";
        std::cout << std::endl << std::endl;
        return;
    }
    std::cout << std::endl << std::endl << std::endl << "Here is the listing of the paths" << std::endl << std::endl;


    for (auto MoveListIter : m_PathRecords)
    {
        for (int i = 0; i < 25; i++) std::cout << "-";
        std::cout << std::endl << std::endl;
        KMFastAccessMoveCollection ThisPath = MoveListIter;
        OutputOnePath(ThisPath);
    }
}

void KMOutputData::OutputOnePath(KMFastAccessMoveCollection MoveList)
{
    std::cout << "This path contains " << MoveList.size() << " moves." << std::endl;
    for (auto MoveIter : MoveList) {
        KMMove ItemToShow = MoveIter;
        std::cout << ItemToShow << std::endl;
    }
}

void KMOutputData::OutputSlicingMethodlogy()
{
    switch (m_LimitationsOnMoves) {
    default :
        throw std::runtime_error("KnightMovesTIO::OutputSlicingMethodlogy : Unknown type of Path Limitation.");
    case DenyByPreviousLocation :
        std::cout << "The slicing methodology used to further limit searches was no repeat visits to squares on the board." << std::endl;
        break;
    case DenyByPreviousRowOrColumn:
        std::cout << "The slicing methodology used to further limit searches was no repeat visits to any rows or columns." << std::endl;
        break;
    }
}

Answer 1

I see a number of things that could help you improve your code.

typedef struct is not needed in C++

In KMBaseData.h, the code includes this line:

typedef struct KnightMovesBaseData {
    // ...
} KMBaseData;

While common in C, this is not needed in C++ since the name of the struct type is already available as a type. That line should simply be:

struct KMBaseData {
    // ...
};

Then replace each instance of KnightMovesBaseData with KMBaseData. It's usually better to have just one name.

Don't use const with non-reference return values

The KMMove class includes this member function:

const bool IsValid();

That says that the non-const function IsValid returns a const bool. I don't think that's what you meant. It should instead be:

bool IsValid() const;

Use only standard forms of main

The code includes this line:

int main(const int argc, const char *argv[])

There are two problems with that. First, neither argc nor argv are const. See this question which refers to the only two standard declarations of main which are:

int main(int argc, char* argv[])
int main() 

The second problem is that neither argc nor argv are used, so this program should use the second form of main.

Use const where practical

The current KMBoardLocation::IsSet() routine does not (and should not) modify the underlying object, and so it should be declared const:

bool KMBoardLocation::IsValid() const

Similarly:

bool KMBoardLocation::operator ==(const KMBoardLocation &OtherLocation) const {

Use include guards

There should be an include guard in every .h file. That is, start each include file with something like this for `KMBoardDimensionConstants.h:

#ifndef KMBOARDDIMENSIONCONSTANTS_H
#define KMBOARDDIMENSIONCONSTANTS_H
// file contents go here
#endif // KMBOARDDIMENSIONCONSTANTS_H

Simplify your copy constructor

The copy constructor for KMPath fails to initialize the base class KMPossibleMoves. While this could be addressed by simply adding that to the already long list of copies, why don't we simplify things considerably and fix the omission by doing this:

KMPath(const KMPath &Original) = default;

Now the compiler will generate all of the correct code for you.

Use "range for" and simplify your code

Right now within main, the code loops through the test cases like this:

size_t TestDataCount = sizeof(TestData) / sizeof(KMBaseData);

try {
    for (size_t i = 0; i < TestDataCount; i++) {
        ExecutionLoop(TestData[i]);
    }
    return status;
}

There is a much simpler way to express this in C++11 by using a "range for":

try {
    for (const auto &test : TestData) {
        ExecutionLoop(test);
    }
}

Note that I've omitted the return status since it's already included as the last line of main, so repeating it here is not useful.

Pass const references where practical

The current code is much slower than it needs to be because it is spending lots of time needlessly making copies of objects. For example, the KMPath::IsNotPreviouslyVisited function could be declared like this:

bool KMPath::IsNotPreviouslyVisited(const KMBoardLocation& PossibleDestination) const

Eliminate redundant copies in loops

In the heavily used KMPossibleMoves::GetOnlyValidPossibleMoves() function, we have this code:

for (auto MoveToUpdate: KMPossibleMoves::AllPossibleMoves) {
    KMMove TempMove = MoveToUpdate;
    // do stuff with TempMove
}

That's a redundant copy. When you have auto MoveToUpdate instead of auto &MoveToUpdate, you're already making a copy of each item, so there's no need to make yet another copy with the following line. Instead, eliminate the second line and write the first like this:

for (auto MoveToUpdate: KMPossibleMoves::AllPossibleMoves) {

Return const reference where appropriate

The only place that the std::string KMBoardLocation::GetName() is called is within output routines. The implementation of the function is this:

std::string KMBoardLocation::GetName() {
    if (m_Name.empty()) {
        MakeName();
    }
    return m_Name;
}

First, it's somewhat misleading for a function named GetName to have an occasional side-effect of setting it! It's also not necessary. I'd recommend making this a const function that returns a const reference:

const std::string& GetName() const { return m_Name; };

Fix your constructors

The existing constructor for KMPath looks like this:

KMPath::KMPath()
: //m_SingleSideBoardDimension{DefaultBoardDimensionOnOneSide},
  m_ReachedDestination{false},
  m_Valid{false},
  m_PathLength{0},
  m_PathLimitations{DenyByPreviousRowOrColumn}
{
    m_SingleSideBoardDimension = DefaultBoardDimensionOnOneSide;
}

That's the right idea, but not quite the right syntax. Use this:

KMPath::KMPath()
: KMPossibleMoves{DefaultBoardDimensionOnOneSide},
  m_ReachedDestination{false},
  m_Valid{false},
  m_PathLength{0},
  m_PathLimitations{DenyByPreviousRowOrColumn}
{
}

With that, you can also remove the using in KMPath.h if you do a similar fix to the other constructor.

Make const data really const

The KMPossibleMoves::AllPossibleMoves is static which is good, but it should also be const and it should be initialize only once at startup rather than within the class constructor. Use this:

const KMRandomAccessMoveCollection KMPossibleMoves::AllPossibleMoves{
    Left1Up2,
    Left2Up1,
    Left2Down1,
    Left1Down2,
    Right1Up2,
    Right2Up1,
    Right2Down1,
    Right1Down2,
};

And place it immediately after the const initialization for those moves. This will allow you to remove the UpdateDimension call as well. Instead, the GetOnlyValidPossibleMoves() looks like this:

KMRandomAccessMoveCollection KMPossibleMoves::GetOnlyValidPossibleMoves(const KMBoardLocation& Origin) const
{
    KMRandomAccessMoveCollection ValidMoves;
    for (auto TempMove: KMPossibleMoves::AllPossibleMoves) {
        TempMove.SetOriginCalculateDestination(Origin);
        TempMove.SetBoardDimension(m_SingleSideBoardDimension);
        if (TempMove.IsValid()) {
            ValidMoves.push_back(TempMove);
        }
    }
    return ValidMoves;
}

Avoid creating temporary collections

The current KMPath::GetPossibleMoves() creates a temporary collection by calling GetOnlyValidPossibleMoves() and then creating copies of those to put into another collection which is returned. It would make more sense, and give your code a performance benefit, if you would instead simply create the final collection that's returned by combining the two functions. Rewritten, it might look like this:

KMRandomAccessMoveCollection KMPath::GetPossibleMoves(const KMBoardLocation& Origin) const
{
    KMRandomAccessMoveCollection PossibleMoves;
    for (auto ThisPossibleMove : AllPossibleMoves) {
        ThisPossibleMove.SetOriginCalculateDestination(Origin);
        ThisPossibleMove.SetBoardDimension(m_SingleSideBoardDimension);
        if (ThisPossibleMove.IsValid() && IsNotPreviouslyVisited(ThisPossibleMove)) {
            PossibleMoves.push_back(ThisPossibleMove);
        }
    }
    return PossibleMoves;
}

Multithreading

This program would probably benefit from a multithreaded approach, but the current design, in which CalculatePath alters m_Results would need locking to avoid data races. An alternative would be to modify the program to have each thread create its own m_Results and then join them when all threads are complete. std::async would be useful for that approach.

Results

Doing all of these things to the code resulted in the speed approximately doubling, with the 26 square per side running in 179.345 seconds. (1.87 times faster on my 64-bit Linux machine.) I'm sure there's more to be reduced, but the principles above should help you get there.