CodeReviewで提示されたソリューションは、CentOS 7.1 で正常に動作します。私はそれをWindows 7、Visual Studio 2012に移植しようとしました.VS 2012がコードコンパイルをサポートしていないC++ 11の部分を可能にするためにマイナーな編集を行い、ループの最初の実行が正しく機能します. テスト ケースの残りの実行は失敗し、実行のたびに不正確さが増していきます。
この問題のコードはgithubにあります。
0 で計算を終了 /* ここの問題は問題に含まれていません */
経過時間: 0.202012 秒
すべてのパス検索の起点は A3 でした すべてのパス検索
の終点は H4
でした ボードの各エッジの正方形の数は 8 です
検索をさらに制限するために使用されたスライス方法論は、行または列への繰り返しの訪問ではありませんでした。
結果のパスは 5 つです
試行されたパスは 323 ありました
パスの長さの平均は 4.8 です
パスの長さの中央値は 4 です
最長のパスは 6 回の移動
です 最短のパスは 4 回の移動です
問題は、以下にリストされているファイルのいずれかにあると思います。私はこれを 2 日間デバッグしてきました。
CRKnightMoves_Cpp2.cpp
/*
* KnightMoves.cpp
*
* Author: pacmaninbw
*/
#include "stdafx.h"
#include <iostream>
#include <stdexcept>
#include <chrono>
#include <ctime>
#include <algorithm>
#include <functional>
#include <vector>
#include "KnightMoves.h"
#include "KnightMovesImplementation.h"
#include "KMBoardDimensionConstants.h"
double Average(std::vector<double> TestTimes)
{
double AverageTestTime = 0.0;
double SumOfTestTimes = 0.0;
int CountOfTestTimes = 0;
for (auto TestTimesIter : TestTimes)
{
SumOfTestTimes += TestTimesIter;
CountOfTestTimes++;
}
if (CountOfTestTimes) { // Prevent division by zero.
AverageTestTime = SumOfTestTimes / static_cast<double>(CountOfTestTimes);
}
return AverageTestTime;
}
void OutputOverAllStatistics(std::vector<double> TestTimes)
{
if (TestTimes.size() < 1) {
std::cout << "No test times to run statistics on!" << std::endl;
return;
}
std::cout << std::endl << "Overall Results" << std::endl;
std::cout << "The average execution time is " << Average(TestTimes) << " seconds" << std::endl;
std::nth_element(TestTimes.begin(), TestTimes.begin() + TestTimes.size()/2, TestTimes.end());
std::cout << "The median execution time is " << TestTimes[TestTimes.size()/2] << " seconds" << std::endl;
std::nth_element(TestTimes.begin(), TestTimes.begin()+1, TestTimes.end(), std::greater<double>());
std::cout << "The longest execution time is " << TestTimes[0] << " seconds" << std::endl;
std::nth_element(TestTimes.begin(), TestTimes.begin()+1, TestTimes.end(), std::less<double>());
std::cout << "The shortest execution time is " << TestTimes[0] << " seconds" << std::endl;
}
double ExecutionLoop(KMBaseData UserInputData)
{
KnightMovesImplementation *KnightPathFinder = new KnightMovesImplementation(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);
double ElapsedTimeForOutPut = elapsed_seconds.count();
char ctimebuffer[1024];
std::cout << "finished computation at " << ctime_s(ctimebuffer, 1024, &end_time) << "\n"
<< "elapsed time: " << ElapsedTimeForOutPut << " Seconds\n" << "\n" << "\n";
// Don't include output of results in elapsed time calculation
OutputData.DontShowPathData();
// OutputData.ShowPathData();
OutputData.ShowResults();
delete KnightPathFinder;
return ElapsedTimeForOutPut;
}
int LetUserEnterTestCaseNumber(std::vector<KMBaseData> &TestData)
{
int i = 1;
int Choice = -1;
std::cout << "Select the number of the test case you want to run.\n";
std::cout << "Test Case #" << "\tStart Name" << "\tTarget Name" << "\tBoard Size" << "\tSlicing Method" << "\n";
for (auto TestCase: TestData) {
std::cout << i << "\t" << TestCase.m_StartName << "\t" << TestCase.m_TargetName << "\t" << TestCase.m_DimensionOneSide << "\t";
switch (TestCase.m_LimitationsOnMoves)
{
default :
throw std::runtime_error("LetUserEnterTestCaseNumber : Unknown type of Path Limitation.");
case DenyByPreviousLocation :
std::cout << "Can't return to previous location";
break;
case DenyByPreviousRowOrColumn:
std::cout << "Can't return to previous row or column";
break;
}
std::cout << "\n";
i++;
}
std::cout << i << "\tAll of the above except for 13 and 14\n";
std::cout << ++i <<"\tAll of the above (Go get lunch)\n";
std::cin >> Choice;
if (Choice == 15)
{
std::vector<KMBaseData> TempTests;
for (auto TestCase: TestData)
{
if ((TestCase.m_DimensionOneSide != MaximumBoardDimension) && (TestCase.m_LimitationsOnMoves != DenyByPreviousLocation))
{
TempTests.push_back(TestCase);
}
}
TestData = TempTests;
}
return Choice;
}
void InitTestData(std::vector<KMBaseData> &TestData)
{
KMBaseData TestCases[] = {
{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
{8,4,"H4",1,3,"A3", DefaultBoardDimensionOnOneSide, DenyByPreviousRowOrColumn},
{4,4,"D4",1,8,"A8", DefaultBoardDimensionOnOneSide, DenyByPreviousRowOrColumn},
{4,4,"D4",5,6,"E6", DefaultBoardDimensionOnOneSide, DenyByPreviousRowOrColumn},
{1,3,"A3",2,5,"B5", 12, DenyByPreviousRowOrColumn}, // Minimum should be one move
{1,3,"A3",2,5,"B5", DefaultBoardDimensionOnOneSide, DenyByPreviousLocation}, // Minimum should be one move
{1,3,"A3",2,5,"B5", MaximumBoardDimension, DenyByPreviousRowOrColumn} // Minimum should be one move
};
for (int i = 0; i < sizeof(TestCases)/sizeof(KMBaseData); i++) {
TestData.push_back(TestCases[i]);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int status = 0;
std::vector<KMBaseData> TestData;
std::vector<double> TestTimes;
try {
InitTestData(TestData);
int Choice = LetUserEnterTestCaseNumber(TestData);
if (Choice < 0)
{
return status;
}
if (Choice < 15)
{
ExecutionLoop(TestData[Choice-1]);
}
else
{
for (auto TestDataIter: TestData) {
TestTimes.push_back(ExecutionLoop(TestDataIter));
}
}
OutputOverAllStatistics(TestTimes);
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;
}
KnightMovesImplementation.h
#pragma once
/*
* KnightMovesImplementation.h
*
* Created on: Mar 18, 2016
* Modified on: June 20, 2016
* Author: pacmaninbw
*
* 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 actual implementation is documented in the CPP file because it
* can be changed. This head file provides the public interface which
* should not be changed. The public interface may be moved to a
* super class in the future.
*/
#ifndef KNIGHTMOVESIMPLEMENTATION_H_
#define KNIGHTMOVESIMPLEMENTATION_H_
#include "KMPath.h"
#include "KMOutputData.h"
#include "KMMoveFilters.h"
class KnightMovesImplementation {
private:
KMBoardLocation m_PointOfOrigin;
KMBoardLocation m_Destination;
unsigned int m_SingleSideBoardDimension;
KnightMovesMethodLimitations m_PathLimitations;
KMOutputData *m_Results;
KMMoveFilters *m_MoveFilters;
KMPath *m_Path;
protected:
bool CalculatePath(KMMove CurrentMove); // Recursive function
void InitPointOfOrigin(KMBaseData UserData);
void InitDestination(KMBaseData UserData);
public:
KnightMovesImplementation(KMBaseData UserData);
virtual ~KnightMovesImplementation(void);
KMOutputData CalculatePaths();
};
#endif /* KNIGHTMOVESIMPLEMENTATION_H_ */
KnightsImplementation.cpp
/*
* KnightMovesImplementation.cpp
*
* Created on: Mar 18, 2016
* Modified on: June 21, 2016
* Commented on: June 24, 2016
* Author: pacmaninbw
*
* This class implements the search for all possible paths for a Knight
* on a chess board from one particular square on the board to another
* particular square on the board.
*
* 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 m_Path variable is used as a stack within the search.
*
* 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
* m_MoveFilters.GetPossibleMoves() function it calls performs a breadth
* first search of the current level.
*
*/
#include "stdafx.h"
#include "KnightMoves.h"
#include "KnightMovesImplementation.h"
#include "KMBoardDimensionConstants.h"
KnightMovesImplementation::~KnightMovesImplementation(void)
{
delete m_MoveFilters;
delete m_Results;
delete m_Path;
}
KnightMovesImplementation::KnightMovesImplementation(KMBaseData UserInputData)
: m_SingleSideBoardDimension(UserInputData.m_DimensionOneSide),
m_PathLimitations(UserInputData.m_LimitationsOnMoves)
{
InitPointOfOrigin(UserInputData);
InitDestination(UserInputData);
m_Path = new KMPath;
m_MoveFilters = new KMMoveFilters(static_cast<unsigned int>(UserInputData.m_DimensionOneSide), UserInputData.m_LimitationsOnMoves);
m_Results = new KMOutputData(m_PointOfOrigin, m_Destination, m_SingleSideBoardDimension, m_PathLimitations);
}
void KnightMovesImplementation::InitPointOfOrigin(KMBaseData 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(KMBaseData 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()
{
KMRandomAccessMoveCollection PossibleFirstMoves = m_MoveFilters->GetPossibleMoves(m_PointOfOrigin);
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()) {
CalculatePath(CurrentMove);
}
}
}
return *m_Results;
}
bool KnightMovesImplementation::CalculatePath(KMMove CurrentMove)
{
bool CompletedSearch = false;
KMBoardLocation CurrentLocation = CurrentMove.GetNextLocation();
m_Path->AddMoveToPath(CurrentMove);
m_MoveFilters->PushVisited(CurrentLocation);
if (CurrentLocation == m_Destination)
{
m_Results->AddPath(*m_Path);
CompletedSearch = true;
m_Results->IncrementAttemptedPaths();
}
else
{
if (CurrentMove.IsValid())
{
KMRandomAccessMoveCollection PossibleMoves = m_MoveFilters->GetPossibleMoves(CurrentLocation);
if (!PossibleMoves.empty())
{
for (auto NextMove : PossibleMoves)
{
CalculatePath(NextMove);
}
}
else
{
// No more moves to test, record the attempted path
m_Results->IncrementAttemptedPaths();
}
}
else
{
// There is a logic error if we get here.
std::cerr << "In KnightMovesImplementation::CalculatePath CurrentMove Not Valid" << std::endl;
}
}
m_Path->RemoveLastMove();
m_MoveFilters->PopVisited();
return CompletedSearch;
}
KMMoveFilters.h
#pragma once
/*
* KMMoveFilters.h
*
* Created on: Jun 20, 2016
* Author: pacmaninbw
*
* 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.
*/
#ifndef KMMOVEFILTERS_H_
#define KMMOVEFILTERS_H_
#include <vector>
#include "KnightMoves.h"
#include "KMMove.h"
class KMMoveFilters {
private:
std::vector<KMBoardLocation> m_VisitedLocations;
std::vector<unsigned int> m_VisitedRows;
std::vector<unsigned int> m_VisitedColumns;
unsigned int m_SingleSideBoardDimension;
KnightMovesMethodLimitations m_PathLimitations;
static KMRandomAccessMoveCollection AllPossibleMoves;
// 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;
protected:
bool IsNotPreviouslyVisited(KMMove Move) const { return IsNotPreviouslyVisited(Move.GetNextLocation()); };
bool IsNotPreviouslyVisited(KMBoardLocation Destination) const;
public:
KMMoveFilters(void);
KMMoveFilters(unsigned int BoardDimension, KnightMovesMethodLimitations SlicingMethod);
void ResetFilters(unsigned int BoardDimension, KnightMovesMethodLimitations SlicingMethod) {m_SingleSideBoardDimension = BoardDimension; m_PathLimitations = SlicingMethod; }
virtual ~KMMoveFilters(void);
void PushVisited(KMBoardLocation Location);
void PopVisited();
KMRandomAccessMoveCollection GetPossibleMoves(const KMBoardLocation CurrentLocation) const;
};
KMMoveFilters.cpp
/*
* KMMoveFilters.cpp
*
* Created on: Jun 20, 2016
* Author: pacmaninbw
*/
#include "stdafx.h"
#include <stdexcept>
#include <algorithm>
#include "KMBoardDimensionConstants.h"
#include "KMMoveFilters.h"
KMMoveFilters::~KMMoveFilters(void)
{
}
KMMoveFilters::KMMoveFilters(void)
: m_SingleSideBoardDimension(DefaultBoardDimensionOnOneSide),
m_PathLimitations(DenyByPreviousRowOrColumn)
{
AllPossibleMoves.push_back(Left1Up2);
AllPossibleMoves.push_back(Left2Up1);
AllPossibleMoves.push_back(Left2Down1);
AllPossibleMoves.push_back(Left1Down2);
AllPossibleMoves.push_back(Right1Up2);
AllPossibleMoves.push_back(Right2Up1);
AllPossibleMoves.push_back(Right2Down1);
AllPossibleMoves.push_back(Right1Down2);
}
KMMoveFilters::KMMoveFilters(unsigned int BoardDimension, KnightMovesMethodLimitations SlicingMethod)
: m_SingleSideBoardDimension(BoardDimension), m_PathLimitations(SlicingMethod)
{
AllPossibleMoves.push_back(Left1Up2);
AllPossibleMoves.push_back(Left2Up1);
AllPossibleMoves.push_back(Left2Down1);
AllPossibleMoves.push_back(Left1Down2);
AllPossibleMoves.push_back(Right1Up2);
AllPossibleMoves.push_back(Right2Up1);
AllPossibleMoves.push_back(Right2Down1);
AllPossibleMoves.push_back(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;
KMMove KMMoveFilters::Left1Up2(Left1, Up2, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Left2Up1(Left2, Up1, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Left2Down1(Left2, Down1, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Left1Down2(Left1, Down2, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Right1Up2(Right1, Up2, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Right2Up1(Right2, Up1, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Right2Down1(Right2, Down1, DefaultBoardDimensionOnOneSide);
KMMove KMMoveFilters::Right1Down2(Right1, Down2, DefaultBoardDimensionOnOneSide);
KMRandomAccessMoveCollection KMMoveFilters::AllPossibleMoves;
KMRandomAccessMoveCollection KMMoveFilters::GetPossibleMoves(const KMBoardLocation CurrentLocation) const
{
KMRandomAccessMoveCollection PossibleMoves;
for (auto PossibeMove : AllPossibleMoves) {
KMMove *TempMove = new KMMove(PossibeMove);
TempMove->SetBoardDimension(m_SingleSideBoardDimension);
TempMove->SetOriginCalculateDestination(CurrentLocation);
if ((TempMove->IsValid()) && (IsNotPreviouslyVisited(*TempMove))) {
PossibleMoves.push_back(*TempMove);
}
}
return PossibleMoves;
}
bool KMMoveFilters::IsNotPreviouslyVisited(KMBoardLocation PossibleDestination) const
{
bool NotPrevioslyVisited = true;
if (!m_VisitedLocations.empty()) { // This is always a test, we can't move backwards
if (std::find(m_VisitedLocations.begin(), m_VisitedLocations.end(), PossibleDestination)
!= m_VisitedLocations.end()) {
NotPrevioslyVisited = false;
}
}
switch (m_PathLimitations) {
default :
throw std::runtime_error("KMPath::CheckMoveAgainstPreviousLocations : Unknown type of Path Limitation.");
case DenyByPreviousLocation :
// Always tested above.
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 KMMoveFilters::PushVisited(KMBoardLocation Location)
{
m_VisitedRows.push_back(Location.GetRow());
m_VisitedColumns.push_back(Location.GetColumn());
m_VisitedLocations.push_back(Location);
}
void KMMoveFilters::PopVisited()
{
m_VisitedRows.pop_back();
m_VisitedColumns.pop_back();
m_VisitedLocations.pop_back();
}