Recursive Breadth First Search for Knights Tour

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.276

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_Reach

StackExchange Code Review Q#123489, answer score: 5