Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Knights Tour Prototype
// 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))
);
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.