graph/example/knights_tour.cpp

//=======================================================================
// Copyright 2001 Jeremy G. Siek, Andrew Lumsdaine, Lie-Quan Lee,
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#include <boost/config.hpp>
#include <stdlib.h>
#include <iostream>
#include <stack>
#include <queue>
#include <ctime>
#include <boost/operators.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/property_map/property_map.hpp>

using namespace boost;

typedef std::pair< int, int > Position;
Position knight_jumps[8]
    = { Position(2, -1), Position(1, -2), Position(-1, -2), Position(-2, -1),
          Position(-2, 1), Position(-1, 2), Position(1, 2), Position(2, 1) };

Position operator+(const Position& p1, const Position& p2)
{
    return Position(p1.first + p2.first, p1.second + p2.second);
}

struct knights_tour_graph;
struct knight_adjacency_iterator
: public boost::forward_iterator_helper< knight_adjacency_iterator, Position,
      std::ptrdiff_t, Position*, Position >
{
    knight_adjacency_iterator() {}
    knight_adjacency_iterator(int ii, Position p, const knights_tour_graph& g)
    : m_pos(p), m_g(&g), m_i(ii)
    {
        valid_position();
    }
    Position operator*() const { return m_pos + knight_jumps[m_i]; }
    void operator++()
    {
        ++m_i;
        valid_position();
    }
    bool operator==(const knight_adjacency_iterator& x) const
    {
        return m_i == x.m_i;
    }

protected:
    void valid_position();
    Position m_pos;
    const knights_tour_graph* m_g;
    int m_i;
};

struct knights_tour_graph
{
    typedef Position vertex_descriptor;
    typedef std::pair< vertex_descriptor, vertex_descriptor > edge_descriptor;
    typedef knight_adjacency_iterator adjacency_iterator;
    typedef void out_edge_iterator;
    typedef void in_edge_iterator;
    typedef void edge_iterator;
    typedef void vertex_iterator;
    typedef int degree_size_type;
    typedef int vertices_size_type;
    typedef int edges_size_type;
    typedef directed_tag directed_category;
    typedef disallow_parallel_edge_tag edge_parallel_category;
    typedef adjacency_graph_tag traversal_category;
    knights_tour_graph(int n) : m_board_size(n) {}
    int m_board_size;
};
int num_vertices(const knights_tour_graph& g)
{
    return g.m_board_size * g.m_board_size;
}

void knight_adjacency_iterator::valid_position()
{
    Position new_pos = m_pos + knight_jumps[m_i];
    while (m_i < 8
        && (new_pos.first < 0 || new_pos.second < 0
            || new_pos.first >= m_g->m_board_size
            || new_pos.second >= m_g->m_board_size))
    {
        ++m_i;
        new_pos = m_pos + knight_jumps[m_i];
    }
}

std::pair< knights_tour_graph::adjacency_iterator,
    knights_tour_graph::adjacency_iterator >
adjacent_vertices(
    knights_tour_graph::vertex_descriptor v, const knights_tour_graph& g)
{
    typedef knights_tour_graph::adjacency_iterator Iter;
    return std::make_pair(Iter(0, v, g), Iter(8, v, g));
}

struct compare_first
{
    template < typename P > bool operator()(const P& x, const P& y)
    {
        return x.first < y.first;
    }
};

template < typename Graph, typename TimePropertyMap >
bool backtracking_search(Graph& g,
    typename graph_traits< Graph >::vertex_descriptor src,
    TimePropertyMap time_map)
{
    typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
    typedef std::pair< int, Vertex > P;
    std::stack< P > S;
    int time_stamp = 0;

    S.push(std::make_pair(time_stamp, src));
    while (!S.empty())
    {
        Vertex x;
        boost::tie(time_stamp, x) = S.top();
        put(time_map, x, time_stamp);
        // all vertices have been visited, success!
        if (time_stamp == num_vertices(g) - 1)
            return true;

        bool deadend = true;
        typename graph_traits< Graph >::adjacency_iterator i, end;
        for (boost::tie(i, end) = adjacent_vertices(x, g); i != end; ++i)
            if (get(time_map, *i) == -1)
            {
                S.push(std::make_pair(time_stamp + 1, *i));
                deadend = false;
            }

        if (deadend)
        {
            put(time_map, x, -1);
            S.pop();
            boost::tie(time_stamp, x) = S.top();
            while (get(time_map, x) != -1)
            { // unwind stack to last unexplored vertex
                put(time_map, x, -1);
                S.pop();
                boost::tie(time_stamp, x) = S.top();
            }
        }

    } // while (!S.empty())
    return false;
}

template < typename Vertex, typename Graph, typename TimePropertyMap >
int number_of_successors(Vertex x, Graph& g, TimePropertyMap time_map)
{
    int s_x = 0;
    typename graph_traits< Graph >::adjacency_iterator i, end;
    for (boost::tie(i, end) = adjacent_vertices(x, g); i != end; ++i)
        if (get(time_map, *i) == -1)
            ++s_x;
    return s_x;
}

template < typename Graph, typename TimePropertyMap >
bool warnsdorff(Graph& g, typename graph_traits< Graph >::vertex_descriptor src,
    TimePropertyMap time_map)
{
    typedef typename graph_traits< Graph >::vertex_descriptor Vertex;
    typedef std::pair< int, Vertex > P;
    std::stack< P > S;
    int time_stamp = 0;

    S.push(std::make_pair(time_stamp, src));
    while (!S.empty())
    {
        Vertex x;
        boost::tie(time_stamp, x) = S.top();
        put(time_map, x, time_stamp);
        // all vertices have been visited, success!
        if (time_stamp == num_vertices(g) - 1)
            return true;

        // Put adjacent vertices into a local priority queue
        std::priority_queue< P, std::vector< P >, compare_first > Q;
        typename graph_traits< Graph >::adjacency_iterator i, end;
        int num_succ;
        for (boost::tie(i, end) = adjacent_vertices(x, g); i != end; ++i)
            if (get(time_map, *i) == -1)
            {
                num_succ = number_of_successors(*i, g, time_map);
                Q.push(std::make_pair(num_succ, *i));
            }
        bool deadend = Q.empty();
        // move vertices from local priority queue to the stack
        for (; !Q.empty(); Q.pop())
        {
            boost::tie(num_succ, x) = Q.top();
            S.push(std::make_pair(time_stamp + 1, x));
        }
        if (deadend)
        {
            put(time_map, x, -1);
            S.pop();
            boost::tie(time_stamp, x) = S.top();
            while (get(time_map, x) != -1)
            { // unwind stack to last unexplored vertex
                put(time_map, x, -1);
                S.pop();
                boost::tie(time_stamp, x) = S.top();
            }
        }

    } // while (!S.empty())
    return false;
}

struct board_map
{
    typedef int value_type;
    typedef Position key_type;
    typedef read_write_property_map_tag category;
    board_map(int* b, int n) : m_board(b), m_size(n) {}
    friend int get(const board_map& ba, Position p);
    friend void put(const board_map& ba, Position p, int v);
    friend std::ostream& operator<<(std::ostream& os, const board_map& ba);

private:
    int* m_board;
    int m_size;
};

int get(const board_map& ba, Position p)
{
    return ba.m_board[p.first * ba.m_size + p.second];
}

void put(const board_map& ba, Position p, int v)
{
    ba.m_board[p.first * ba.m_size + p.second] = v;
}

std::ostream& operator<<(std::ostream& os, const board_map& ba)
{
    for (int i = 0; i < ba.m_size; ++i)
    {
        for (int j = 0; j < ba.m_size; ++j)
            os << get(ba, Position(i, j)) << "\t";
        os << std::endl;
    }
    return os;
}

int main(int argc, char* argv[])
{
    int N;
    if (argc == 2)
        N = atoi(argv[1]);
    else
        N = 8;

    knights_tour_graph g(N);
    int* board = new int[num_vertices(g)];
    board_map chessboard(board, N);
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            put(chessboard, Position(i, j), -1);

    bool ret = warnsdorff(g, Position(0, 0), chessboard);

    if (ret)
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < N; ++j)
                std::cout << get(chessboard, Position(i, j)) << "\t";
            std::cout << std::endl;
        }
    else
        std::cout << "method failed" << std::endl;
    return 0;
}