Knight swap

KnightSwap.cpp

#include <boost/range/algorithm.hpp>
#include <boost/range/adaptors.hpp>
#include <boost/range/join.hpp>
#include <boost/range/algorithm_ext/push_back.hpp>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>

#include <boost/phoenix.hpp>
#include <cstdint>
#include <iostream>
#include <boost/timer/timer.hpp>

using namespace boost;
using namespace adaptors;
using phoenix::arg_names::arg1;
using std::placeholders::_1;
using std::bind;

//Color
enum class Color {
    White,
    Black,
};

Color operator!(Color rhs) {
    if (rhs == Color::White)
        return Color::Black;

    return Color::White;
}

//Square

struct Square {
    std::uint_fast8_t row, col;
};

static_assert(std::is_pod<Square>::value, "Square is POD");

bool operator==(const Square& lhs, const Square& rhs) {
    return (lhs.row == rhs.row) && (lhs.col == rhs.col);
}

bool operator!=(const Square& lhs, const Square& rhs) {
    return !(lhs == rhs);
}

bool operator<(const Square& lhs, const Square& rhs){
    if (lhs.row == rhs.row)
        return lhs.col < rhs.col;
    else return lhs.row < rhs.row;
}

std::ostream& operator<<(std::ostream& stream, const Square& square) {
    static const char* colToChar = "abcdefgh";
    stream << colToChar[square.col] << (square.row+1);
    return stream;
}

//Move

struct Move {
    Square square_1, square_2;
};

static_assert(std::is_pod<Move>::value, "Move is POD");

std::ostream& operator<<(std::ostream& stream, const Move& move) {
    stream << move.square_1 << "-" << move.square_2;
    return stream;
}

using Moves = std::vector<Move>;

//Position

class Position {
public:

    using Attacks = std::multimap<Square, Square>;

    static const Attacks attacks;

    using KnightSquares = std::array<Square, 3>;

    Position() {
    }

    Position(const KnightSquares& white, const KnightSquares& black, Color color = Color::White):
        whiteKnights(white),
        blackKnights(black),
        m_color(color)
    {
        sort(whiteKnights);
        sort(blackKnights);
    }

    Position(const Position& position, const Move& move):
        whiteKnights(position.whiteKnights),
        blackKnights(position.blackKnights),
        m_color(!position.m_color)
    {
        for (auto& square : join(whiteKnights, blackKnights)){
            if (square == move.square_1)
                square = move.square_2;
        }

        sort(whiteKnights);
        sort(blackKnights);
    }


    const KnightSquares& getKnightSquares() const{
        if (m_color == Color::White)
            return whiteKnights;
        else return blackKnights;
    }

    bool isLegal(const Move& move) const {

        for (const auto& square : join(whiteKnights, blackKnights)){
            if (square == move.square_2)
                return false;
        }

        auto ownKnights = getKnightSquares() | filtered (arg1 != move.square_1);
        const auto attacked = attacks.equal_range(move.square_2) | map_values;

        for (const auto& square : attacked){
            if (find(ownKnights, square) != ownKnights.end())
                return false;
        }

        return true;

    }


    Moves legalMoves() const{
        Moves toReturn;

        for (const auto& square_1 : getKnightSquares()){
            push_back(toReturn, attacks.equal_range(square_1)
                      | map_values
                      | transformed([&square_1](const Square& square){ return Move{square_1, square}; })
                      | filtered(bind(&Position::isLegal, this, _1)));

        }
        return toReturn;
    }

    bool operator<(const Position& rhs) const{
        if (whiteKnights == rhs.whiteKnights)
            return blackKnights < rhs.blackKnights;
        else return whiteKnights < rhs.whiteKnights;
    }

    bool operator==(const Position& rhs) const {
        return (whiteKnights == rhs.whiteKnights) && (blackKnights == rhs.blackKnights);
    }

private:
    KnightSquares whiteKnights, blackKnights;
    Color m_color;
};


const std::multimap<Square, Square> Position::attacks = {
    {{0,0}, {1,2}}, {{0,0}, {2,1}},
    {{1,0}, {0,2}}, {{1,0}, {2,2}},
    {{2,0}, {1,2}}, {{2,0}, {0,1}},
    {{0,1}, {1,3}}, {{0,1}, {2,2}}, {{0,1}, {2,0}},
    {{1,1}, {0,3}}, {{1,1}, {2,3}},
    {{2,1}, {1,3}}, {{2,1}, {0,2}}, {{2,1}, {0,0}},
    {{0,2}, {1,0}}, {{0,2}, {2,3}}, {{0,2}, {2,1}},
    {{1,2}, {0,0}}, {{1,2}, {2,0}},
    {{2,2}, {1,0}}, {{2,2}, {0,3}}, {{2,2}, {0,1}},
    {{0,3}, {1,1}}, {{0,3}, {2,2}},
    {{1,3}, {0,1}}, {{1,3}, {2,1}},
    {{2,3}, {1,1}}, {{2,3}, {0,2}},
};

struct Position_t {
    typedef vertex_property_tag kind;
};

struct Move_t {
    typedef edge_property_tag kind;
};

typedef property<Position_t, Position> PositionProperty;
typedef property<Move_t, Move> MoveProperty;

using Graph = adjacency_list<vecS, vecS, directedS, PositionProperty, MoveProperty>;
using Vertex = Graph::vertex_descriptor;

struct KnightSwap {
    Vertex value;
};

struct SwapChecker
{
    typedef on_discover_vertex event_filter;

    void operator()(Vertex u, const Graph &g){

        static const Position swapped({{{0,3},{1,3},{2,3}}}, {{{0,0},{1,0},{2,0}}});

        auto position = get(Position_t(), g, u);

        if (position == swapped)
            throw KnightSwap{u};
    }
};

using PredecessorMap = std::map<Vertex, Vertex>;
using Edge = PredecessorMap::value_type;

class PathIterator : public iterator_facade<PathIterator,  const Edge, forward_traversal_tag, Edge> {
public:
    PathIterator(Vertex vertex = 0, const PredecessorMap* predecessorMap = nullptr):
        vertex_1(vertex),
        m_predecessorMap(predecessorMap)
    { }

private:
    friend class boost::iterator_core_access;

    void increment() {
        vertex_1 = m_predecessorMap->at(vertex_1);
    }

    Edge dereference() const {
        return {m_predecessorMap->at(vertex_1), vertex_1};
    }

    bool equal(const PathIterator &other) const {

        return vertex_1 == other.vertex_1;
    }

    Vertex vertex_1;
    const PredecessorMap* m_predecessorMap;
};

class Pathfinder {
public:

    Pathfinder() {
        Position initial({{{0,0},{1,0},{2,0}}}, {{{0,3},{1,3},{2,3}}});
        m_vertices.emplace(initial, add_vertex(initial, m_graph));
        generatePositions(initial);

        PredecessorMap predecessorMap;
        auto pMap = make_assoc_property_map(predecessorMap);
        auto both = std::make_pair(record_predecessors(pMap, on_tree_edge()), SwapChecker());
        auto bothWrapped = visitor(make_bfs_visitor(both));

        try {
            breadth_first_search(m_graph, m_vertices.at(initial), bothWrapped);
        } catch (KnightSwap knightSwap) {

            auto pathRange = make_iterator_range(PathIterator(knightSwap.value, &predecessorMap), PathIterator(m_vertices.at(initial)));

            Moves path;

            transform(pathRange, std::back_inserter(path), [this](const Edge& edge){
                auto edge_desc = boost::edge(edge.first, edge.second, m_graph).first;
                return get(Move_t(), m_graph, edge_desc);
            });

            copy(path | reversed, std::ostream_iterator<Move>(std::cout, "\n"));
        }
    }

    std::pair<Vertex, bool> uniqueAdd(const Position& position)  {
        if (!m_vertices.count(position)){
            auto vertex = add_vertex(position, m_graph);
            m_vertices.emplace(position, vertex);
            return {vertex, true};
        }

        return {m_vertices.at(position), false};
    }

    void generatePositions(const Position& position){
        auto movesTotry = position.legalMoves();
        for (const auto& move : movesTotry){
            Position newPosition(position, move);
            auto vertex_1 = m_vertices.at(position);
            decltype(vertex_1) vertex_2;
            bool insertion;
            tie(vertex_2, insertion) = uniqueAdd(newPosition);
            add_edge(vertex_1, vertex_2, move, m_graph);
            if (insertion)
                generatePositions(newPosition);
        }
    }

private:
    Graph m_graph;
    std::map<Position, Vertex> m_vertices;
};


int main() {
    //Uncomment the following line to benchmark
    //timer::auto_cpu_timer timer;

    Pathfinder pathfinder;
}

On which IDE or Compiler should we run this code?