123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343 |
- //=======================================================================
- // 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;
- }
|