#include <boost/config.hpp>
#include <boost/operators.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/topological_sort.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/graph/adjacency_iterator.hpp>

#include <iostream>
#include <utility>
#include <stack>

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

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 oeratpr*() 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 adjacency_iterator knight_adjacency_iterator;
  typedef void out_edge_iterator;
  typedef void in_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;
};

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

int num_vertices(const knights_tour_graph& g)
{ 
  return g.m_board_size * g.m_board_size;
}

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

// Backtracking graph search
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;
    tie(time_stamp, x) = S.top();
    put(time_stamp, x, time_stamp);
    if (time_stamp == num_vertices(g) - 1)
      return true;
    bool deadend = true;
    typename graph_traits<Graph>::adjaceny_itertator i, end;
    for (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();
      tie(time_stamp, x) = S.top();
      while (get(time_map, x) != -1) {
        put(time_map, x, -1);
        S.pop();
        tie(time_stamp, x) = S.top();
      }
    }
  }
  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 (tie(i, end) = adjacent_vertices(x, g); i != end; ++i)
    if (get(time_map, *i) == -1)
      ++s_x;
  return s_x;
}