C++ solver for the Knight's Tour. Runtime on my Mac, for 8x8 board: real 0m0.530s user 0m0.529s sys 0m0.001s

knight.cpp

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#include <stack>

#include <cstring>

typedef std::pair<int, int> Position;

template<int _WIDTH, int _HEIGHT>
class KnightsPathSolver
{
public:
    KnightsPathSolver()
    {
        GenerateMoves();
    }
    
    bool Solve(const Position& initialPosition, std::stack<Position>& solution)
    {
        std::memset(mStatus, 0, sizeof(bool) * _WIDTH * _HEIGHT);
        mStatus[initialPosition.first][initialPosition.second] = true;
        
        if (Run(initialPosition, 1, solution))
            solution.push(initialPosition);
        
        return !solution.empty();
    }
    
private:
    bool Run(const Position& pos, int depth, std::stack<Position>& solution)
    {
        auto it = std::begin(mMoves);
        
        if (depth++ == _WIDTH * _HEIGHT)
            return true;
        
        for ( ; it != std::end(mMoves); ++it)
        {
            auto position = std::make_pair(pos.first + it->first, pos.second + it->second);           
            
            if (!IsValid(position))
            {
                continue;
            }
            
            mStatus[position.first][position.second] = true;
            if (Run(position, depth, solution))
            {
                solution.push(position);
                return true;
            }
            
            mStatus[position.first][position.second] = false;
        }
        
        return false;
    }
    
    bool IsValid(const Position& position) const
    {
        return (position.first  >= 0 && position.first < _WIDTH)  &&
               (position.second >= 0 && position.second < _HEIGHT) &&
               !mStatus[position.first][position.second];
    }
    
    void GenerateMoves()
    {
        const Position baseMoves[] = { std::make_pair(1, 2), std::make_pair(2, 1) };
        
        mMoves.reserve(8);
        
        for (auto &x : baseMoves)
            for (int i = 0; i < 4; i++)
                mMoves.push_back(std::make_pair((i & 2) ? x.first  : -x.first,
                                                (i & 1) ? x.second : -x.second));
    }
    
    std::vector<Position> mMoves;
    bool mStatus[_WIDTH][_HEIGHT];
};

int main(int, char **)
{
    std::stack<Position>    solution;
    KnightsPathSolver<8, 8> solver;
    solver.Solve(std::make_pair(0, 0), solution);

    while (!solution.empty())
    {
        auto &x = solution.top();
        
        std::cout << (char) ('a' + x.first) << 8 - x.second << std::endl;
        
        solution.pop();
    }
    
  return 0;
}