Kojirion

Home Projects Links About RSS

Knight swap

Start_Position

Following is a close look at a C++11 application solving the problem in the least number of moves. The Boost.Graph library is employed; furthermore most loops are eschewed in favor of algorithms and functors from Boost’s Range and Phoenix libraries.

Namespaces

First, discarding namespace qualifiers:

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

There are two major reasons to avoid doing this;

i) Namespace conflicts
ii) Being able to tell what library a function or class is from at a glance.

However, in rather small snippets where specific libraries are used, the qualifiers clutter the code and obscure its meaning. For instance, in this example it does not matter whether the transform and copy algorithms are from Boost or the STL - they are functionally equivalent; it is the operation that is important.

Representing the board

Color

First, an enum to distinguish between the two sides:

enum class Color {
    White,
    Black,
};

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

    return Color::White;
}

Using the strongly typed enum class safeguards against implicit conversions to int. On the other hand, the flip operator has to be manually written.

Square

There are several ways to represent the board. The most straightforward would be an array with appropriate indexing (row * nr_columns + col), while chess engines employ bitboards that allow fast generation of moves. In this example a simple Square struct, consisting of a two integers describing row and column, will form the building block of a Move and a Position class. It is expressive and the most flexible - it will outshine other approaches if one tackles the puzzle on a board of arbitrary shape with holes in the middle.

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;
}

Because the board is small, 8-bit unsigned integers are more than sufficient to describe the row and column. On the other hand, depending on the CPU the application is run on, these may not be the fastest type to operate on. Therefore the choice is delegated to the compiler which will pick the fastest integer of width at least 8 bits.

The assertion that follows ensures that Square is a Plain Old Data type and will reap the relevant benefits - for instance, its default copy constructor will perform a bitwise copy of the object.

Operator < is written so that Squares can be used as a key in a map. Lastly, an ostream operator is written to allow pretty output of the moves later; a static array of chars is used as a lookup table to convert column indices to letters.

Move

Move is also a POD that consists of two Squares:

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>;

A standard vector is aliased as a convenient container of Moves. This is equivalent to a typedef; the new syntax is clearer since the alias appears first and is cleanly separated from the type it represents.

Position

The Position class will carry the information describing a position on the board; hence it will also feature a method returning the legal Moves on it. A check on whether a Move is legal can be broken down to 3 steps - assuming there is a knight on the first square:

The second step is a pure function; it does not depend on the position and will always return the same output for the same input. Therefore, it can be entirely precomputed and the results stored as a static lookup table, such as a standard multimap from Square to Square.

using Attacks = std::multimap<Square, Square>;
static const Attacks attacks;

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}},
};

To represent the position, it is sufficient to keep track of the squares the white and black knights are on.
In order to be able to use Position as key, there are two options - a comparator, such as operator<, or a hash function.
Here the first option is chosen. To that end, the class will hold the squares of the white and black knights in two separate arrays that will be kept sorted (it is enough to sort them on construction). Lastly, it also holds the Color of whose turn it is, making for a total of 3 private variables:

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

private:
    KnightSquares whiteKnights, blackKnights;
    Color m_color;

The class features 3 constructors:

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);
}

The newly created position is the same as the old one with the move made on it and the color flipped. Thus new positions are generated from the legal moves of the previous one.

Assuming that the first square contains a knight and that the knight jump represented is legal, a function validating moves consists of the other two steps described above:

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;
}

First all occupied squares are iterated through - if any is the target square, the move is illegal. Then two ranges are checked for intersection;

If the ranges intersect then the knight will be attacking a comrade from its new square and therefore the move is illegal. The natural syntax of the predicate on line 8 comes courtesy of Phoenix’s lazy operators. The same functionality can be achieved by using std::not_equal_to - or simply writing a lambda.

To generate all legal moves of the position, one needs to

The following function accomplishes this:

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;
}

The Graph

The Boost Graph Library is an exemplar of generic programming. Although it provides several graph classes, its algorithms can be applied on any class that models the relevant concepts. The problem at hand presents a dilemma; during the graph generation, it is more convenient and faster to use Positions as the key to vertex descriptors - so that edges can be added to existing positions, as well as ensuring unique insertions.
On the other hand, when extending one of the algorithms by creating a visitor, the vertex descriptors have to be used as the key.
The library’s undocumented labeled_graph allows using a property as the key to vertices, while Property maps are the designated way of associating data with vertices and edges. None however address both issues at once satisfactorily. The optimal solution likely is to forego the library’s graph classes and instead create a problem specific one. Here a brute method is used instead - Positions will be stored both outside the graph and internally as properties.

Properties

To store Positions and Moves as properties internally as properties of vertices and edges respectively and be able to look them up later, tags are required. These are simple structs that will be bundled with the classes themselves:

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;

Adjacency list

The library’s adjacency list will serve as the graph class.

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

The uniqueness of the vertices and of the edges of each vertex (no parallel edges) is ensured during generation. Therefore, vectors are picked as the most efficient containers for both. Clearly, the graph is directed.

Since the edges of the graph all have the same weight, it is sufficient to perform a breadth-first search to find the shortest path. To get results from the algorithm, Boost.Graph allows supplying visitors to the search - these are objects whose functions will be called during the search. The recommended way to exit early is to throw an exception. Therefore two visitor objects will be supplied to the search - one that checks if the knights have swapped position and one to record the predecessors of each position.

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;

KnightSwap is a struct that serves as the exception to be thrown. Its only member is the vertex descriptor identifying the swapped position. SwapChecker is the visitor that will check for knight swap. If this were the sole one, it would be enough to derive from default_bfs_visitor. However, since it will be bundled together with the predecessor recorder, it models an EventVisitor instead. The event_filter typedef determines when its operator() will be called.

The predecessor recorder will be provided by the library.

Walking the path

When the search has finished, the path can be read by following the predecessors from the swapped position to the initial; this can be easily done with a while loop. The fancier way is to define an iterator to perform this traversal with:

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;
};

Inheriting from Boost’s iterator_facade makes for more concise code than writing an iterator by hand. The gotcha here is that the edge is directed to vertex_1.

Finding the path

Everything is brought together into a Pathfinder class that will hold the graph and a map from Positions to vertex descriptors.

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

Unique insertions

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};
}

Boost.Graph does not offer a function to add vertices keeping them unique while also indicating whether one was added. This function will mimic the one that does exist for edges; returning a pair, the first member being the vertex descriptor - whether of the new vertex or an old one - and the second a boolean indicating whether there was an insertion. This is where the map from positions to vertex descriptors comes in.

Position generation

All positions can be generated through a recursive function. For a given position, each of the legal moves is used to generate a new position, which is added to the graph by the function above. If there was an insertion, then the function is called on the new position.

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);
    }
}

decltype allows declaring the two vertices with the same type without explicitly stating either’s - both are deduced by the compiler. Boost::tie offers a handy way of unpacking the returned pair.

Execution

With everything in place, all the work will be carried out in the Pathfinder’s construction.

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);

The initial position is constructed and added to the graph; it is also added to the map pointing to its vertex descriptor. Then generatePositions() is called on it; the recursion will generate the entire graph.

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));

The SwapChecker visitor is bundled together with a predecessor recorder provided by the library. An instance of PredecessorMap is passed to its constructor, adapted as an associative property map. The bundle is in turned adapted as a visitor to the breadth-first search.

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"));
}

The search is wrapped within a try-catch block to catch the exception denoting knight swap. When that is done, a range is constructed that can be traversed to output the path. However, it is a forward range only - it must first be stored in a vector, which is then copied reversed to standard output:

a1-b3
d2-b1
a2-c3
d3-c1
a3-c2
c1-a2
b3-c1
b1-a3
c1-d3
a2-c1
c2-a1
a3-c2
a1-b3
c2-a1
c3-a2
d1-c3
b3-d2
c3-b1
a2-c3
b1-a3
c3-d1
c1-a2

Performance

On a 3.2GHz core, compiled with gcc -O3, the entire run takes ~0.016 seconds on average. Avenues exist to further improve performance - possibly to be explored in future posts.

Source

The full source code may be found here.
To compile it, a C++11 compliant compiler is required, as well as the Boost libraries. Header only libraries are sufficient unless one uncomments the timer line to benchmark. Board and piece art by Peter Wong (http://www.virtualpieces.net/).