Knights Tour Prototype

knights-tour.cpp

// Copyright Dave Abrahams 2012. 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 <bitset>
#include <utility>
#include <map>
#include <boost/integer.hpp>
#include <boost/mpl/size_t.hpp>
#include <boost/mpl/if.hpp>
#include <boost/concept_check.hpp>
#include <boost/operators.hpp>
#include <boost/static_assert.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/iterator/counting_iterator.hpp>
#include <boost/graph/astar_search.hpp>
#include <boost/graph/property_maps/constant_property_map.hpp>

namespace mpl = boost::mpl;

template <unsigned N, unsigned test = 0>
struct bits_required
  : mpl::if_c<
        (~(-1UL << test) & N) == N,
        mpl::size_t<test>,
        bits_required<N,test+1> >::type
{
};

BOOST_STATIC_ASSERT(bits_required<0>::value == 0);
BOOST_STATIC_ASSERT(bits_required<1>::value == 1);
BOOST_STATIC_ASSERT(bits_required<2>::value == 2);
BOOST_STATIC_ASSERT(bits_required<3>::value == 2);
BOOST_STATIC_ASSERT(bits_required<4>::value == 3);
BOOST_STATIC_ASSERT(bits_required<127>::value == 7);

int const knight_moves[][2] = {
    {1,2},{2,1},
    {1,-2},{-2,1},
    {-1,2},{2,-1},
    {-1,-2},{-2,-1}
};

template <unsigned N, unsigned M>
struct knights_tour
{
    static unsigned const num_positions = (N*M);
    typedef std::bitset<num_positions> position_set;

    // Return True if the bit corresponding to position (x,y) is set
    static bool is_set(position_set const& pos, unsigned x, unsigned y)
    {
        return pos[x*y];
    }
    
    // Satisfying Graph requirements
    
    // A vertex in the tour graph is fully described by the knight's
    // current position, and which vertices have been visited
    struct vertex_descriptor
      : boost::equality_comparable<vertex_descriptor>
    {
        typedef knights_tour graph_type;
        
        position_set visited;
        
        typename boost::uint_t<bits_required<N>::value>::least x;
        typename boost::uint_t<bits_required<M>::value>::least y;

        vertex_descriptor(
            unsigned x = 0, unsigned y = 0,
            position_set const& visited = position_set()
        )
            : visited(visited),
              x(x),
              y(y)
        {}
        
        friend bool operator==(
            vertex_descriptor const& a, vertex_descriptor const& b)
        {
            return a.x == b.x && a.y == b.y && a.visited == b.visited;
        }

        int next_move(int i = -1) const
        {
            while (++i < 8) {
                int const new_x = x + knight_moves[i][0];
                int const new_y = y + knight_moves[i][1];
                if (new_x >= 0 && new_x < N && new_y >= 0 && new_y < M)
                    if (!visited[new_x + new_y*N])
                        return i;
            }
            return -1;
        }
    };
    
    BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<vertex_descriptor>));
    BOOST_CONCEPT_ASSERT((boost::Assignable<vertex_descriptor>));
    BOOST_CONCEPT_ASSERT((boost::EqualityComparable<vertex_descriptor>));

    struct edge_descriptor
      : boost::equality_comparable<edge_descriptor>
    {
        vertex_descriptor start;
        signed char move_index;

        edge_descriptor() {}
        
        edge_descriptor(vertex_descriptor const& start, signed char move_index)
            : start(start), move_index(move_index)
        {}
        
        friend bool operator==(
            edge_descriptor const& a, edge_descriptor const& b)
        {
            return a.start == b.start && a.move_index == b.move_index;
        }

        edge_descriptor& operator++()
        {
            move_index = start.next_move(move_index);
            return *this;
        }
    };

    static edge_descriptor begin_edge(vertex_descriptor const& pos)
    {
        return edge_descriptor(pos, pos.next_move(-1));
    }
    
    static edge_descriptor end_edge(vertex_descriptor const& pos)
    {
        return edge_descriptor(pos, -1);
    }
    
    BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<edge_descriptor>));
    BOOST_CONCEPT_ASSERT((boost::Assignable<edge_descriptor>));
    BOOST_CONCEPT_ASSERT((boost::EqualityComparable<edge_descriptor>));

    // Documented Graph requirements
    typedef boost::directed_tag directed_category;
    typedef boost::disallow_parallel_edge_tag edge_parallel_category;
    typedef boost::incidence_graph_tag traversal_category;

    // Incidence Graph requirements (see https://svn.boost.org/trac/boost/ticket/7741)
    typedef boost::counting_iterator<edge_descriptor, std::input_iterator_tag, int>
    out_edge_iterator;
    
    typedef unsigned char degree_size_type;

    friend vertex_descriptor source(edge_descriptor const& e, knights_tour)
    {
        return e.start;
    }

    friend vertex_descriptor target(edge_descriptor const& e, knights_tour)
    {
        vertex_descriptor r = e.start;
        r.x += knight_moves[e.move_index][0];
        r.y += knight_moves[e.move_index][1];
        r.visited[r.x+r.y*N] = true;
        return r;
    }

    friend std::pair<out_edge_iterator,out_edge_iterator>
    out_edges(vertex_descriptor const& u, knights_tour)
    {
        return std::make_pair(
            out_edge_iterator(edge_descriptor(u, u.next_move(-1))),
            out_edge_iterator(edge_descriptor(u, -1)));
    }
    
    friend degree_size_type
    out_degree(vertex_descriptor const& u, knights_tour)
    {
        unsigned count = 0;
        for (int i = -1; (i = u.next_move(i)) >= 0; ++count);
        return count;
    }
    
    // Dummies to satisfy the default implementation of graph_traits
    typedef void adjacency_iterator;
    typedef void in_edge_iterator;
    typedef void vertex_iterator;
    typedef void edge_iterator;
    typedef void vertices_size_type;
    typedef void edges_size_type;
};

#if 0
namespace boost
{
  template <unsigned N, unsigned M>
  struct graph_traits<knights_tour<N,M> >
  {
      
  };
}
#endif

BOOST_CONCEPT_ASSERT((boost::IncidenceGraphConcept<knights_tour<8,8> >));

struct heuristic
{
    template <class Descriptor>
    unsigned operator()(Descriptor const& d) const
    {
        return out_degree(d, typename Descriptor::graph_type());
    }
};

int main()
{
    typedef knights_tour<8,8> tour;
    std::map<tour::vertex_descriptor,tour::vertex_descriptor> predecessors;
    boost::astar_search_no_init(
        tour(),
        tour::vertex_descriptor(),
        heuristic(),
        predecessor_map(predecessors)
        .weight_map(boost::make_constant_property<tour::vertex_descriptor>(1))
    );
};