Knights Tour - Improved Refactored Recursive Breadth First Search for

The development and testing was performed on a Dell M6400 Laptop (Intel Core 2 Duo) running Centos 7, g++ compiler version 4.8.5, compiler switches -O3 -std=c++0x -D__cplusplus=201103L. (machine bought August 2009 with Windows XP
). It was also tested on a four core i7 based version of CentOS 7 with 12GB of DDR3 RAM (built 2011).

The code, makefile and gz compressed gprof output are posted on GitHub.

This is a refactored version of the code presented in Recursive Breadth First Search for Knights Tour.

Please make any and all suggestions on improvement, I am especially interested in the following

1. Are the any Containers or Library Algorithms in C++11 that would have decreased the amount of code or improved the quality of the code?

1. Improving readability

1. Improving maintainability

1. Improved Data Encapsulation.

1. Reducing coupling between classes as much as possible.

1. More optimization (speed freak).

The code was refactored several reasons:

1. There was too much couping between the KMPath class and the KnightMovesImplementation class.

1. The KMPath class was too complex (KISS principal or Demeter's Law).

1. The KMPath class did not properly encapsule the data.

1. The recursive algorithm in the KnightMovesImplementation class was too complex.

1. Too much data was being copied.

1. The number of attempted paths was being recorded wrong.

1. The implementation was too difficult to translate to other languages.

Due to the new implementation:

1. There is about 6% less code

1. The implementation is 2 to 4 times faster than the original, based on individual test cases. 2.6 times faster in Overall statistics.

1. The output results other than the execution times and the number of attempted paths is the same.

After implementing all of suggestions from the last review, the overall timing was

The average execution time is 0.00511662 seconds

The median execution time is 0.00271199 seconds

The longest execution time is 0.0319622 seconds

Th

• Improving readability

The code suffers from wall-of-text syndrome.

Make a vertical space between the different function groups in the code:
constructors/destructor/assigners
set/get
doers.

Also before each if, while, for and others that starts a new block.


More optimization (speed freak).

You have a lot of const, if they really are const use constexpr instead.

When you then have a fixed sized std::vector use std::array instead.

Using an emplace_back instead of push_back when possible.

You have a lot of std::string copying and creating these takes a lot of time. Instead create a std::array of all the texts and use an index into it instead.

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

gets to be something like

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

or

int GetName() const { return m_Name; }

depending on the usage.

Your using std::list that is seldom a good choice if you use it in critical loops. Depending on your usage you might be better off with std::array or std::vector.

If you want to check if a row or column has been visited, you could use a bitmask instead. With a maximum of 26 rows/columns a int32_t can be used for each.

(untested code)

bool visited(int row, int col) {
  row = (1<<(row-1); // convert to bit mask.
  col = (1<<(col-1);

  if (row & prevRow || col & prevCol) // bitwise and
    return false; // already visited

  prevRow |= row; // bitwise or
  prevCol |= col;
  return true; // ok visit
}

bool unvisited(int row, int col) {
  row = (1<<(row-1); // convert to bit mask.
  col = (1<<(col-1);

  // sanity check
  if (!(row & prevRow && col & prevCol)) // bitwise and
    return false; // trying to remove wrong col/row

  prevRow &= ~row; // bitwise and, removing the bits by masking
  prevCol &= ~col;
  return true; // remove was ok.
}

2 ints should be a lot easier to handle than the large state your hauling around.

Your timings could be off because you use the system clock, which could have a max resolution of around 1ms. Use a std::chrono::high_resolution_clock instead, read the notes as it might still be the system clock.

StackExchange Code Review Q#132876, answer score: 3